Chapter 5
Templates and The Standard Library

Kurt Nørmark
Department of Computer Science, Aalborg University


Abstract
Previous lecture Next lecture
Index References Contents
...


Templates

Templates
Slide Annotated slide Contents Index
References 

Templates in C++ provide for compile-time parametrization of functions and classes

Templates correspond to generic types and generic methods in Java and C#

  • Template parameters

    • Types

    • Values of template types

    • Constants of integer types

    • Pointer to an object, a pointer to function, or pointer to a member

    • It is not possible to pass, doubles, floats, or string constants as a template arguments

  • Template specialization

    • It is possible to define several specializations (variants) of a template distiguished by a 'formal type parameter pattern'

    • Can be used to provide a shared template for all pointer types

    • Both for class and function templates

The C++ template facility is macros that look like classes [Anders Hejlsberg].

Templates versus generics in Java, C# and C++
Slide Annotated slide Contents Index
References 

Templates in C++ can be compared with generics in Java and C#

  • Java

    • Type erasure: type parameters are compiled away.

      • Problems with reflection - cannot reestablish actual type parameters

  • C#

    • Reflection with generic types is possible

    • Support of constraints on formal parameter types: where clauses

      • where class;   where struct;   where new();   where C;   where C, I

    • When value types are used as actual type parameters

      • Separate instantiations are generated

  • C++

    • Template specialization, and partial specialization

      • Allow alternative implementation for certain template parameters

      • To avoid code bloat in some situations

        • Containers of pointers share their implementation     (§13.5)

    • Powerful compile time calcuations - Turing complete

    • Templates cannot be compiled as such     (§13.2.5)

      • The instantiations are compiled

      • Only relatively superficial compiler check of the template - before any instantiation

    • Relies on compile-time duck typing

Example - Point<C>
Slide Annotated slide Contents Index
References 

We make a type parameterized Point - class Point<C>

Program: A type parameterized variant of class Point - point.h.
template<class C>class Point {
private: 
  C x, y;

public:
  Point(C, C);
  Point();
  C getx () const;
  C gety () const;
  Point<C>& move(C, C);
  double distance_to(Point);
};

template<class C>  std::ostream& operator<< (std::ostream&, const Point<C>&);

Program: The implementation of the template class Point - point.cc.
#include <cmath>
#include <iostream>
#include "point.h"

template<class C> Point<C>::Point(C x_coord, C y_coord):
   x(x_coord), y(y_coord){
}

template<class C> Point<C>::Point(): x(0.0), y(0.0){
}

template<class C> C Point<C>::getx () const{
  return x;
}

template<class C> C Point<C>::gety () const{
  return y;
}

template<class C> Point<C>& Point<C>::move(C dx, C dy){
  x += dx; y += dy;  // Implicitly assume that + applies to C values 
  return *this;
}

template<class C> double Point<C>::distance_to(Point p){
  return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
}


template<class C> std::ostream& operator<< 
                        (std::ostream& s, const Point<C>& p){
  return s << "(" << p.getx() << "," << p.gety() << ")" ;
}

Program: A program that illustrate template instantiation.
#include <iostream>
#include <string>
#include "point.cc"  // Notice inclusion of the cc file, in order to 
                     // instantiate the template for int and double.
                     // Else lots of linker errors will occur.
                     // This treats templates in the same way as inline functions.
                     // The C++ Programming Language, 3ed, page 350-351.

int main(){
  Point<double> pd1,
                pd2(1,2);

  Point<int>    pi1,
                pi2(3,4);

  pd2.move(1,1);
  pi2.move(1,1),

  std::cout << "pd2: " << pd2 << std::endl;      // (2,3)
  std::cout << "pi2: " << pi2 << std::endl;      // (4,5)
}

  • Lessons learned

    • The definition of member functions in the template class becomes more complex

      • See the file point.cc

    • Template instantiation first occurs when Point<int> and Point<double> is encoutered

      • For this reason, point.cc must be included in prog.cc instead of (as usual) point.h

Exercise 5.2. A template class with friendsArrange that operator<< becomes a friend of the template class Point<C>. It may be useful to consult §C.13.2 page 854-855 in The C++ Programming Language.

Class templates in C++
Slide Annotated slide Contents Index
References 

In many ways similar to generic classes in C# and Java

  • Template classes versus classes

    • A template can be used to create classes by means of template instantiation

  • Template instantiation

    • Supplying actual template parameters

    • Template parameters to classes must be supplied explicitly

    • Each instantiation creates a class which has the same status as a hand crafted class

  • "The generated classes and functions are perfectly ordinary classes that obey all the usual rules for classes"

    • "... a powerful way of generating code"

    • "... a certain amount of caution is in order to avoid flooing memory with almost identical [...] definitions"

    • [Stoustrup page 331]

  • Type parameters are not related by inheritance

    • "There are no requirements that different arguments for the same template parameter should be related by inheritance", §13.2.1

    • No constraints on formal type parameters as in C#

Example - Point<C,dim,default_value>
Slide Annotated slide Contents Index
References 

We make a Point class parameterized with a type C, an integer dimension, and some default value in C

All template parameters are defaulted

Program: A type parameterized variant of class Point - point.h.
// Multi dimensional point. The dimension and a default value is supplied as a template parameter.
// Defaults are provided for all three template parameters.

#include <vector>

template<class C, int dim, C def> class Point;
template<class C, int dim, C def> std::ostream& operator<<
                             (std::ostream& s, const Point<C,dim,def>& p);

class PointDimProblem{};

template<class C = int, int dim = 3, C def = 0>class Point {
private: 
  C values[dim];            // An array of C values

public:
  Point();
  C get (int i) const;
  Point<C, dim, def>& move(const std::vector<int>&);
  double distance_to(Point<C, dim, def>);
  friend  std::ostream& operator<< <>
                             (std::ostream&, const Point<C, dim, def>&);
};

Program: The implementation of the template class Point - point.cc.
// The implementation of the Point template class.

#include <cmath>
#include <iostream>
#include "point.h"

// Default contructor
template<class C, int dim, C def> Point<C, dim, def>::Point() {
  for (int i = 0; i < dim; i++)
    values[i] = def;
}

// The get method access dimension i of the point
template<class C, int dim, C def> C Point<C, dim, def>::get(int i) const{
  if (i >= 1 && i <= dim)
    return values[i-1];
  else 
    throw PointDimProblem();
}

// Move the point by means of a vector of int.
template<class C, int dim, C def> Point<C, dim, def>&    // deltas is a vector<int>
                          Point<C, dim, def>::move(const std::vector<int>& deltas){  
  for (int i = 0; i < dim; i++)                                               
    values[i] += deltas[i];
  return *this;
}

// Distance to method - Using some funny norm:
template<class C, int dim, C def> double Point<C, dim, def>::distance_to(Point p){    
  double temp = 0.0;
  for (int i = 0; i < dim; i++)
    temp += std::abs(values[i] - p.values[i]);

  return temp;
}


// The << operator for points.
template<class C, int dim, C def> std::ostream& operator<<
                          (std::ostream& s, const Point<C, dim, def>& p){
  s << "(";
  for(int i = 0; i < dim-1; i++)
    s << p.values[i] << ", ";
  s << p.values[dim-1];
  s << ")" << std::endl;

  return s;
}

Program: A program that illustrate the template instantiation.
// A program that illustrates how to use the parametered Point teplate class

#include <iostream>
#include <string>
#include <vector>
#include "point.cc"           // Inclusion of the .cc (.cpp) file, not just .h file

const int Dim = 10;

int main(){
  using namespace std;

  Point<long int> pli1;       // Default dimension and default default value.

  Point<int,Dim,7> pi1, pi2;  // double is illegal as type parameter in this context,
                              // because non-integer constants are not allowed!
  Point<char, 4, 65> pc1;
  Point<> pi3;                // All three parameters are defaulted.

  // Diplacement int vectors:
  vector<int> displacement1;
  displacement1.push_back(1); displacement1.push_back(2); displacement1.push_back(3);

  vector<int> displacement2;
  for(int i = 0; i < Dim; i++)
    displacement2.push_back(i*2);

  // Move points
  pli1.move(displacement1);
  pi1.move(displacement2);
  pc1.move(displacement2);
  pi3.move(displacement1);

  // Print points:
  cout << "pli1: " << pli1 << std::endl;    // (1, 2, 3)
  cout << "pi1: " << pi1 << std::endl;      // (7, 9, 11, 13, 15, 17, 19, 21, 23, 25)
  cout << "pc1: " << pc1 << std::endl;      // (A, C, E, G)
  cout << "pi3: " << pi3 << std::endl;      // (1, 2, 3)

  cout << "|pi1 - pi2| = " << pi1.distance_to(pi2) << endl;  // 90
}

  • Lessons learned

    • It is only possible to pass template constant parameters of integer type

      • The compiler disallows a constant of type double

    • The details in point.cc becomes even more challenging

    • Tricky to deal with the overloading of operator<< as a friend and template function

      • The compiler helps a bit...

Function templates
Slide Annotated slide Contents Index
References 

Functions outside classes can also be defined as templates

Program: The template function compare, and various uses of it.
#include <iostream>
#include <string>
#include "point.h"

class ComparsionProblem{};

template<typename T> int compare(const T &v1, const T &v2){
  if (v1 < v2) 
    return -1;
  else if (!(v1 < v2) && !(v2 < v1))  // better than v1 == v2
    return 0;
  else if (v2 < v1)                   // better than v1 > v2
    return 1;
  else 
    throw ComparsionProblem();
}

int main(){
  using namespace std;

  // Comparing int, infers the type automatically:
  cout << compare(1,2) << endl;             // -1
  cout << compare(1,1) << endl;             //  0
  cout << compare(2,1) << endl;             //  1
  cout << endl;

  // Passing type parameteter explicitly:
  cout << compare<int>(1,2) << endl;        // -1
  cout << compare<int>(1,1) << endl;        //  0
  cout << compare<int>(2,1) << endl;        //  1
  cout << endl;

  string s1 = "abe",
         s2 = "katten",
         s3 = "abe";

  // Comparing strings:
  cout << compare(s1,s2) << endl;           // -1
  cout << compare(s2,s1) << endl;           //  1
  cout << compare(s1,s3) << endl << endl;   //  0
  cout << endl;

  // Comparing C-style strings:
  cout << compare("ABE","KAT") << endl;     //  1. Wrong. Why? Because we compare pointers...
  cout << compare("KAT","ABE") << endl;     // -1. Wrong.
  cout << compare("kat","katten") << endl;  // error: no matching function for call to 
                                            // compare(const char [4], const char [7])

  // Comparing Points (without having defined < on Point):
  Point p1(1,2), p2(3,4);                   
  int i = compare(p1, p2);                  // error: no match for operator< in v2 < v1
                                            // error: no match for operator< in v1 < v2
                                            // error: no match for operator< in v2 < v1

}

We make a version of class Point with an overloaded < operator

Program: Class Point with comparison operator friends.
// Preparing for definition of operator< in class Point.

class Point {
private: 
  double x, y;

public:
  Point(double, double);
  Point();
  double getx () const;
  double gety () const;
  void move(double, double);
  double distance_to(Point);

  friend bool operator<(const Point&, const Point&);
};

std::ostream& operator<<(std::ostream&, const Point&);

Program: The implementation of class Point.
#include <cmath>
#include <iostream>
#include "point.h"

Point::Point(double x_coord, double y_coord): x(x_coord), y(y_coord){
}

Point::Point(): x(0.0), y(0.0){
}

double Point::getx () const{
  return x;
}

double Point::gety () const{
  return y;
}

void Point::move(double dx, double dy){
    x += dx; y += dy;
}

double Point::distance_to(Point p){
    return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
}

std::ostream& operator<<(std::ostream& s, const Point& p){
  return s << "(" << p.getx() << "," << p.gety() << ")" ;
}

// Implementation of comparisons that only take the x-coordinate into account.

bool operator<(const Point& p1, const Point& p2){
  return (p1.x < p2.x);
}

Program: The template function compare used for Point comparison.
#include <iostream>
#include <string>
#include "point.h"

class ComparsionProblem{};

template<typename T> int compare(const T &v1, const T &v2){
  if (v1 < v2) 
    return -1;
  else if (!(v1 < v2) && !(v2 < v1)) 
    return 0;
  else if (v2 < v1)                  
    return 1;
  else 
    throw ComparsionProblem();
}

int main(){
  using namespace std;


  Point p1(1,2), p2(3,4);                   
  cout << compare(p1, p1) << endl;          // 0
  cout << compare(p1, p2) << endl;          // -1
  cout << compare(p2, p1) << endl;          // 1
}

Inappropriate actual type parameters are simply discovered by the compiler

Appropriateness is not expressed by inheritance relationships

Type parameter may be deduced automatically in function templates

Policies with Templates
Slide Annotated slide Contents Index
References 

A type parameter can be used to parameterize a class or function with a class that represent a given policy

For instance a set of functions that compare data in a certain way

Reference
  • The C++ Programming Language: Page 338

  • Why use templates for policies

    • As an alternative to a function parameter, or to an instance of a class with virtual functions

    • Use of templates will typically give more efficient programs

      • Compile time substitutions

See details in §13.4 in The C++ Programming Language

Example of Policies with Templates
Slide Annotated slide Contents Index
References 

I parameterize class Point with a 'policy for distance and comparison'

In the real world it seems more reasonable to parameterize functions - rather than classes - with policies

Program: The Point class definition - a template - policy parameterized.
template <typename N> class Point {
private: 
  double x, y;

public:
  Point(double, double);
  Point();
  double getx () const;
  double gety () const;

  double distance_to(Point<N>);
  bool less_than(const Point<N>&);
};

template <typename N> std::ostream& operator<<(std::ostream&, const Point<N>&);

Program: Member functions in class Point.
#include <cmath>
#include <iostream>
#include "point.h"

template<typename N>Point<N>::Point(double x_coord, double y_coord): x(x_coord), y(y_coord){
}

template<typename N>Point<N>::Point(): x(0.0), y(0.0){
}

template<typename N> double Point<N>::getx () const{
  return x;
}

template<typename N> double Point<N>::gety () const{
  return y;
}

template<typename N> double Point<N>::distance_to(Point<N> p){
    return N::distance_to(*this,p);
}

template<typename N> bool Point<N>::less_than(const Point<N>& p){
    return N::less_than(*this,p);
}

template<typename N> std::ostream& operator<<(std::ostream& s, const Point<N>& p){
  return s << "(" << p.getx() << "," << p.gety() << ")" ;
}

Program: Four different policy classes - with type parameterized static methods.
#include <cmath>

struct FixedNorm{
  template<typename C> static bool less_than(const C& a, const C& b){
    return false;
  }

  template<typename C> static double distance_to(const C& a, const C& b){
    return 7.0;
  }
};



struct HorizontalNorm{
  template<typename C> static bool less_than(const C& a, const C& b){
    return a.getx() < b.getx();
  }

  template<typename C> static double distance_to(const C& a, const C& b){
    return fabs(a.getx() - b.getx());
  }
};



struct VerticalNorm{
  template<typename C> static bool less_than(const C& a, const C& b){
    return a.gety() < b.gety();
  }

  template<typename C> static double distance_to(const C& a, const C& b){
    return fabs(a.gety() - b.gety());
  }
};



template<typename T>double square(T a){
  return a*a;
}

struct Norm{
  template<typename C> static bool less_than(const C& a, const C& b){
    return (a.getx() < b.getx()) && (a.gety() < b.gety());
  }

  template<typename C> static double distance_to(const C& a, const C& b){
    return sqrt(square(a.getx() - b.getx()) + square(a.gety() - b.gety()));
  }
};

Program: A sample application.
// Ilustration of class point parameterized with a "policy type"

#include <iostream>
#include <string>
#include "point.cc"
#include "norms.cc"

template<typename C>void do_tell_about(C x, C y){
  double dist = x.distance_to(y);
  std::cout << "Distance: " << dist << std::endl; 
  std::cout << "Less than? " << (x.less_than(y) ? "true" : "false") << std::endl << std::endl;
}

int main(){
  using namespace std;

  double dist;
  Point<FixedNorm> p1(1,2),          // Here we parameterize p1 and p2 with a bundle of functions from Fixed form. 
                   p2(4,11);
  do_tell_about(p1,p2);

  Point<HorizontalNorm> p3(1,2),     // Ditto p3 and p4 with HorizontalNorm
                        p4(4,11);
  do_tell_about(p3,p4);

  Point<VerticalNorm> p5(1,2),       // Ditto p5 and p6 with VerticalNorm
                      p6(4,11);
  do_tell_about(p5,p6);

  Point<Norm> p7(1,2),               // Ditto p7 and p8 with Norm
              p8(4,11);
  do_tell_about(p7,p8);
}

Below we parameterize individual functions with a policy

Program: The Point class definition - not a template in this version.
// Another variant of the example - now parameterizing non-member Point functions

#ifndef POINT_H
#define POINT_H

#include <iostream>


class Point {
private: 
  double x, y;

public:
  Point(double, double);
  Point();
  double getx () const;
  double gety () const;

};

std::ostream& operator<<(std::ostream&, const Point&);

#endif // POINT_H

Program: Member functions in class Point - not essential to this example.
// Not particularly relevant to this example.

#include <cmath>
#include <iostream>
#include "point.h"

Point::Point(double x_coord, double y_coord): x(x_coord), y(y_coord){
}

Point::Point(): x(0.0), y(0.0){
}

double Point::getx () const{
  return x;
}

double Point::gety () const{
  return y;
}


std::ostream& operator<<(std::ostream& s, const Point& p){
  return s << "(" << p.getx() << "," << p.gety() << ")" ;
}

Program: Four different policy classes - with type parameterized static methods.
// Four different Point policies - the static methods are now specific to class Point.

#include <cmath>
#include "Point.h"

struct FixedNorm{
  static bool less_than(const Point& a, const Point& b){
    return false;
  }

  static double distance_to(const Point& a, const Point& b){
    return 7.0;
  }
};


struct HorizontalNorm{
  static bool less_than(const Point& a, const Point& b){
    return a.getx() < b.getx();
  }

  static double distance_to(const Point& a, const Point& b){
    return fabs(a.getx() - b.getx());
  }
};


struct VerticalNorm{
  static bool less_than(const Point& a, const Point& b){
    return a.gety() < b.gety();
  }

  static double distance_to(const Point& a, const Point& b){
    return fabs(a.gety() - b.gety());
  }
};


template<typename T>double square(T a){
  return a*a;
}

struct Norm{
 static bool less_than(const Point& a, const Point& b){
    return (a.getx() < b.getx()) && (a.gety() < b.gety());
  }

 static double distance_to(const Point& a, const Point& b){
    return sqrt(square(a.getx() - b.getx()) + square(a.gety() - b.gety()));
  }
};

Program: A sample application - together with policy parameterized functions.
// Parameterizing individual functions with a policy.

#include <iostream>
#include <string>
#include "point.h"
#include "norms.cc"

// Generic distance_to and less_than functions: 
template<typename N> double distance_to(const Point& p, const Point& q){
  return N::distance_to(p,q);
}

template<typename N> bool less_than(const Point& p, const Point& q){
    return N::less_than(p,q);
}

int main(){
  using namespace std;
  double dist;

  Point p1(1,2),
        p2(4,11);
  dist = distance_to<HorizontalNorm>(p1,p2);   // Parameterizing distance_to with a
  cout << "Distance: " << dist << endl;        // ...  bundle of two functions from HorizontalNorm
  cout << "Less than? " << (less_than<HorizontalNorm>(p1,p2) ? "true" : "false") << endl << endl;   // Ditto less_than

  Point p3(1,2),
        p4(4,11);
  dist = distance_to<Norm>(p1,p2);
  cout << "Distance: " << dist << endl; 
  cout << "Less than? " << (less_than<Norm>(p1,p2) ? "true" : "false") << endl << endl;

}

Template Specialization
Slide Annotated slide Contents Index
References 

It is possible to provide a special version of a template for a particular type of parameter

Template specialization can be used for both class templates and function templates

Reference
  • The C++ Programming Language: Page 341

  • Class template specialization

    • Can be used to provide a single and shared implementation for all pointer types

    • Example: vector<C> is specialized to vector<C*>

    • Details in §13.5 in The C++ Programming Language

Reference

Function templates can also be specialized

Example - Specialization of Point<C> to Point<char>
Slide Annotated slide Contents Index
References 

We show show how to specialize Point<C> to Point<char>

This example solely demonstrates some technicalities of class template specialization

Program: The general class template Point followed by the specialized one.
// First the general Point template class.

template<class C> class Point;
template<class C> std::ostream& operator<<(std::ostream& s, const Point<C>& p);

template<class C>class Point {
private: 
  C x, y;

public:
  Point(C, C);
  Point();
  C getx () const;
  C gety () const;
  Point<C>& move(C, C);
  double distance_to(Point);
  friend  std::ostream& operator<< <>(std::ostream&, const Point<C>&);
};

// A funny specialization for Point<char>. All details are inlined in this version.
template<>class Point <char>{
private: 
  char x, y;
public:
  Point(char c1, char c2): x(c1), y(c2) {}
  Point(): x('a'), y('z'){}
  char getx () const {return x;}
  char gety () const {return y;}
  Point<char>& move(char c1, char c2){x = c1; y = c2; return *this;}
  double distance_to(Point){return 7.0;}
  friend  std::ostream& operator<< <>(std::ostream&, const Point<char>&);
};

Program: The implementation of the template class Point - point.cc - nothing interesting here.
// The general implementation of the Point template class.

#include <cmath>
#include <iostream>
#include "point.h"

template<class C> Point<C>::Point(C x_coord, C y_coord):
   x(x_coord), y(y_coord){
}

template<class C> Point<C>::Point(): x(C()), y(C()){    // int() is 0 ...
}

template<class C> C Point<C>::getx () const{
  return x;
}

template<class C> C Point<C>::gety () const{
  return y;
}

template<class C> Point<C>& Point<C>::move(C dx, C dy){
    x += dx; y += dy; 
    return *this;
}

template<class C> double Point<C>::distance_to(Point p){
    return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
}


template<class C> std::ostream& operator<<
                          (std::ostream& s, const Point<C>& p){
  return s << "(" << p.x << "," << p.y << ")" ;
}

Program: A program that illustrate the instantiation of both the general and specialized template classes.
// A program that illustrate use of both the general Point template class
// and the specialized Point template class.

#include <iostream>
#include <string>
#include "point.cc"           
                              
int main(){
  Point<double> pd1,
                pd2(1,2);

  Point<int>    pi1,
                pi2(3,4);

  Point<char>   pc1,           // Using the template specialization.
                               // The strange default constructor reveals the
                               // use of the template specialization.
                pc2(97, 98);   // Char 97 = 'a'

  pd2.move(1,1);
  pi2.move(1,1);
  pc2.move('r', 's');          // Absolute moving!

  std::cout << "pd2: " << pd2 << std::endl;      // (2,3)
  std::cout << "pi2: " << pi2 << std::endl;      // (4,5)
  std::cout << "pc1: " << pc1 << std::endl;      // (a,z)  !!
  std::cout << "pc2: " << pc2 << std::endl;      // (r,s)

  std::cout << "|pd1 - pd2| = " << pd1.distance_to(pd2) << std::endl;    // 3.60555
  std::cout << "|pi1 - pi2| = " << pi1.distance_to(pi2) << std::endl;    // 6.40312
  std::cout << "|pc1 - pc2| = " << pc1.distance_to(pc2) << std::endl;    // 7

// std::cout << "|pd1 - pi2| = " << pd1.distance_to(pi2) << std::endl;    // Error: No matching function for call 
                                                                          // to 'Point<double>::distance_to(Point<int>&)' 
}

Specialization of class templates - complete and partial
Slide Annotated slide Contents Index
References 

We illustrate complete and partial specialization of a class template A

Program: Full and partial specializations of a class template A.
#include <iostream>
#include <string>

template <typename S, typename T> class A{               // Template class
  //  ...
};

template<> class A <int, std::string> {                  // Complete specialization to S = int, T = string
  //  
};

template<typename S, typename T> class A <S*, T*> {      // Partial Specialization to pointers
  //
};

template<typename T> class A <T, T> {                    // Partial specialization: T and S are the same types
  //
};



int main(){
  A<double,bool> a1;                                     // Use of A<S,T>
  A<int,std::string> a2;                                 // Use of A<int,string>
  A<double*,std::string*> a3;                            // Use of A<T*,S*>
  A<double,double> a4;                                   // Use of A<T,T>
}

Compile time computations with template specialization
Slide Annotated slide Contents Index
References 

We show examples of simple recursive functions which can be called and evaluated by the compiler

Program: The factorial function - from Wikipedia.
// Factorial template function from Wikipedia.

#include <iostream>
#include <string>

// The general case:
template <int N> struct Factorial {
  static const int value = N * Factorial<N - 1>::value;
};
 
// The base case of the recursion, via template specialization:
template <>
struct Factorial<0> {
  static const int value = 1;
};

int main(){
  Factorial<5> facBox;
  std::cout << facBox.value << std::endl;           // 120
  std::cout << Factorial<10>::value << std::endl;   // 3628800
}

Program: The power function on integer type arguments.
// The power function on integer type arguments.

#include <iostream>

// The general case:
template <unsigned int N, unsigned int P> struct Power{   
  static const unsigned int value = N * Power<N,P-1>::value;
};
 
// The base case, via template specialization:
template <unsigned int N>struct Power<N,1> {              
  static const unsigned int value = 1;
};

int main(){
  std::cout << Power<5,3>::value << std::endl;    // 25
  std::cout << Power<5,5>::value << std::endl;    // 625
  std::cout << Power<5,7>::value << std::endl;    // 15625
}

Program: The power function on integer type arguments - alternative implementation with an enumeration constant.
// The power function on integer type arguments - use of enumeration constants.

#include <iostream>

// The general case:
template <unsigned int N, unsigned int P> struct Power{   
  enum {value = N * Power<N,P-1>::value};
};
 
// The base case, via template specialization:
template <unsigned int N>struct Power<N,1> {              
  enum {value = 1};
};

int main(){
  std::cout << Power<5,3>::value << std::endl;    // 25
  std::cout << Power<5,5>::value << std::endl;    // 625
  std::cout << Power<5,7>::value << std::endl;    // 15625
}

Reference

Program: A more advanced version of the power function - from Stack Overflow.
// John Bartholomew, stack overflow
// http://stackoverflow.com/questions/4608763/compile-time-templated-c-calculations-on-unsigned-long-long-on-doubles

#include <iostream>

template <unsigned long long N, unsigned int P, int Odd = (P&1)> struct Power;

template <unsigned long long N, unsigned int P>
struct Power<N,P,0> {                    // 0: P is even  (square N and halve the power)
    static const unsigned long long val = Power<N*N,(P/2)>::val;
};

template <unsigned long long N, unsigned int P>
struct Power<N,P,1> {                    // 1: P is odd   (multiply by N and decrement the power)
    static const unsigned long long val = N * Power<N,(P-1)>::val;
};

template <unsigned long long N>
struct Power<N,0,0> {                    // zero (x**0 is 1 for all x != 0)
    static const unsigned long long val = 1;
};

int main() {
    std::cout << "2**0 = " << Power<2,0>::val << "\n";
    std::cout << "2**1 = " << Power<2,1>::val << "\n";
    std::cout << "2**2 = " << Power<2,2>::val << "\n";
    std::cout << "2**3 = " << Power<2,3>::val << "\n";
    std::cout << "2**4 = " << Power<2,4>::val << "\n";
    std::cout << "2**5 = " << Power<2,5>::val << "\n";
    std::cout << "2**6 = " << Power<2,6>::val << "\n";
    std::cout << "2**7 = " << Power<2,7>::val << "\n";
    std::cout << "2**8 = " << Power<2,8>::val << "\n";
    std::cout << "2**9 = " << Power<2,9>::val << "\n";
    std::cout << "2**10 = " << Power<2,10>::val << "\n";
    std::cout << "2**11 = " << Power<2,11>::val << "\n";
    std::cout << "2**12 = " << Power<2,12>::val << "\n";
    std::cout << "2**30 = " << Power<2,30>::val << "\n";
    std::cout << "2**40 = " << Power<2,40>::val << "\n";
    std::cout << "2**50 = " << Power<2,50>::val << "\n";
    std::cout << "2**60 = " << Power<2,60>::val << "\n";
    return 0;
}

Program: A variant of the more advanced version of the power function.
// John Bartholomew, stack overflow
// http://stackoverflow.com/questions/4608763/compile-time-templated-c-calculations-on-unsigned-long-long-on-doubles

#include <iostream>

template <unsigned long long N, unsigned int P, int Odd = (P&1)> struct Power;

template <unsigned long long N, unsigned int P>
struct Power<N,P,0> {                    // 0: P is even  (square N and halve the power)
    static const unsigned long long val = Power<N,(P/2)>::val * Power<N,(P/2)>::val;
};

template <unsigned long long N, unsigned int P>
struct Power<N,P,1> {                    // 1: P is odd   (multiply by N and decrement the power)
    static const unsigned long long val = N * Power<N,(P-1)>::val;
};

template <unsigned long long N>
struct Power<N,0,0> {                    // zero (x**0 is 1 for all x != 0)
    static const unsigned long long val = 1;
};

int main() {
    std::cout << "2**0 = " << Power<2,0>::val << "\n";
    std::cout << "2**1 = " << Power<2,1>::val << "\n";
    std::cout << "2**2 = " << Power<2,2>::val << "\n";
    std::cout << "2**3 = " << Power<2,3>::val << "\n";
    std::cout << "2**4 = " << Power<2,4>::val << "\n";
    std::cout << "2**5 = " << Power<2,5>::val << "\n";
    std::cout << "2**6 = " << Power<2,6>::val << "\n";
    std::cout << "2**7 = " << Power<2,7>::val << "\n";
    std::cout << "2**8 = " << Power<2,8>::val << "\n";
    std::cout << "2**9 = " << Power<2,9>::val << "\n";
    std::cout << "2**10 = " << Power<2,10>::val << "\n";
    std::cout << "2**11 = " << Power<2,11>::val << "\n";
    std::cout << "2**12 = " << Power<2,12>::val << "\n";
    std::cout << "2**30 = " << Power<2,30>::val << "\n";
    std::cout << "2**40 = " << Power<2,40>::val << "\n";
    std::cout << "2**50 = " << Power<2,50>::val << "\n";
    std::cout << "2**60 = " << Power<2,60>::val << "\n";
    return 0;
}

Program: Program output - both versions.
2**0 = 1
2**1 = 2
2**2 = 4
2**3 = 8
2**4 = 16
2**5 = 32
2**6 = 64
2**7 = 128
2**8 = 256
2**9 = 512
2**10 = 1024
2**11 = 2048
2**12 = 4096
2**30 = 1073741824
2**40 = 1099511627776
2**50 = 1125899906842624
2**60 = 1152921504606846976

The 'functions' from above relies on the compiler's ability to evaluate constant expressions, see §C.5 in The C++ Programming Language


Vector Basics

Vectors - basic use
Slide Annotated slide Contents Index
References 

In an earlier lecture we have studied the basic properties and use of vectors in C++

Reference


Iterators

Iterators seen as generalized pointers
Slide Annotated slide Contents Index
References 

C++ iterators are modelled as generalized pointers

The pointer-related operators are used to manipulate iterators

Reference
  • The C++ Programming Language: Page 57, 550

References

  • Most important operators on iterators

    • The current element: * and ->

    • Go to the next element: ++

    • Equality ==

  • The start of a sequence s

    • s.begin()

  • The end of a sequence s

    • s.end()

    • Designates a non-existing one past the last element

  • Iterator validity

    • An iterator can only be used if it is valid

    • An iterator is invalid if it is non-intialized, points to the end, if the container has been destroyed, resized, ...

Example uses of iterators - basis stuff
Slide Annotated slide Contents Index
References 

We show a simple, practical example of iterators and their use

Program: A really simple example of iterators.
#include <iostream>
#include <string>
#include <vector>

int main(){
  using namespace std;

  vector<double> vd;

  for(int i = 1; i <= 10; i++)
     vd.push_back(i + i/10.0);

  typedef vector<double>::iterator vec_it;

  vec_it it1 = vd.begin();
 
  while(it1 != vd.end()){
     cout << *it1 << " ";   // 1.1 2.2 3.3 4.4 5.5 6.6 7.7 8.8 9.9 11 
     ++it1;
  }
}

Program: The same program using a reverse iterator.
#include <iostream>
#include <string>
#include <vector>

int main(){
  using namespace std;

  vector<double> vd;

  for(int i = 1; i <= 10; i++)
     vd.push_back(i + i/10.0);

  typedef vector<double>::reverse_iterator vec_it;

  vec_it it1 = vd.rbegin();

  while(it1 != vd.rend()){
     cout << *it1 << " ";   // 11 9.9 8.8 7.7 6.6 5.5 4.4 3.3 2.2 1.1 
     ++it1;
  }
}

Different classifications of iterators
Slide Annotated slide Contents Index
References 

C++ iterators are classified in a number of different dimensions - not always completely orthogonal

Despite being heavily classified, the iterator types are not organized in a class hierarchy

Reference
  • The C++ Programming Language: Page 551, 553, 557, 561

  • Const and non-const iterators

    • A const iterator cannot be used for modification of the designated element

  • Checked and non-checked iterators

    • A checked iterator enforces range checking

  • Reverse and 'normal non-reverse' iterators

    • For a reverse iterator, ++ moves backward

  • Input, output, forward, bidirectional, random-access iterators

    • Input and output iterators have relative few operators defined

    • Random access iterators have many operators defined

    • Next slide

Categories of iterators
Slide Annotated slide Contents Index
References 

Tabular overview of the five catetories at the top of page 551

The classification list operations that can be implemented efficiently - O(1)

Reference
  • The C++ Programming Language: Page 550

Reference

  • All iterators

    • ++

  • Output iterator p

    • Can write into the container with *p = x

    • Cannot read the current element by x = *p

  • Input iterator p

    • Can read the current element by x = *p

    • Cannot write to current element by *p = x

    • Other operators: ==, !=

  • Forward

    • As read and write

    • Other operators: ==, !=

  • Bidirectional

    • -- applies

    • Else like forward iterators

  • Random-access

    • Can add and subtract integers to/from iterators

    • Can read and write

    • Can compare iterators with <, <=, >, and >=

    • Other operators: ==, !=

The categories are not represented by inheritance, but they appear in iterator tags types (page 554) - used for convenient functions overloding

The distance between two iterators can be calculated for all iterators, appart from output iterators, simply by advancing the first until it meets the other

Insert iterators
Slide Annotated slide Contents Index
References 

Many algorithms overwrites existing elements

It is also necessary to be able to insert new elements

Insertion is done by the container operations push_back(), push_front(), and insert()

Insertion can also be accomplished via insert-iterators, which are output iterators

Insertion iterators can be created by the template (factory) functions back_inserter, front_inserter, and inserter.

Using these, assignments are used for inserting new elements

Reference
  • The C++ Programming Language: Page 555

Program: Output insert-iterators and factory functions that create such iterators.
// Demonstration of output iterators and inserters

#include <iostream>
#include <string>
#include <vector>
#include <list>

template <typename CONT> void print_seq(const CONT &v);

int main(){
  using namespace std;

  // Make and initialize a vector:
  vector<double> vd;
  for(int i = 1; i <= 10; i++)
     vd.push_back(i + i/10.0);

  typedef back_insert_iterator<vector<double> > back_ins_vec_it;

  // BACK INSERT ITERATOR:
  // Make back insert iterator (an output iterator).
  // The back inserter overloads the assignment operator,
  // see The C++ Programming Language 3ed, page 556.
  back_ins_vec_it bii = back_inserter(vd);

  *bii = 20;
  *bii = 21;

  print_seq(vd);  // 1.1 2.2 3.3 4.4 5.5 6.6 7.7 8.8 9.9 11 20 21


  // FRONT INSERT ITERATOR             (cannot be used on vector)
  typedef front_insert_iterator<list<double> > front_ins_list_it;

  list<double> ld;              
  for(int i = 1; i <= 10; i++)
     ld.push_back(i + i/10.0);

  front_ins_list_it fii = front_inserter(ld);
  *fii = -3;
  *fii = -5.7;

  print_seq(ld);   // -5.7 -3 1.1 2.2 3.3 4.4 5.5 6.6 7.7 8.8 9.9 11


  // INSERT ITERATOR
  typedef insert_iterator<list<double> > ins_list_it;

  typename list<double>::iterator ins_begin = ld.begin();  
  ++++++ins_begin;        // Advance the iterator 3 positions.

  // An inserter that starts inserting at ins_begin
  ins_list_it ili = inserter(ld, ins_begin);

  *ili = 100;
  *ili = 101;
  print_seq(ld);   // -5.7 -3 1.1 100 101 2.2 3.3 4.4 5.5 6.6 7.7 8.8 9.9 11

}

// Print the sequence v on standard output:
template <typename CONT> void print_seq(const CONT &v){
  typename CONT::const_iterator it = v.begin();
  while(it != v.end()){
     std::cout << *it << " ";
     it++;
  }
  std::cout << std::endl;
}  


Standard Containers

Documentation of the container library
Slide Annotated slide Contents Index
References 

Be sure to use the online documentation of the STL container library

http://www.cplusplus.com/reference/stl/

Lots of useful examples

STL - Standard Template Library

The template library for containers and iterators

Overview of containers
Slide Annotated slide Contents Index
References 

Three kinds of containers in the C++ template library

The most important container types - not a complete listing

Reference
  • The C++ Programming Language: Page 52-56

  • Sequences

    • list, vector, deque

    • stack, queue, priority_queue via adapters on other sequences - restricting interfaces

  • Associative containers

    • map, multimap, set, multiset

  • Almost containers

    • string, valarray, bitset, and built-in arrays

References

A priority queue example
Slide Annotated slide Contents Index
References 

A priority queue is a heap

We show an example of a priority queue of points, which is built on top of double-ended queue

A priority queue relies on a comparison function - in our case the overloaded   <   operator in class Point

A priority queue adapts an underlying container, defaulted to vector - we try a deque instead.

Reference
  • The C++ Programming Language: Page 478

Program: Class point with an overloaded operator<.
class Point {
private: 
  double x, y;

public:
  Point(double, double);
  Point();
  double getx () const;
  double gety () const;
  void move(double, double);
  double distance_to(Point);

  friend bool operator< (const Point&, const Point&);
  
};

std::ostream& operator<<(std::ostream&, const Point&);

Program: The implementation of class Point and in particular operator<.
#include <cmath>
#include <iostream>
#include "point.h"

Point::Point(double x_coord, double y_coord): x(x_coord), y(y_coord){
}

Point::Point(): x(0.0), y(0.0){
}

double Point::getx () const{
  return x;
}

double Point::gety () const{
  return y;
}

void Point::move(double dx, double dy){
    x += dx; y += dy;
}

double Point::distance_to(Point p){
    return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
}

// funny implementation
bool operator<(const Point& p, const Point& q){  
  return p.x+p.y < q.x+q.y;
}

std::ostream& operator<<(std::ostream& s, const Point& p){
  return s << "(" << p.getx() << "," << p.gety() << ")" ;
}

Program: Illustration of priority_queue<Point, deque<Point> >.
#include <iostream>
#include <string>
#include <queue>
#include <list>
#include "point.h"

int main(){
  using namespace std;

  priority_queue<Point, deque<Point> > point_queue;     // A priority queue of points.
                                                        // Built on a deque<Point>.
  Point p1(1,2),   p2(-5,27),
        p3(3,4),   p4(7,8),
        p5(-3,-4), p6(0,0);

  point_queue.push(p1);   point_queue.push(p2);
  point_queue.push(p3);   point_queue.push(p4);
  point_queue.push(p5);   point_queue.push(p6);

  while (not (point_queue.empty())){
    cout << point_queue.top() << " ";  // (-5,27) (7,8) (3,4) (1,2) (0,0) (-3,-4)
    point_queue.pop();
  }

}

A map example
Slide Annotated slide Contents Index
References 

We show a simple example of the use of the map standard container

An example taken from The C++ Programming Language page 483

Program: Illustration of the map standard container.
// Reproduced from The C++ Programming Language, 3ed, page 483.
// Read strings and counts from standard input, and keep track of the
// sum for a particular string in the map. Also calculate the final total.

#include <iostream>
#include <string>
#include <map>

using namespace std;

void readitems(map<string, int> &m){
 string word;
 int val;
 while (cin >> word >> val)
   m[word] += val;             // Relies on the default map value initialization.
}

int main(){
  map<string,int> str_count;   // All values in the map are initialized to 0.

  readitems(str_count);

  int total = 0;
  typedef map<string,int>::const_iterator CI;
  
  // Accumulating total - and printing:
  for(CI it = str_count.begin(); it != str_count.end(); ++it){
    total += it->second;
    cout << it->first << "\t\t" << it->second << endl;
  }

  cout << "-------------------------\ntotal\t\t" << total << endl;
}

Program: Sample program input - provided via input redirection.
abba 7   beatles 8  abba 3      stones 10  elvis 12 
cash 13  abba 5     beatles 12  cash 10    abba 7

Program: Program output.
abba            22
beatles         20
cash            23
elvis           12
stones          10
-------------------------
total           87

Common properties of containers
Slide Annotated slide Contents Index
References 

Overall properties of STL containers

Reference
  • The C++ Programming Language: Page 441

Reference

  • No common base class for the standard containers

    • However, each container provides standard operations with standard names and semantics

  • Emphasis on iterators

    • Different kinds of iterators are not related by a common base class

  • Non-intrusive containers

    • Elements of containers do no need to be instances of certain classes

    • Values of built-in types can be elements in container

  • Standard containers relies heavily on templates

    • Template specializations provide shared implementations for pointers to elements

Container member types
Slide Annotated slide Contents Index
References 

Each standard container defines a number of types - via typedefs

These type definitions serve as standard type names that apply for all container types

Reference
  • The C++ Programming Language: Page 443, 462

  • Examples of member types defined in standard containers

    • value_type

    • iterator, const_iterator, reverse_iterator, const_reverse_iterator

    • size_type, difference_type

    • pointer, const_pointer

    • reference, const_reference

Program: Illustration of the use of member types for a list of chars.
#include <iostream>
#include <string>
#include <list>

int main(){
  using namespace std;

  list<char> lc;
  lc.push_back('a'); lc.push_back('b'); lc.push_back('e');

  list<char>::value_type x = 'c';               // A complicated way to denote the type char
  list<char>::iterator lc_it = lc.begin();      // The iterator type of list<char>
  list<char>::size_type sz = lc.size();         // The size type of list<char>
}

Program: Same program - now with use of typename as prefix of 'nested dependent type names'.
#include <iostream>
#include <string>
#include <list>

int main(){
  using namespace std;

  list<char> lc;
  lc.push_back('a'); lc.push_back('b'); lc.push_back('e');

  typename list<char>::value_type x = 'c';               // A complicated way to denote the type char
  typename list<char>::iterator lc_it = lc.begin();      // The iterator type of list<char>
  typename list<char>::size_type sz = lc.size();         // The size type of list<char>
}

Program: Illustration of a couple of ambiguities.
#include <vector>

int x = 5;

template<typename T>double f(){      // The name iterator depends on T.
  T::iterator *x;                    // Ambiguity 1:  
                                     //   T::iterator multiplied by x    OR
                                     //   x declared as a pointer to the type named T::iterator
  // ...
}

int main(){
  f<std::vector<double>>();          // Ambiguity 2:
                                     //  >>   shift right   OR
                                     //  end of nested template argument list
}

Program: Compiler error messages.
ambiguities-1.cpp: In function 'int main()':
ambiguities-1.cpp:13:23: error: '>>' should be '> >' within a nested template argument list
ambiguities-1.cpp: In function 'double f() [with T = std::vector<double>]':
ambiguities-1.cpp:13:26:   instantiated from here
ambiguities-1.cpp:6:3: error: dependent-name 'T:: iterator' is parsed as a non-type, but instantiation yields a type
ambiguities-1.cpp:6:3: note: say 'typename T:: iterator' if a type is meant

Program: Ambiguities resolved.
#include <vector>

int x = 5;

template<typename T>double f(){
  typename T::iterator *x;    


  // ...
}

int main(){
  f<std::vector<double> >(); 
                             
                             
}

A vector specialization: vector<bool>
Slide Annotated slide Contents Index
References 

vector<bool> is a specialization of vector<T> that provides for compact representation of boolean vectors

vector<bool> complements the fixed-typed container bitset<N>

Reference
  • The C++ Programming Language: Page 548 - Vector<bool>. 492 - bitset<N>.

Program: Illustration of the use of vector<bool>.
#include <iostream>
#include <vector>

int main(){
  using namespace std;

  vector<bool> vb;

  vb.push_back(true);  vb.push_back(true);  vb.push_back(false);
  vb.push_back(false); vb.push_back(false); vb.push_back(true);
  
  typedef vector<bool>::const_iterator VBI;

  for(VBI it = vb.begin(); it != vb.end(); it++) cout << *it;  // 110001
}


Algorithms

Documentation of the algorithms library
Slide Annotated slide Contents Index
References 

Be sure to use the online documentation of the algorithms library

http://www.cplusplus.com/reference/algorithm/

Lots of useful examples

Overview of Algorithms
Slide Annotated slide Contents Index
References 

The standard library contains approximately 60 standard algorithms

Most of these represent simple ideas, as opposed to algorithms in an Algorithms and Data Structure course tradition

The design here is not on the desing of algorithms or even on the use of any but the simplest and most obvious algorithms, §18.2 in The C++ Programming Language

Reference
  • The C++ Programming Language: Page 508

  • Nonmodifying sequence algorithms

    • for-each(): Applies a function on each element of a sequence

    • find(): Find the first element that satisfies a given predicate. Return iterator to element

  • Modifying sequence algorithms

    • transform(): Applies a function on each element, and writes the result into another container.

    • replace(): Replace elements that satisfies a predicate with a another value

  • Sorted sequence algorithms

    • sort

    • binary_search

  • Set algorithms

    • Heap algorithms

      • make_heap, push_heap, and pop_heap

    • Min and max algorithms

      • The naive min and max functions

      • max_element and min_element: Generalization to sequences of elements

    • Permutation algorithms

      • next_permuation and prev_permuation: Systematic creation of permutations of a sequence

    • Numeric algorithms

      Principles used for algorithms
      Slide Annotated slide Contents Index
      References 

      We list a number of principles (ideas and concepts) which are typically used for a number of standard algorithms

      • Generalization by function parameters

        • Insight from higher-order functions

        • Spawns some work on C++ function objects §18.4

          • Due to the lack of lambda expressions - until C++ 2011

      • A sequence is defined by two iterators

        • Beginning at the first element

        • Ended by the one-beyond-the-last element

      • Failure to find an element in a sequence

        • Return the (off by one) end of sequence iterator

      • Algorithms that use a pair of iterators as input

        • Bundle these in pairs: input sequences, §18.3.1

        • Provide factory methods that produce such a pair of sequences

          • iseq(Container c) returns such a pair from c.begin() to c.end()

      The for-each algorithm
      Slide Annotated slide Contents Index
      References 

      In C++ for-each is an algorithm, not a control structure like foreach in C#

      C++ 2011 has introduced a 'range based for loop' similar to foreach in C#

      Program: A possible implementation of the for-each algorithm.
      // The C++ Programming Language, 3ed, page 524.
      // Possible definition of the for_each function template. 
      template <class In, class Op> Op for_each(In first, In last, Op f){
        while (first != last) f(*first++);
        return f;
      }

      Program: Implementation and sample use of for-each on an C-style array.
      #include <iostream>
      #include <string>
      
      
      // The C++ Programming Language, 3ed, page 524.
      // Possible definition of the for_each function template. 
      template <class In, class Op> Op for_each(In first, In last, Op f){
        while (first != last) f(*first++);
        return f;
      }
      
      void print_element(int i){
        std::cout << i << std::endl;
      }
      
      int main(){
        int a[] = {7,9,8,1,-1};
      
        // The two first parameters are iterators:
        for_each(a, a+5, print_element);  // 7, 9, 8, 1, -1
      }

      Program: Implementation and sample use of for-each on a list of integers.
      #include <iostream>
      #include <string>
      #include <list>
      
      
      
      template <class In, class Op> Op for_each(In first, In last, Op f){
        while (first != last) f(*first++);
        return f;
      }
      
      void print_element(int i){
        std::cout << i << std::endl;
      }
      
      int main(){
        using namespace std;
      
        list<int> lst;
        lst.push_back(7);   lst.push_back(9);  lst.push_back(8);  lst.push_back(1);  lst.push_back(-1);
      
        // The two first parameters are iterators:
        for_each(lst.begin(), lst.end(), print_element);   // 7 9 8 1 -1
      }

      • A Stroustrup advice:

        • "In general, before using for_each(), consider if there is a more specialized algorithm that would do more for you"

          • Such as find() or accumulate()

      • Observation about the return-value of for_each

        • The function f of type Op is returned.

          • Later we will see an example where this is convenient

      Function objects
      Slide Annotated slide Contents Index
      References 

      A function object (function-like object or functor) is a an object with an application operator, operator()

      Reference
      • The C++ Programming Language: Page 514-515, 287

      Program: Class Point with overloadings of the application operator.
      class Point {
      private: 
        double x, y;
      
      public:
        Point(double, double);
        Point();
        double getx () const;
        double gety () const;
        void move(double, double);
        double distance_to(Point);
      
        double operator()(int) const;
        double operator()(Point) const;
      };
      
      std::ostream& operator<<(std::ostream&, const Point&);

      Program: Definition of Point application operators.
      #include <cmath>
      #include <iostream>
      #include "point.h"
      
      Point::Point(double x_coord, double y_coord): x(x_coord), y(y_coord){
      }
      
      Point::Point(): x(0.0), y(0.0){
      }
      
      double Point::getx () const{
        return x;
      }
      
      double Point::gety () const{
        return y;
      }
      
      void Point::move(double dx, double dy){
          x += dx; y += dy;
      }
      
      double Point::distance_to(Point p){
          return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
      }
      
      double Point::operator()(int i) const{
        return x + y + 2*i;
      }
      
      double Point::operator()(Point otherP) const{
        return x*otherP.x + y*otherP.y;
      }
      
      std::ostream& operator<<(std::ostream& s, const Point& p){
        return s << "(" << p.getx() << "," << p.gety() << ")" ;
      }

      Program: Sample uses of the application operators - Funny and artificial.
      #include <iostream>
      #include <string>
      #include "point.h"
      
      int main(){
        using namespace std;
      
        Point p(1,2),
              q(3,4);
        double d, e;
      
        d = p(5);                     // Use the application operator on p, pass 5 as the int parameter.
                                      // Pretends that p is a function.
                                      // 1 + 2 + 2*5
        cout << "d: " << d << endl;   // 13
      
        e = p(q);                     // Another overload of the application operator.
                                      // Applies p on q
                                      // Pretends, in a similar way, that p is a function.
                                      // 1*3 + 2*4 
        cout << "e: " << e << endl;   // 11
        
      }

      As another example, we provide access to x and y in point p via p(1) and p(2)

      Program: Class Point with another overloading of the application operator.
      // Another example - another overload of the Point application operator, as applied on int.
      
      class Point {
      private: 
        double x, y;
      
      public:
        Point(double, double);
        Point();
        double getx () const;
        double gety () const;
        void move(double, double);
        double distance_to(Point);
      
        double operator()(int i) const;   // Accesses x or y
      };
      
      class IndexProblem{};
      
      std::ostream& operator<<(std::ostream&, const Point&);

      Program: Definition of then Point application operator.
      #include <cmath>
      #include <iostream>
      #include "point.h"
      
      Point::Point(double x_coord, double y_coord): x(x_coord), y(y_coord){
      }
      
      Point::Point(): x(0.0), y(0.0){
      }
      
      double Point::getx () const{
        return x;
      }
      
      double Point::gety () const{
        return y;
      }
      
      void Point::move(double dx, double dy){
          x += dx; y += dy;
      }
      
      double Point::distance_to(Point p){
          return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
      }
      
      double Point::operator()(int i) const{
        if (i == 1)
          return x;
        else if (i == 2)
          return y;
        else throw IndexProblem();  
      }
      
      std::ostream& operator<<(std::ostream& s, const Point& p){
        return s << "(" << p.getx() << "," << p.gety() << ")" ;
      }

      Program: Sample uses of the application operators - slightly more realistic.
      #include <iostream>
      #include <string>
      #include "point.h"
      
      int main(){
        using namespace std;
      
        Point p(1,2),
              q(3,4);
      
      
        try{
          cout << "p(1): " << p(1) << endl;   // 1
          cout << "p(2): " << p(2) << endl;   // 2
      
          cout << "q(1): " << q(1) << endl;   // 3
          cout << "q(2): " << q(2) << endl;   // 4
      
          cout << "p(3): " << p(3) << endl;   // Throws IndexProblem exception.
        }
        catch (IndexProblem){
          cout << "Recovering from indexing problem" << endl;
        }
        
      }

      Using the sort algorithm
      Slide Annotated slide Contents Index
      References 

      We reproduce an example program that uses the sort algorithm from cplusplus.com

      Program: Two overloads of the sort function template.
      template <class RandomAccessIterator>
        void sort (RandomAccessIterator first, RandomAccessIterator last);
      
      template <class RandomAccessIterator, class Compare>
        void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

      Program: Sorting a vector of integers.
      // sort algorithm example   - reproduced directly from www.cplusplus.com
      
      #include <iostream>     // std::cout
      #include <algorithm>    // std::sort
      #include <vector>       // std::vector
      
      bool myfunction (int i,int j) { return (i<j); }
      
      struct myclass {
        bool operator() (int i,int j) { return (i<j);}
      } myobject;
      
      int main () {
        int myints[] = {32,71,12,45,26,80,53,33};
        std::vector<int> myvector (myints, myints+8);               // 32 71 12 45 26 80 53 33
      
        // using default comparison (operator <):
        std::sort (myvector.begin(), myvector.begin()+4);           //(12 32 45 71)26 80 53 33
      
        // using function as comp
        std::sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)
      
        // using object as comp
        std::sort (myvector.begin(), myvector.end(), myobject);     //(12 26 32 33 45 53 71 80)
      
        // print out content:
        std::cout << "myvector contains:";
        for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
          std::cout << ' ' << *it;
        std::cout << '\n';
      
        return 0;
      }

      An example of for-each and function objects
      Slide Annotated slide Contents Index
      References 

      An sample use of for-each() to find out if a list is sorted

      Initial discussions of possible solutions to this simple problem

      Program: A possible use of for-each to solve this problem.
      // Example from C++ in a Nutshell, page 337-338. Slightly revised.
      
      #include <iostream>
      #include <algorithm>
      #include <list>
      
      // An object of an instance of Is_sorted is used as a function
      // with state, corresponding to the three data members.
      template<typename T> class Is_sorted{
      private:
        bool first_time,    // true when applied first time
             sorted;        // true as along as prefix is sorted
        T prev_item;        // the previous item
      
      public:
        Is_sorted(): first_time(true), sorted(true){}
      
        void operator() (const T& item){
          if (first_time)
            first_time = false;
          else if (item < prev_item)
            sorted = false;
          prev_item = item;
        }
      
        operator bool(){return sorted;}
      };
      
      int main(){
        using namespace std;
      
        list<int> lst;
        lst.push_back(3); lst.push_back(15); lst.push_back(9); lst.push_back(11); 
        lst.push_back(13); lst.push_back(15); lst.push_back(19); lst.push_back(21); 
      
        if(for_each(lst.begin(), lst.end(), Is_sorted<int>()))
          cout << "The list lst is sorted" << endl;
        else
          cout << "The list lst is NOT sorted" << endl;
      }

      • Observations

        • Use of objects as functions via an overload of the application operator

        • A function surrounded by private, mutable state

        • Use of the returned value from for-each

      Program: Following the advice: Solve the problem with a more appropriate algorithm.
      // A more straightforward solution - using the adjent_find algorithm
      
      #include <iostream>
      #include <algorithm>
      #include <list>
      
      int main(){
        using namespace std;
      
        list<int> lst;
        lst.push_back(3); lst.push_back(5); lst.push_back(9); lst.push_back(11); 
        lst.push_back(13); lst.push_back(15); lst.push_back(19); lst.push_back(21); 
      
        if(adjacent_find(lst.begin(), lst.end(), greater<int>()) != lst.end())    // find element out of order
          cout << "The list lst is NOT sorted" << endl;
        else
          cout << "The list lst is sorted" << endl;
      }

      • Observation

        • greater is a wrapper around the > operator, §18.4.2.1

      Program: The type greater and its base class.
      template <class Arg1, class Arg2, class Result>
        struct binary_function {
          typedef Arg1 first_argument_type;
          typedef Arg2 second_argument_type;
          typedef Result result_type;
        };
      
      template <class T> struct greater : binary_function <T,T,bool> {
        bool operator() (const T& x, const T& y) const
          {return x>y;}
      };

      Use of function objects in STL
      Slide Annotated slide Contents Index
      References 

      In a context where lambda expressions are not yet used, and

      operators are not functions

      Binders, Adapters and Negaters

      Reference
      • The C++ Programming Language: Page 518

      • Wrapping operator predicates

        • Predicates such as == and <

        • Available as for instance equal_to, less, and greater - see §18.4.2.1

      • Wrapping arithmetic operators

        • Operators such as + and -

        • Available as plus and minus, see §18.4.3

      • Binding one argument of a two argument function

        • Currying

      • Allowing a member function to be used as a function

        • mem_fun, applied on a member pointer, servers as a function that can called on an object

      • Negating a predicate

        Adapter examples
        Slide Annotated slide Contents Index
        References 

        We show a couple of example of Adapters

        Adaption of an operator (+) and adaptation of a member function (print in Point)

        Program: An illustration of plus<double>.
        // A program that illustrate the difference between the plus operator
        // and a function of two arguments that adds the arguments together.
        
        #include <iostream>
        #include <list>
        #include <numeric>     // accumulate
        #include <functional>  // plus
        
        int main(){
          using namespace std;
        
          list<double> lst;
          for(int i = 1; i <= 10; i++) lst.push_back(i);   // 1, 2, ..., 10
        
          // An operator is NOT a first class entity in C++:
          double res = accumulate(lst.begin(), lst.end(), 0.0, +);   // error: expected primary-expression ....
        
          // We must make an object which serves as a binary plus function: 
          double res = accumulate(lst.begin(), lst.end(), 0.0, plus<double>() );
        
          cout << "The plus accumulation is: " << res << endl;       // 55
        }

        Program: A possible definition of plus.
        // We show a possible definition of plus, as a struct with an 
        // application operator. The binary_function is not strictly necessary.
        // It only contains a few typedefs
        
        #include <iostream>
        #include <list>
        #include <numeric>     // accumulate
        #include <functional>  // binary_function
        
        template <class T> struct plus: public std::binary_function<T,T,T> {
          T operator() (const T& x, const T& y) const {return x+y;}
        };
        
        int main(){
          std::list<double> lst;
          for(int i = 1; i <= 10; i++) lst.push_back(i);   // 1, 2, ..., 10
        
          // We must make an object which serves as a binary plus function: 
          double res = std::accumulate(lst.begin(), lst.end(), 0.0, plus<double>() );
        
          std::cout << "The plus accumulation is: " << res << std::endl;       // 55
        }

        Program: Another definition of plus - as a function template.
        // We show another definition of plus, as a function template.
        // A down-to-earth approach.
        
        #include <iostream>
        #include <list>
        #include <numeric>     // accumulate
        #include <functional>  // binary_function
        
        template<typename T> T plus_fn(T a, T b){
          return a + b;
        }
        
        int main(){
          std::list<double> lst;
          for(int i = 1; i <= 10; i++) lst.push_back(i);   // 1, 2, ..., 10
        
          // We must make an object which serves as a binary plus function: 
          double res = std::accumulate(lst.begin(), lst.end(), 0.0, plus_fn<double>);
        
          std::cout << "The plus accumulation is: " << res << std::endl;       // 55
        }

        Program: Use of member function adaption, with mem_fun_ref.
        // Illustration of member function adaptions.
        // We cannot just pass a pointer to a member function to for_each and
        // similar functions, because we miss the target. And we cannot easily
        // make use of the .* operator to bind the target object.
        
        #include <iostream>
        #include <string>
        #include <list>
        #include <algorithm>
        #include "point.h"
        
        void f(std::list<Point> &lp){
         using namespace std;
        
          // error: must use  .*  or  ->*  to call pointer-to-member function:
          for_each(lp.begin(), lp.end(), &Point::print);  
        
          // Adapting the member function pointer to print, such that it becomes
          // a function that can be called by for_each:
          for_each(lp.begin(), lp.end(), mem_fun_ref(&Point::print));
        }
        
        int main(){
          using namespace std;
          Point p1(1,2),   p2(-5,27),
                p3(3,4),   p4(7,8),
                p5(-3,-4), p6(0,0);
        
          list<Point> point_list;
          point_list.push_back(p1);   point_list.push_back(p2);
          point_list.push_back(p3);   point_list.push_back(p4);
          point_list.push_back(p5);   point_list.push_back(p6);
        
          f(point_list);
        }

        Program: The definition of Point - point.h.
        class Point {
        private: 
          double x, y;
        
        public:
          Point(double, double);
          Point();
          double getx () const;
          double gety () const;
          void move(double, double);
          double distance_to(Point);
          void print();
        };


        Collected references
        Contents Index
        The C++ Programming Language: Page 338
        The C++ Programming Language: Page 341
        vector<bool> as a specialization of vector<T>
        The math behind the quick power function
        Vectors in C++
        The C++ Programming Language: Page 57, 550
        Collections in C#
        The iterator design pattern
        The C++ Programming Language: Page 551, 553, 557, 561
        The C++ Programming Language: Page 550
        Iterator categories at cplusplus.com
        The C++ Programming Language: Page 555
        The C++ Programming Language: Page 52-56
        multiset at cplusplus.com
        set at cplusplus.com
        multimap at cplusplus.com
        map at cplusplus.com
        priority_queue at cplusplus.com
        queue at cplusplus.com
        stack at cplusplus.com
        deque at cplusplus.com
        list at cplusplus.com
        vector at cplusplus.com
        The C++ Programming Language: Page 478
        The C++ Programming Language: Page 441
        C# counterpart - Collection class hierarchy
        The C++ Programming Language: Page 443, 462
        The C++ Programming Language: Page 548 - Vector<bool>. 492 - bitset<N>.
        The C++ Programming Language: Page 508
        The C++ Programming Language: Page 514-515, 287
        The C++ Programming Language: Page 518

         

        Chapter 5: Templates and The Standard Library
        Course home     Author home     About producing this web     Previous lecture (top)     Next lecture (top)     Previous lecture (bund)     Next lecture (bund)     
        Generated: March 26, 2013, 13:03:51