21. Templates

1. Function templates

1.1. Identical algorithms on different data types

Sometimes a program involves several functions that have identical algorithms and differ only in the types of arguments that they receive. One such example is the function max2 that takes two arguments and returns the maximum of the two values.

If we need to apply the function max2 to integers and real numbers, then we would provide two versions.

#include<iostream>
long max2(long a, long b){
   long biggerNum=a;
   if(b>a){biggerNum=b;} 
   return biggerNum;
}
double max2(double a, double b){
   double biggerNum=a;
   if(b>a){biggerNum=b;} 
   return biggerNum;
}
int main(){
   double d1, d2; long l1,l2;
   std::cin>>d1>>d2>>l1>>l2;
   std::cout<<max2(d1,d2)<<"\n";
   std::cout<<max2(l1,l2)<<"\n";
   return 0;
}

1.2. Programs with template functions

To make our source codes shorter, we can write one generic function that works on generic data type GeneralData instead of double and long. The precise syntax is given below

template <typename GeneralData>
GeneralData max2(GeneralData a, GeneralData b){
   GeneralData biggerNum=a;
   if(b>a){biggerNum=b;} 
   return biggerNum;
}

The above function can be implemented instead of multiple versions of the same function that differ only in the type of data. The functions can be now called in two ways:

• First way: Explicit identification of type.

  std::cout<<max2<double>(d1,d2)<<"\n";
  std::cout<<max2<long>(l1,l2)<<"\n";

• Second way: Implicit identification of type. If the compiler is capable of figuring out what is the type of data, then we can omit <double> and <long> from the calls.

  std::cout<<max2(d1,d2)<<"\n";
  std::cout<<max2(l1,l2)<<"\n";

Note: Sometimes the compiler cannot figure out which function to call. Then, the compiler will return an error. This is an example in which the error will be returned:

std::cout<<max2(19,29.11)<<"\n";

#include<iostream>
struct River{
public:
   std::string name;
   double length;
};
struct Rectangle{
public:
   double length;
   double height;
};
   // ??? //
int main(){
   Rectangle a1, a2, a3, bestA;
   River b1, b2, b3, bestB;
   std::cin>>a1.length>>a1.height>>a2.length>>a2.height>>a3.length>>a3.height;
   std::cin>>b1.name>>b1.length>>b2.name>>b2.length>>b3.name>>b3.length;
   bestA=longestOfTheThree<Rectangle>(a1,a2,a3);
   bestB=longestOfTheThree<River>(b1,b2,b3);
   std::cout<<bestA.length<<" "<<bestA.height<<" "<<bestB.name<<" "<<bestB.length<<"\n";
   return 0;
}

Code editor

2. Class templates

2.1. Class declaration

We can also create a generic class in which one (or more) data types are generalized. These general data types can later be replaced with specific classes or types of objects.

Here is an example of a class called ThreeComponents. It has three private attributes first, second, and third that can be of different general types: A, B, or C.

template<typename A, typename B, typename C> 
class ThreeComponents{
private:
   A first; B second; C third;
public:
   void setFirst(const A &);
   void setSecond(const B &);
   void setThird(const C &);
   A getFirst() const;
   B getSecond() const;
   C getThird() const;
};

2.2. Object declaration

We have still not implemented the methods. Before we do so, we will show how the objects will be declared. We will assume that the class was declared as above. We will also assume that methods are implemented (they are not, we will implement them later). Once these two assumptions are made, we can use the above general class for several purposes. We can use the class to store data about people. The two components can be first and last name, while the third component is an id number. The class can also be used to keep data about lakes. The first component can be the name, the second component can be the area, and the third component can be the maximal depth. Here is a code that declares one person and one lake.

ThreeComponents<std::string, std::string, long> person;
person.setFirst("John");
person.setSecond("Smith");
person.setThird(12345);
ThreeComponents<std::string,double,double> lake;
lake.setFirst("Michigan");
lake.setSecond(58030);
lake.setThird(281);

2.3. Implementation of methods

A special syntax has to be used when implementing the methods. We must first specify that we are making the methods for the general class. We need to choose the variables for the general data types. In the case of our class ThreeComponents we will pick the same three variables: A, B, and C for general data types. Instead of the name ThreeComponents we must use ThreeComponents<A,B,C>.

The methods setFirst and getFirst are implemented with the code listed below.

template<typename A, typename B, typename C>
void ThreeComponents<A,B,C>::setFirst(const A& x){first=x;}
template<typename A, typename B, typename C>
A ThreeComponents<A,B,C>::getFirst() const{return first;}

2.4. Complete program

We will now implement the entire class ThreeComponents. In addition, we will create a function printComponents that accepts one object of the class ThreeComponents and prints the attributes.

#include<iostream>
template<typename A, typename B, typename C> 
class ThreeComponents{
private:
   A first; B second; C third;
public:
   void setFirst(const A &);
   void setSecond(const B &);
   void setThird(const C &);
   A getFirst() const;
   B getSecond() const;
   C getThird() const;
};
template<typename A, typename B, typename C>
void ThreeComponents<A,B,C>::setFirst(const A& x){first=x;}
template<typename A, typename B, typename C>
void ThreeComponents<A,B,C>::setSecond(const B& x){second=x;}
template<typename A, typename B, typename C>
void ThreeComponents<A,B,C>::setThird(const C& x){third=x;}
template<typename A, typename B, typename C>
A ThreeComponents<A,B,C>::getFirst() const{return first;} 
template<typename A, typename B, typename C>
B ThreeComponents<A,B,C>::getSecond() const{return second;} 
template<typename A, typename B, typename C>
C ThreeComponents<A,B,C>::getThird() const{return third;} 
template<typename A, typename B, typename C>
void printComponents(const ThreeComponents<A,B,C>& t){
   std::cout<<t.getFirst()<<" "<<t.getSecond()<<" "<<t.getThird()<<"\n";
}
int main(){
   ThreeComponents<std::string, std::string, long> person;
   person.setFirst("John");
   person.setSecond("Smith");
   person.setThird(12345);
   ThreeComponents<std::string,double,double> lake;
   lake.setFirst("Michigan");
   lake.setSecond(58030);
   lake.setThird(281);
   printComponents(person);
   printComponents(lake);
   return 0;
}

3. Typename enforcement

C++ compilers need additional guidance when working with certain iterators. This happens when the iterator has to be declared for a data structure that is built as a template. We will explain this with an example.

3.1. First attempt that fails

This first attempt will have correct idea, but will return a compiler error. Then we will explain what is going on and provide the solution to the problem.

The idea is to position an iterator to the beginning of the set. The beginning of the set is the smallest element. Then we will increment the iterator and return the obtained object.

#include<iostream>
#include<set>
template<typename T> 
T secondSmallest(const std::set<T>& s){
  T res;
  if(s.size()<2){return res;}
  std::set<T>::const_iterator it;
  it=s.begin();
  ++it;
  return *it;
}
int main(){
   std::set<std::string> names; 
   names.insert("Bob"); names.insert("Alice"); names.insert("Carl"); names.insert("Danny");
   std::cout<<secondSmallest(names)<<"\n";
   std::set<long> numbers;
   numbers.insert(900); numbers.insert(700); numbers.insert(800); numbers.insert(1000);
   std::cout<<secondSmallest(numbers)<<"\n";
   return 0;
}

The compiler will return an error. It will look something like:

error: need ‘typename’ before ‘std::set<T>::const_iterator’ because ‘std::set<T>’ is a dependent scope

3.2. Second attempt that succeeds

There is one command that can have too possible meanings. The compiler does not know which of the two meanings the programmer had in mind. The offending line is:

std::set<T>::const_iterator

• First meaning: The programmer wants to declare an object of the type std::set<T>::const_iterator. This is actually what we wanted to do in the program.
• Second meaning: The programmer wants to make an implementation of the method for the class std::set<T> and the method will be called const_iterator.

We want to clarify to the compiler that we want the command std::set<T>::const_iterator to have the first of the possible two meanings. We want to specify that we are using the command to declare an object. In other words, we want the compiler to treat std::set<T>::const_iterator as a data type. This is achieved by placing the word typename before the command.

There is only one word that is needs to be added to make the correct code. The improved program is:

#include<iostream>
#include<set>
template<typename T> 
T secondSmallest(const std::set<T>& s){
  T res;
  if(s.size()<2){return res;}
  typename std::set<T>::const_iterator it;
  it=s.begin();
  ++it;
  return *it;
}
int main(){
   std::set<std::string> names; 
   names.insert("Bob"); names.insert("Alice"); names.insert("Carl"); names.insert("Danny");
   std::cout<<secondSmallest(names)<<"\n";
   std::set<long> numbers;
   numbers.insert(900); numbers.insert(700); numbers.insert(800); numbers.insert(1000);
   std::cout<<secondSmallest(numbers)<<"\n";
   return 0;
}

#include<iostream>
#include<set>
template<typename T>
T kthLargest(const std::set<T> & a, long k){
  // ??? //
}
int main(){
   std::set<long> numbers; std::set<std::string> words;
   long n; std::string w;
   std::cin>>n;
   while(n>0){numbers.insert(n);std::cin>>n;}
   std::cin>>w;
   while(w!="end"){words.insert(w);std::cin>>w;}
   long k; std::cin>>k;
   std::cout<<kthLargest<long>(numbers,k)<<" "<<kthLargest<std::string>(words,k)<<"\n";
   return 0;
}

Code editor