Sans Pareil Technologies, Inc.

Key To Your Business

Lab Exercise 9 - Templates


We will create a simple project that will implement a generic function as well as a generic class to illustrate the concepts and power of generic programming.

The generic function will implement a range based sort algorithm (similar to C++17 ranges), while the generic class will re-implement the Polygon hierarchy we developed in Lab 5.

As a final step we will illustrate the benefit of template metaprogramming (TMP) using factorial computation as an example.
generic.h 

We will implement a generic range based sort function, that just delegates to std::sort. The template function will work with any input type that provides begin() and end() functions that return iterators to the dataset. We also introduce a Range structure that can be used to represent a subset of data within a dataset. Notice how the sort function implementation does not care not need to know about whether the input range covers the entire dataset or not.

#pragma once
#include <algorithm>

namespace csc240
{
  template <typename Range>
  void sort( Range& range )
  {
    std::sort( range.begin(), range.end() );
  }

  template <typename Iterator>
  struct Range
  {
    Range( Iterator&& first, Iterator&& last ) : first{ first }, last{ last } {}

    Range( Range& ) = delete;
    Range& operator= ( Range & ) = delete;

    Iterator begin() noexcept { return first; }
    Iterator end() noexcept { return last; }

  private:
    Iterator first;
    Iterator last;
  };
}
generic.cpp 

We can now test our generic sort function using vectors or raw arrays of integer values. We will also test the sort function using a subset of data specified via an instance of the Range struct.

#include "catch.hpp"
#include "generic.h"

#include <iterator>
#include <vector>

using Vector = std::vector<uint32_t>;

#define INT_VALUES { 5, 3, 4, 2, 9, 1, 8, 6, 7, 0 }
#define INT_RESULTS { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
#define INT_PARTIAL { 2, 3, 4, 5, 9, 1, 8, 6, 7, 0 }

SCENARIO( "Generic sort can work with standard containers" )
{
  GIVEN( "A vector of int values" )
  {
    Vector values INT_VALUES;

    THEN( "Sort function sorts the full contents of vector" )
    {
      csc240::sort( values );
      const Vector results INT_RESULTS;
      REQUIRE( results == values );
    }
  }
}

SCENARIO( "Generic sort can work with custom ranges" )
{
  GIVEN( "A vector of int values" )
  {
    Vector values INT_VALUES;

    auto middle = std::distance( values.begin(), values.end() ) / 2;
    auto end = values.begin();
    std::advance( end, middle );

    csc240::Range<Vector::iterator> range{ values.begin(), std::move( end ) }

    THEN( "Sort function sorts the elements in specified range" )
    {
      csc240::sort( range );

      const std::vector<uint32_t> results INT_RESULTS;
      REQUIRE_FALSE( results == values );

      const std::vector<uint32_t> partial INT_PARTIAL;
      REQUIRE( partial == values );
    }
  }
}

SCENARIO( "Generic sort can work with C-style arrays" )
{
  GIVEN( "A C-array of int values" )
  {
    int32_t values[] INT_VALUES;
    int32_t results[] INT_RESULTS;

    auto begin = std::begin( values );
    csc240::Range<decltype( begin )> range{ std::move( begin ), std::end( values ) };

    THEN( "Sort function sorts the elements of array" )
    {
      csc240::sort( range );
      REQUIRE( std::equal( std::cbegin( values ), std::cend( values ),
        std::cbegin( results ) ) );
    }
  }
}
Polygon.h 

We will modify the original Polygon class and make it generic. We will use a template parameter as a discriminator to help determine the type of the Polygon (rectangle, triangle etc). We will also require as a constructor parameter a function that will calculate the area of the polygon. With these we have avoided the need for inheritance hierarchies and sub-classing.

Note: We have chosen to use a std::function to illustrate its use. We could easily have chosen to use a template parameter that takes a functor as type (which is the technique the standard library generally adopts).

#pragma once

#include <functional>

namespace csc240
{
  using Function = std::function<double( float, float )>;

  template <typename Type>
  class Polygon final
  {
  public:

    Polygon( const Type &type, float width, float height, Function function ) :
      type{ type }, function{ function }, width{ width }, height{ height } {}

    Polygon( const Polygon& ) = delete;
    Polygon& operator= ( const Polygon& ) = delete;

    Polygon( Polygon&& other ) noexcept
    {
      std::swap( type, other.type );
      std::swap( function, other.function );
      std::swap( width, other.width );
      std::swap( height, other.height );
    }

    Polygon& operator= ( Polygon&& other ) noexcept
    {
      std::swap( type, other.type );
      std::swap( function, other.function );
      std::swap( width, other.width );
      std::swap( height, other.height );
      return *this;
    }

    double area() const
    {
      return function( width, height );
    }

    const Type& getType() { return type; }
    const Type& getType() const { return type; }

    float getWidth() { return width; }
    float getWidth() const { return width; }

    float getHeight() { return height; }
    float getHeight() const { return height; }

  private:
    Type type;
    Function function;
    float width;
    float height;
  };

  template <typename T>
  inline std::ostream& operator<< ( std::ostream& stream, const Polygon<T>& polygon )
  {
    stream << polygon.getType() <<
      " - width: " << polygon.getWidth() <<
      ", height: " << polygon.getHeight();
    return stream;
  }

  template <typename T>
  inline bool operator== ( const Polygon<T>& lhs, const Polygon<T>& rhs )
  {
    return ( lhs.getType() == rhs.getType() ) &&
      ( lhs.getWidth() == rhs.getWidth() ) &&
      ( lhs.getHeight() == rhs.getHeight() );
  }

  template <typename T>
  inline bool operator!= ( const Polygon<T>& lhs, const Polygon<T>& rhs )
  {
    return !( lhs == rhs );
  }

  template <typename T>
  inline bool operator< ( const Polygon<T>& lhs, const Polygon<T>& rhs )
  {
    return lhs.area() < rhs.area();
  }
}
Polygon.cpp 

We will test the Polygon template using it to represent a rectangle and triangle. We use a lambda function and a regular function as input parameters when creating our concrete instances of Polygon.

#include "catch.hpp"
#include "Polygon.h"

namespace csc240
{
  auto areaOfTriangle( float width, float height ) -> double
  {
    return width * height / 2.0;
  }
}

using csc240::Function;
using csc240::Polygon;

SCENARIO( "Polygon can represent rectangles" )
{
  GIVEN( "A lambda to compute the area of a rectangle" )
  {
    Function area = [] ( float width, float height ) -> double { return width * height; };

    THEN( "We can create a polygon that represents a rectangle" )
    {
      const std::string type{ "Rectangle" };
      const Polygon<std::string> rectangle{ type, 2.0, 3.0, area };
      REQUIRE( 6.0 == rectangle.area() );
      REQUIRE( type == rectangle.getType() );
    }
  }
}

SCENARIO( "Polygon can represent triangles" )
{
  GIVEN( "A function that computes the area of a triangle" )
  {
    Function area = csc240::areaOfTriangle;

    THEN( "We can create a polygon that represents a triangle" )
    {
      const std::string type{ "Triangle" };
      const Polygon<std::string> triangle{ type, 4.0, 3.0, area };
      REQUIRE( 6.0 == triangle.area() );
      REQUIRE( type == triangle.getType() );
    }
  }
}
factorial.h 

We will implement a recursive factorial function, as well as a generic struct that computes the factorial of a number. We will use the commonly used TMP based struct for computing factorial and observe the performance difference between the two implementations. Note that the TMP based approach is a constant time operation since the value is computed at compile time. This will also illustrate the use of template specialisation (for the special case of 0).

#pragma once
#include <cstdint>

namespace csc240
{
  namespace internal
  {
    inline int64_t factorial( uint32_t number, uint64_t sum )
    {
      if ( number == 1 ) return sum;
      return factorial( number - 1, sum * number );
    }
  }

  inline int64_t factorial( uint32_t number )
  {
    if ( number == 0 ) return 1;
    return internal::factorial( number, 1 );
  }

  template <int N>
  struct Factorial
  {
    enum { value = N * Factorial<N - 1>::value };
  };

  template <>
  struct Factorial<0>
  {
    enum { value = 1 };
  };
}
factorial.cpp 

We will add a simple test that ensures that the two values for factorial are the same. To illustrate the difference in performance, we will compute the factorial in a loop and measure the time it takes to compute the factorial. Play around with different values of input number, and notice how the time to compute factorial increases with the input number for the recursive function, but stays constant for the TMP struct based value.

#include "catch.hpp"
#include "factorial.h"

#include <iostream>
#include <chrono>

SCENARIO( "Compare performance of regular vs TMP factorial functions" )
{
  GIVEN( "A recursive factorial function and a TMP struct" )
  {
    using std::chrono::duration_cast;
    using std::chrono::high_resolution_clock;
    using std::chrono::microseconds;
    constexpr uint32_t number = 125;
    uint64_t functionResult;
    uint64_t tmpResult;

    WHEN( "Time to compute factorial in a loop using function" )
    {
      high_resolution_clock::time_point t1 = high_resolution_clock::now();
      for ( uint8_t i = 0; i < 100; ++i )
      {
        functionResult = csc240::factorial( number );
      }
      high_resolution_clock::time_point t2 = high_resolution_clock::now();

      auto duration = duration_cast<microseconds>( t2 - t1 ).count();
      std::cout << "Time to compute using recursive function: " << duration << std::endl;
    }

    AND_WHEN( "Time to compute factorial in a loop using TMP" )
    {
      high_resolution_clock::time_point t1 = high_resolution_clock::now();
      for ( uint8_t i = 0; i < 100; ++i )
      {
        tmpResult = csc240::Factorial<number>::value;
      }
      high_resolution_clock::time_point t2 = high_resolution_clock::now();

      auto duration = duration_cast<microseconds>( t2 - t1 ).count();
      std::cout << "Time to compute using TMP: " << duration << std::endl;
    }

    THEN( "Returned values are identical" )
    {
      REQUIRE( functionResult == tmpResult );
    }
  }
}