[RA] Ch17 Templates

Reading Assignment: All of Programming Chapter 17 Templates

C++ provide us parametric polymorphism. Polymorphism, which literally means “many shapes” or “many forms”, is the ability of the same code to operate on different types. This ability to operate on multiple types reduces code duplication, by allowing the same piece of code to be re-used across the different types it can operate on. C++ provides parametric polymorphism through templates.

Templated Functions

The template parameters have a scope of the entire templated function. For example, we might write our function which returns a pointer to the largest element in an array as a template as follows:

template <typename T>
T* arrMax(T* array, size_t n){
  if(n == 0){
    return NULL;
  }
  T* ans = &array[0];
  for(size_t i = 1; i < n; i++){
    if(array[i] > *ans){
      ans = &array[i];
    }
  }
  return ans;
}

Templates may take multiple parameters, and their parameters may be “normal” types, such as int. For example, it would be perfectly valid to write a templated function that looked generally like this:

template<typename T, typename C, int N>
int someFunction(const T &t, S s){
    ...
}

Instantiating Templated Functions

To instantiate a template, we write the name of the templated functions, followed by the arguments we wish to pass inside of the angle brackets. The result is a function, which we then call as we normally would:

1
2
3

int *m1 = arrMax<int>(myIntArray, nIntElements);
string *m2 = arrMax<string>(myStringArray, nStringElements);
int x = someFunction<int *, double, 42>(m1, 3.14);

Whenever you instantiate a template, the C++ compiler creates a template specialization-a normal function derived from a template for particular values of its parameters-if one does not already exist.

Templated Classes

In much the same way with templated functions, it also allows templated classes.

template<typename T>
class Array{
private:
  T* data;
  size_t size;
public:
  Array(): data(NULL), size(0){}
  Array(size_t n): data(new T[n]()), size(n){}
  Array(const Array &rhs) : data(NULL), size(rhs.size){
    (*this) = rhs;
  }
  ~Array(){
    delete[] data;
  }
  Array & operator=(const Array &rhs){
    if(this != &rhs){
      T * temp = new T[rhs.size];
      for(int i = 0; i < rhs.size(); i++){
        temp[i] = rhs.data[i];
      }  
      delete[] data;
      data = temp;
      size = rhs.size;
    }
    return *this;
  }
  T & operator[](unsigned ind){
    return data[ind];
  }
  const T& operator[](unsigned ind) const {
    return data[ind];
  }
  size_t getSize() const{
    return size;
  }
}

Templates as Template Parameters

Template parameters can also be another template.

template<typename T, template<typename>class Container>
class Something{
private:
  Container<T> data;
};

Here, Something is a template whose second parameter is another template. Specifically, one that takes one type as a parameter-such as the Array template we just made.

With the Array template we wrote above, we could instantiate this templated class like this:

1	Something<int, Array> x;

This instantiation will create a specialization whose data field is an Array<int>. If we always wanted to use an Array to store our data, we could just write that in our class-so why would we want to parameterize this template over this templated class? This is just another example of abstraction-we decouple the specific implementation for how the Container stores its data from the interface required to do so. Our Something template will work with any templated class which conforms to the interface it expects. We then have greater flexibility in how we use it later.

Template Rules

Template Definitions Must Be “Visible” at Instantiations

The actual definition of the templated function or class must be “visible” to the compiler at the point where the template is instantiated. The compiler cannot just generate a call to it and find it in an object file.

Template Arguments Must Be Compile-time Constants

The arguments that are passed to a template must be compile-time constants-they may be an expression, but the compiler must be able to directly evaluate that expression to a constant. For example, if f is a function templated over an int, the following is illegal:

1
2
3

for(int i = 0; i < 4; i++){
  x += f<i>x; // illegal: i is not a compile time constant
}

However, this is legal code:

x += f<0>(x);
x += f<1>(x);
x += f<2>(x);
x += f<3>(x);

The compiler must create a specialization for the argument values given.

Templates Are Only Type-checked When Specialized

In C++, a template is only type checked when it is specialized. That is, you can write a template which can only legally be instantiated with some types but not others.

For example,

template <typename T>
T* arrMax(T* array, size_t n){
  if(n == 0){
    return NULL;
  }
  T* ans = &array[0];
  for(size_t i = 1; i < n; i++){
    if(array[i] > *ans){
      ans = &array[i];
    }
  }
  return ans;
}

It is legal only for Ts where the > operator is defined to compare two Ts, and return a bool.

Multiple Close Brackets Must Be Separated by Whitespace

1 2	std::vector<std::pair<int, std::string>> myVector; //illegal std::vector<std::pair<int, std::string> > myVector; //legal

Dependent Type Names Require “typename”

If T is a template parameter which names a type, then the compiler has a difficult time determining if T::x names a type or a variable. Likewise, Something<T>::x is difficult to figure out. In these two situations, we call x a dependent name, as its interpretation depends on what T is.

Whenever you use a dependent name for a type, you need to explicitly tell the compiler that it names a type by placing the typename keyword before the name of the type. For example:

template<typename T>
class Something{
private:
  typename T::t oneField;
  typename anotherTemplate<T>::x two Filed;
public:
  typename T::t someFunction(typename T::t x){
    typename T::t someVar;
    // some code.
  }
};

There are also circumstances where a dependent name has a templated class or function inside of it, and the compiler must explicitly be told that name refers to a template to disambiguate the < which enclose the templates’s arguments from the less-than operator.

You Can Provide an Explicit Specialization

You can explicitly write a specialization for a template-providing specific behavior for particular values of the template arguments.

Template Parameters for Functions(But not Classes) May Be Inferred

When you use a templated function, you can omit the angle brackets and template arguments in cases where the compiler can infer them, that is, if the compiler can guess what to use based on other information, such as the types of the parameters to the function in question. However, we recommend against this practice. It is much better to be explicit, and make sure you and the compiler both agree on what types are being used.

The Standard Template Library

The std::vector Templated Classes

A vector is similar to an array in that it stores elements of some other type-namely, the type that is its template parameter, T. You should #include<vector> if you want to use this class.

The std::pair Templated Class

std::pair class is templated over two types, T1 and T2. All the pair class does is provide a way to pair two objects-one of type T1 and one of type T2-together into a single object. The elements of the pair can then be accessed via the public fields first and second.

Iterators

The approach that C++ takes to resolve the tension between good abstraction and high performance is to provide an abstraction called an iterator. An iterator is a class which encapsulates the state of the internal traversal while providing an implementation-independent interface to external code.

std::vector<int>::iterator it = myVector.begin();
while(it != myVector.end()){
  std::cout << *it << "\n";
  ++it;
}

You may wonder why we have written ++it rather than more familiar it++. Although this distinction seems minor, the postfix increment requires the operator to make a copy of the original object, perform the increment, then return the copy of the object. In general, you should use prefix increment operator whenever the increment is on an object type to avoid these unnecessary copies and destructions.

We have iterator to iterate the objects, and we also have const_iterator to iterate objects with const.

Whenever a modification occurs, an iterator may be invalidated by that modification-use of an invalidated iterator is incorrect.

Algorithms from STL

You should #include <algorithm>. An object with “function call” behavior is referred to as a function object.

Overloading the function call operator on a class allows the programmer to place parenthesis with arguments after an instance of that class in a way that looks like a function call-resulting in a call to the overloaded operator. A object with “function call” behavior is refered to as a function object.

class OrderIgnoreCase{
public:
  bool operator()(const std::string &s1, const std::string &s2) const{
    for(size_t i = 0; i < s1.size() && i < s2.size(); i++){
        char c1 = tolower(s1[i]);
        char c2 = tolower(s2[i]);
        if(c1 != c2) return c1 < c2;
    }
    return s1.size() < s2.size();
  }
};

In this example, we overload the function call operator to take two const std::string &s which are the strings to compare for ordering. The syntax may seem a bit odd, however, nothing is actually unusual-the name of the operator is just operator(), which is then followed by the parameter list in parenthesis. The function then compares the strings ignoring the case of each letter.

We could then use this class to with the min algorithm to find the minimum of two strings, ignore case:

1	std::min<std::string, OrderIgnoreCase>(stri1, str2, OrderIgnoreCase());