Chapter 6
The Standard Library and Metaprogramming

Kurt NÝrmark
Department of Computer Science, Aalborg University


Abstract
Previous lecture
Index References Contents
...


Iterators

Iterators seen as generalized pointers
Slide Contents Index
References 

C++ iterators are modelled as generalized pointers

The pointer-related operators are used to manipulate iterators

Reference
  • The C++ Prog. Lang. (3. edition): Page 57, 550

Reference
  • The C++ Prog. Lang. (4. edition): Page 103, 953

References

  • The most important operators on iterators

    • Access to the current element: * and ->

    • Go to the next element: ++

    • Equality and inequality: == and !=

  • 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 - basic stuff
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);

  auto it1 = vd.begin();    // auto covers the type vector<double>::iterator
 
  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.
// Reverse iterator - instead of forward 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);

  auto 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;
  }
}

Program: Equivalent program with range-for - with iterators abstracted away - C++11.
// No iterators at all - range-for instead (C++11).

#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);

  for(auto el: vd){
     cout << el << " ";   // 1.1 2.2 3.3 4.4 5.5 6.6 7.7 8.8 9.9 11 
  }
}

Different classifications of iterators
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++ Prog. Lang. (3. edition): Page 551, 553, 557, 561

Reference
  • The C++ Prog. Lang. (4. edition): Page 953

  • 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

  • Insert iterators

    • Inserting - instead of overwriting - elements in a container

  • 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 Contents Index
References 

Tabular overview of the five catetories at the top of page 956 in The C++ Prog. Lang. (4. edition)

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

Reference
  • The C++ Prog. Lang. (3. edition): Page 550

Reference
  • The C++ Prog. Lang. (4. edition): Page 955

Reference

  • All iterators

    • ++, *

  • Input iterator p

    • Can read the current element (at least once) by x = *p

    • Cannot necessarily write to current element by *p = x

    • Other operators: ==, !=

  • Output iterator p

    • Can write (once) into the container with *p = x

    • Cannot necessarily read the current element by x = *p

  • Forward

    • Like input and output iterator

    • Can read and write repeatedly

  • Bidirectional

    • Like forward iterator

    • -- applies

  • Random-access

    • Like bidirectional iterator

    • Can add and subtract integers to/from iterators

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

The categories are not represented by inheritance, but they appear in iterator tags types (page 956 The C++ Prog. Lang. (4. edition)) - used for convenient functions overloding

The distance between two iterators can be calculated for most iterators, simply by advancing the first until it meets the other

Insert iterators
Slide Contents Index
References 

Many algorithms overwrite existing elements

It is also necessary to be able to insert new elements

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

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

Using these, assignments are used for insertion of new elements

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

Reference
  • The C++ Prog. Lang. (3. edition): Page 555

Reference
  • The C++ Prog. Lang. (4. edition): Page 963

Program: Output insert-iterators and factory functions that create such iterators.
// Demonstration of output iterators and inserters (C++11, due to >> in template notation, and not > >).

#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) - using a factory function on the container
  // The back inserter overloads the assignment operator, see The C++ Programming Language 4ed, page 964.
  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 - confusing use of prefix increment. 

  // 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;
}  

Program: Same program - simplified in various ways in C++11.
// C++11 version - Still demonstration of output iterators and inserters.
// Takes advantages of auto. Uses next instead of chaining of prefix increment.

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <iterator>   // std::next

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);

  // 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.
  auto 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)

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

  auto 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   (on the list ld. Will also work on the vector vd).
  auto ins_begin = ld.begin();  
  auto pos = next(ld.begin(), 3);    // Advance the iterator 3 positions.

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

  *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;
}  

Reference


Standard Containers

Documentation of the container library
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 Contents Index
References 

Three kinds of containers in the C++ template library

The most important container types - not a complete listing

Reference
  • The C++ Prog. Lang. (3. edition): Page 52-56

Reference
  • The C++ Prog. Lang. (4. edition): Page 101

Reference

  • Sequences

    • vector, list, forward_list, deque

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

  • Associative containers

    • Based on balanced trees:   map, multimap, set, multiset

    • Based on hash tables:   unordered_map, unordered_multimap, unordered_set, unordered_multiset

  • Almost containers

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

    • array (C++11)

      • Contains it elements directly (not a handle to its elements)

      • Fixed size - the size is a constant expression

      • Move is not more efficient than copy

Reference
  • The C++ Prog. Lang. (4. edition): array. Page 974

References

Common properties of containers
Slide Contents Index
References 

Overall properties of STL containers

Reference
  • The C++ Prog. Lang. (3. edition): 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

    • An object is not aware of being an element of a particular container

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

  • Standard containers rely heavily on templates

    • Template specializations provide shared implementations for pointers to elements

A priority queue example
Slide Contents Index
References 

A priority queue is a heap

top() returns the largest element in the queue

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 is an adoptor of an underlying container - defaulted to vector - in the example below we use deque

Reference
  • The C++ Prog. Lang. (3. edition): Page 478

Reference
  • The C++ Prog. Lang. (4. edition): Page 923

References

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();
  }

}

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 - compares sum of x and y coordinates
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() << ")" ;
}

A map example
Slide Contents Index
References 

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

An example taken from The C++ Prog. Lang. (3. edition) page 483

Reference

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;
  using CI = map<string,int>::const_iterator;    // C++11
  
  // Accumulating total - and printing - via use of const interator:
  for(CI it = str_count.begin(); it != str_count.end(); ++it){
    pair<string,int> element = *it;              // Emphasizing that keys and values are grouped in a pair.
    total += element.second;
    cout << element.first << "\t\t" << element.second << endl;
  }

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

Program: Alternative version - using range-for for traveral of the map.
// Alternative version where the map is traversed with a range-for statement.
// 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;
  
  // Accumulating total - and printing - via use of range-for:
  for(auto element: str_count){    // C++11
    total += element.second;
    cout << element.first << "\t\t" << element.second << endl;
  }

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

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

Reference

Program: Program output - as produced on the input from above.
abba            22
beatles         20
cash            23
elvis           12
stones          10
-------------------------
total           87

Container member types
Slide Contents Index
References 

Each standard container defines a number of types - via using type aliases

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

Reference
  • The C++ Prog. Lang. (3. edition): Page 443, 462

Reference
  • The C++ Prog. Lang. (4. edition): Page 896

Reference
  • The C++ Prog. Lang. (4. edition): using type alias. Page 167

  • Examples of member types defined in standard containers, such as

    • 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.
// Examples of member types of list<T>.

#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'.
// Using typename to emphasize that a dependent name (a name that depends on a template parameter) is a type name. 

#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>
}

In C++11 it is often possible to avoid use of container member type names - because auto can be used instead

Member types - ambiguities
Slide Contents Index
References 

Some ambiguities may occur - in part related to uses of member types of containers

Program: Illustration of a couple of ambiguities.
// Example of an ambiguity: 

#include <vector>

int x = 5;

template<typename T>double f(){      // The name iterator depends on T (it is a dependent name, page 746 (4ed)).
  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.
// Ambiguities resolved.

#include <vector>

int x = 5;

template<typename T>double f(){
  typename T::iterator *x;              // Notice use of typename:  
                                        // Means that the dependent name is a typename.

  // ...
}

int main(){
  f<std::vector<double> >();            // >> is written > > 
                                        // Not necessary in C++11.
                             
}

Program: An alternative resolution of the ambiguity .
// An alternative approach: using a 'using type alias'. C++11

#include <vector>

int x = 5;

template<typename T>double f(){
  using it = typename T::iterator;      // a 'using type alias'
  it *x;                                // A simpel and plain declaration: x is of type it* 
                    

  // ...
}

int main(){
  f<std::vector<double>>();             // >> is OK in C++11
                                        
}

A vector specialization: vector<bool>
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++ Prog. Lang. (3. edition): Vector<bool>. Page 548

Reference
  • The C++ Prog. Lang. (4. edition): Vector<bool>. Page 981-982

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);
  
  for(auto be: vb) cout << be;  // 110001
}

Program: Another slightly more complicated (almost) equivalent program.
#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;

  cout << boolalpha;   // Use a stream manipulator, see The C++ PL (4ed) page 1094.

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


Algorithms

Documentation of the algorithms library
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 Contents Index
References 

The C++11 Standard Library contains approximately 80 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++ Prog. Lang. (3. edition)

Reference
  • The C++ Prog. Lang. (3. edition): Page 508

Reference
  • The C++ Prog. Lang. (4. edition): Page 927

  • Nonmodifying sequence algorithms

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

    • find(): Find the first element that compares equal to a given value. Return iterator to element

    • find_if(): 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

  • Sorting and searching algorithms (on sequences):

    • 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_permutation and prev_permutation: Systematic creation of permutations of a sequence

    • Numeric algorithms

      Principles used for algorithms
      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, §19.2.2 (4ed)

          • In part, due to the lack of lambda expressions until C++11

      • 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

      • The time complexities of the algorithms are specified by the C++ standard

      Reference

      The for-each algorithm
      Slide Contents Index
      References 

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

      C++11 has introduced the 'range-for loop' similar to foreach in C#

      Program: A possible implementation of the for-each algorithm.
      // A possible definition of the for_each function template. 
      template <typename InputIt, typename Function>
      Function for_each(InputIt first, InputIt last, Function f){
        while (first != last) f(*first++);      // Notice the use of operator() on f 
        return f;
      }

      Reference

      Program: Implementation and sample use of for-each on an C-style array.
      // A reproduction of the for-each algorithm, and a sample use on a C-style array.
      
      #include <iostream>
      #include <string>
      
      // A possible definition of the for_each function template. 
      template <typename InputIt, typename Function>
      Function for_each(InputIt first, InputIt last, Function f){
        while (first != last) f(*first++);      // Notice the use of operator() on f 
        return f;
      }
      
      void print_element(const 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+3, print_element);  // 7, 9, 8
      
        std::cout << std::endl;
      
        // Same with a lambda expression.
        for_each(a, a+3, [](const int &el){std::cout << el << std::endl;}); // 7, 9, 8
      }

      Program: Implementation and sample use of for-each on a list of integers.
      // Same defintion of for-each. Use of the algorithm on a list of integers: list<int>.
      
      #include <iostream>
      #include <string>
      #include <list>
      
      // A possible definition of the for_each function template. 
      template <typename InputIt, typename Function> Function for_each(InputIt first, InputIt last, Function 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
      }

      Program: Use of std::for-each instead of our own definition of for-each.
      // Use the Standard Libaray for-each instead of your own version of it.
      
      #include <iostream>
      #include <string>
      #include <list>
      #include <algorithm>
      
      void print_element(int i){
        std::cout << i << std::endl;
      }
      
      int main(){
        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:
        std::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 is returned.

          • Later we will see an example where this is convenient

      Function objects
      Slide Contents Index
      References 

      A function object (or function-like object or functor) is an object for which an application operator, operator(), has been defined

      A function object can be called - pretending that it is a function

      Reference
      • The C++ Prog. Lang. (3. edition): Page 514-515, 287

      Reference
      • The C++ Prog. Lang. (4. edition): Page 80-82, 551

      Reference

      Program: Class Point with overloadings of the application operator.
      // Class Point becomes a function object, because it can be called as a function.
      // Class Point with two overloads of the function call operator, 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 funny Point application operators.
      // Member definitions for class Point, including the definition of the funny Point function call 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.
      // Sample uses of the Point function call operators.
      
      #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();
        Point(double);
        Point(double, double);
      
        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.
      // Definition of class Point members - including the call operator that accesses x or y.
      
      #include <cmath>
      #include <iostream>
      #include "point.h"
      
      Point::Point(): x{0.0}, y{0.0}{
      }
      
      Point::Point(double x_coord): x{x_coord}, y{0}{
      }
      
      
      Point::Point(double x_coord, double y_coord): x{x_coord}, y{y_coord}{
      }
      
      
      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.
      // Sample uses of the operator()(int).
      
      #include <iostream>
      #include <string>
      #include "point.h"
      
      int main(){
        using namespace std;
      
        Point p,
              q(1),                           // less confusing if {} initializer
              r(3,4);                         // syntax is used here 
      
        try{
          cout << "p(1): " << p(1) << endl;   // 0
          cout << "p(2): " << p(2) << endl;   // 0
      
          cout << "q(1): " << q(1) << endl;   // 1
          cout << "q(2): " << q(2) << endl;   // 0
      
          cout << "r(1): " << r(1) << endl;   // 3
          cout << "r(2): " << r(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 Contents Index
      References 

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

      Reference

      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   -  adapted from www.cplusplus.com
      
      #include <iostream>     // std::cout
      #include <algorithm>    // std::sort
      #include <vector>       // std::vector
      
      template<typename Cont> void print_container(Cont c); 
      
      bool myfunction (int i,int j) { return (i<j); }
      
      struct myclass {
        bool operator() (int i,int j) { return (i<j);}
      };
      
      int main () {
        int myints[] = {32,71,12,45,26,80,53,33};
        std::vector<int> myvector (myints, myints+8);               
        print_container(myvector);                                  // 32 71 12 45 26 80 53 33
      
        // using default comparison (operator <):
        std::sort(myvector.begin(), myvector.begin()+4);           
        print_container(myvector);                                  // (12 32 45 71)26 80 53 33
      
        // using function for comparison:
        std::sort(myvector.begin()+4, myvector.end(), myfunction); 
        print_container(myvector);                                  // 12 32 45 71(26 33 53 80)
      
        // using an object of type myclass for comparison:
        std::sort(myvector.begin(), myvector.end(), myclass{});     
        print_container(myvector);                                  // 12 26 32 33 45 53 71 80
      
        // using a lambda expression for comparison - descending order!
        std::sort(myvector.begin(), myvector.end(), 
                   [](const int &i, const int &j){return j < i;});    
        print_container(myvector);                                  // 80 71 53 45 33 32 26 12
      
        return 0;
      }
      
      template<typename Cont> void print_container(Cont c){
        for(auto el: c) std::cout << ' ' << el;
        std::cout << std::endl;
      }

      Program: Program output.
       32 71 12 45 26 80 53 33
       12 32 45 71 26 80 53 33
       12 32 45 71 26 33 53 80
       12 26 32 33 45 53 71 80
       80 71 53 45 33 32 26 12

      An example of for-each and function objects
      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 (2003), page 337-338. Slightly revised. Rather tricky.
      
      #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){    // Called for each item in the list.
          if (first_time)                   // If two elements out of order is met, sorted becomes false.
            first_time = false;
          else if (item < prev_item)        // two elements out of order.
            sorted = false;
          prev_item = item;
        }
      
        operator bool(){return sorted;}
      };
      
      int main(){
        using namespace std;
      
        // Make a list with some elements:
        list<int> lst{3, 15, 9, 11, 13, 15, 21};
      
        // Make an instance of the class IsSorted:
        Is_sorted<int> is_sorted{};  
      
        // Use for_each to find out if lst is sorted:
        if(for_each(lst.begin(), lst.end(), is_sorted))   // for_each returns the object is_sorted
          cout << "The list lst is sorted" << endl;       // via the boolean conversion operator.
        else
          cout << "The list lst is NOT sorted" << endl;   // The given list is not sorted.
      }

      • 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{3, 15, 9, 11, 13, 15, 21};
      
        if(adjacent_find(lst.begin(), lst.end(), greater<int>{}) != lst.end())    // find a pair of elements out of order.
          cout << "The list lst is NOT sorted" << endl;                           // greater is shown in the next program.
        else
          cout << "The list lst is sorted" << endl;
      }

      • Observation

        • greater is a wrapper around the > operator, §33.4 (4ed)

      Program: Possible definitions of 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 Contents Index
      References 

      Operators are not functions - operators need some wrapping to be applicable as function parameters to algorithms.

      Binders, Adapters and Negaters.

      Reference
      • The C++ Prog. Lang. (3. edition): Page 518

      Reference
      • The C++ Prog. Lang. (4. edition): Page 966 ff.

      • Wrapping operator predicates

        • Predicates such as ==, < and >

        • Available as equal_to, less, and greater - see §33.4 (4ed)

      • Wrapping arithmetic operators

        • Operators such as + and -

        • Available as plus and minus, see §33.4 (4ed)

      • Binding one argument of a two argument function

        • Currying as of functional programming

      • Allowing a member function to be used as a function

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

      • Negating a predicate

        Adapter examples
        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;
        
          // We make a list of doubles, and insert some numbers in the list:
          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.
        // Notice that the struct plus is derived from binary_function (inheritance).
        // binary_function 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 rather direct and more 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: Yet another alternative where a lambda expression is used.
        // We show how a lambda expression can be used instead.
        
        #include <iostream>
        #include <list>
        #include <numeric>     // accumulate
        #include <functional>  // binary_function
        
        int main(){
          std::list<double> lst;
          for(int i = 1; i <= 10; i++) lst.push_back(i);   // 1, 2, ..., 10
        
          // We can also supply a lambda expression.
          double res = std::accumulate(lst.begin(), lst.end(), 0.0, 
                                       [](const double& d, const double& e){return d + e;});
        
          std::cout << "The plus accumulation is: " << res << std::endl;       // 55
        }

        Program: Illustration of member function adaptions.
        // A new example: 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();
        };


        Generic Programming and Metaprogramming

        What is generic programming in C++?
        Slide Contents Index
        References 

        Generic programming in C++ emphasizes programming of algorithms at a high abstraction level using templates

        Reference
        • The C++ Prog. Lang. (4. edition): Page 700

        • A programming paradigm - or a design philosophy

          • A generic program will work on a number of different types, which are not related by subtype relationships

          • Generic programming emphasizes requirements on arguments

        • Lifting

          • Generalizing one or more concrete functions as a single algorithm

          • Typically with use of type parameters - templates

          • Without sacrificing efficiency

        • Compile time duck typing

          • Assuming requirements on the type arguments

        • Using the idea of concepts (§24.3, 4ed)

          • The template's requirements for its type arguments

            • Expressed with a type predicate

            • In terms of a static_assert - for improved error messages

        Reference

        What is metaprogramming in C++?
        Slide Contents Index
        References 

        Metaprogramming in C++ emphasizes compile time computations that yields types or functions

        C++ offers compile time functional programming

        Reference
        • The C++ Prog. Lang. (4. edition): Page 779-781

        Reference

        • constexpr in C++11

          • Possible compile time calculations

        • Type functions

          • Calculation of types at compile time

          • Type returning functions

        • Support of selection - in between types

          • "Compile Time if-else"

        • Support of iteration

          • Via recursion

        • Other names for metaprogramming

          • Two-level programming, generative programming, template metaprogramming

        A metaprogram is a compile time computation yielding types or functions to be used at run time (§28.1, 4ed)

        What is metaprogramming used for in C++?
        Slide Contents Index
        References 

        Example of use cases for the C++ metaprogramming facilities

        • Optimization

          • Precomputations at compile time

        • Program configuration at compile time

          • Calculating sizes and limits of data structures

            • May lead to the need of functions and abstraction

          • Computations on types

          • Computations on functions

          • Conditional declaration

        • Assertions at compile time

        C++ is not strong in the area of traditional program reflection

        Types cannot be accessed at run time - types are not first class objects

        Static assert
        Slide Contents Index
        References 

        static_assert is checked at compile time, whereas assert from <cassert> is checked at run time

        If static_assert fails, a compiler error message will appear

        Program: Static assert about the size of int.
        // In p1.cc   Does not compile on my laptop, because sizeof(int) is 4.
        
        #include <iostream>
        #include <string>
        
        static_assert(sizeof(int)==8, "Assuming that 8 bytes are used for int");
        
        int main(){
        }

        Program: Compilation of p1.cpp.
        $ g++ p1.cc -std=c++11
        p1.cc:4:1: error: static assertion failed: Assuming that 8 bytes are used for int
         static_assert(sizeof(int)==8, "Assuming that 8 bytes are used for int");
        
        $ 

        Program: Static asserts abstracted in constexpr function.
        // In p4.cc   Does not compile on my laptop, float is not void or integral.
        
        #include <iostream>
        #include <string>
        #include <type_traits>
        
        template<class T>
        constexpr bool void_or_integral(){
          return std::is_void<T>::value || std::is_integral<T>::value;
        }
        
        static_assert(void_or_integral<float>(), "Expected void or integral");
        
        int main(){
        }

        Program: Compilation of p4.cpp.
        $ g++ p4.cc -std=c++11
        p4.cc:12:1: error: static assertion failed: Expected void or integral
         static_assert(void_or_integral<float>(), "Expected void or integral");
        
        $

        Reference

        Program: An example a static_assert in a template user specialization program.
        // Illustrates a static_assert on top of the template specialization stuff.
        // Compiles, meaning that the static assert holds (in this program at least).
        
        #include <iostream>
        #include <string>
        #include <type_traits>
        
        template <typename S, typename T> class A{               // The primary template class
          public: 
            int a;
            S s;
            T t;
            A() : a{1}, s{}, t{} {};
        };
        
        template<> class A <int, std::string> {                  // Complete specialization to S = int, T = string
          public: 
            int a;
            int s;
            std::string t;
            A() : a{2}, s{}, t{}{};
        };
        
        template<typename S, typename T> class A <S*, T*> {      // Partial Specialization to pointers
          public: 
            int a;
            S s;
            T t;
            A() : a{3}, s{}, t{}{};
        
            static_assert(!std::is_pointer<S>::value, "S is not (normally) expected to be a pointer type");
        };
        
        template<typename T> class A <T, T> {                    // Partial specialization: T and S are the same types
          public: 
            int a;
            T s;
            T t;
        
            A() : a{4}, s{}, t{}{};
        };
        
        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>
        
          std::cout << a1.a << std::endl;   // 1
          std::cout << a2.a << std::endl;   // 2
          std::cout << a3.a << std::endl;   // 3
          std::cout << a4.a << std::endl;   // 4
        
        }

        Exercise 6.2. Working with static_assert

        In this program on the accompanying slide the static_assert holds.

        In main, enforce a couple of other template instantiations that will cause the static_assert to fail.

        There is a lot of useful type functions in <type_traits> - see The C++ Prog. Lang. (4. edition) page 1018 - which can be used in static_assert

        Type functions
        Slide Contents Index
        References 

        Type functions accept or return C++ types

        Some sample type functions are listed below - see Section 35.4 of The C++ Prog. Lang. (4. edition) for a comprehensive listing

        Reference
        • The C++ Prog. Lang. (4. edition): Type functions. Page 1018

        • Type predicates, such as

          • is_floating_point<X>

          • is_pointer<X>

          • is_lvalue_reference<X>

          • is_rvalue_reference<X>

          • is_class<X>

          • is_fundamental<X>

          • is_polymorphic<X>

          • is_abstract<X>

        • Type relations, such as

          • is_same<X,Y>

          • is_base_of<X,Y>

        • Type valued functions, such as

          • remove_pointer<X>

          • remove_reference<X>

          • add_lvalue_reference<X>

        Program: Illustration of of type functions in a number static assertions - all of which hold.
        // Compiles without errors, meaning that all the static_asserts hold.
        
        #include <iostream>
        #include <string>
        #include <type_traits>
        
        class D {};
        
        class E{
          public: 
            virtual void vf(){};
        };
        
        int main(){
          int a;
          int &b = a;
          int *c = &a;
          D d;
          E *ep;
        
          std::remove_pointer<decltype(ep)>::type f;   // Corresponds to     E f;
          f.vf();   // OK, because the type of f is E.
        
          static_assert(std::is_integral<decltype(a)>::value, "type of a is expected to be integral");
        
          static_assert(std::is_fundamental<decltype(a)>::value, "type of a is expected to be a fundamental type");
        
          static_assert(std::is_reference<decltype(b)>::value, "type of b is expected to be a reference");
        
          static_assert(std::is_lvalue_reference<decltype(b)>::value, "type of b is expected to be a lvalue reference");
        
          static_assert(!std::is_rvalue_reference<decltype(b)>::value, "type of b is NOT expected to be a rvalue reference");
        
          static_assert(std::is_pointer<decltype(c)>::value, "type of c is expected to be a pointer");
        
          static_assert(std::is_class<decltype(d)>::value, "type of d is expected to be a class");
        
          static_assert(std::is_polymorphic<E>::value, "E is expected to be polymorphic - it has a virtual function");
        
          static_assert(std::is_polymorphic<std::remove_pointer<decltype(ep)>::type>::value, 
                        "ep (without ptr) is expected to be polymorphic");
        
        }

        Reference

        Constant expressions in C++11
        Slide Contents Index
        References 

        A constant expression - constexpr - can be evaluated at compile time, as well as run-time - a C++11 feature

        In contrast, const means immutable - cannot be modified at run-time.

        Reference
        • The C++ Prog. Lang. (4. edition): Page 42-43, 262-264, 311-313

        Reference
        • Effective Modern C++: Use constexpr whenever possible. Item 15

        Reference

        • constexpr

          • Expressive power:

            • Integers, floating-point, and enumeration values

            • Any operator that does not modify a program state

            • Literal types - structs, or classes with a consexpr constructor

            • constexpr functions - pure functions - (relaxed in C++14)

              • Single return

              • No loops, no local variables, no side-effects

              • Recursion

              • Conditional expressions can be used:   - the operator ?:

        Examples of constant expressions
        Slide Contents Index
        References 

        We show a number of examples of constant expressions

        Program: Examples of constant expressions - C++11.
        // A number of examples of constant expressions (C++11).
        
        #include <iostream>
        
        constexpr int I1 = 5, I2 = 7, I3 = 9;
        constexpr int I4 = (I1 % 2 == 0) ? I2 : I3;     
        
        constexpr bool even(int n){
          return n % 2 == 0;
        }
        constexpr int I5 = even(I1) ? I2 : I3;           // Eqvivalent to I4
        
        constexpr long int fac(int n){
         return (n == 0) ? 1 : n * fac(n - 1);
        }
        constexpr long int FAC5 = fac(5);
        constexpr long int FAC10 = fac(10);
        
        constexpr long int fib(int n){
          return (n == 0) ? 0 : (n == 1) ? 1 : fib(n - 1) + fib(n - 2);
        } 
        constexpr long int FIB20 = fib(20);
        
        // int i3 = 3;
        // constexpr int I6 = (I1 % 2 == 0) ? I2 : i3;   // Error: i3 is not a const, and not a constexpr
        
        int main(){                                      // In order to check the results from about (at run time).                        
          using namespace std;    
           
          cout << I1 << " " << I2 << " " << I3 << endl;  // 5 7 9
          cout << I4 << endl;                            // 9
          cout << I5 << endl;                            // 9
          cout << FAC5  << endl;                         // 120
          cout << FAC10 << endl;                         // 362800
        
          int i = 10;
          cout << fac(i) << endl;                        // 362800 - fac can also be called at run time.
        
          cout << FIB20 << endl;                         // 6765
        }

        Program: The same program - with results statically asserted.
        // The same examples again, with static_assert's of results (instead of output at run time).
        // Compiles without errors, with   g++ constexpr-1-statass.cpp -std=c++11 -c
        // This means that all asserted results are correctly computed at compile time.
        
        #include <iostream>
        
        constexpr int I1 = 5, I2 = 7, I3 = 9;
        constexpr int I4 = (I1 % 2 == 0) ? I2 : I3;     
        
        constexpr bool even(int n){
          return n % 2 == 0;
        }
        constexpr int I5 = even(I1) ? I2 : I3;           // Eqvivalent to I4
        static_assert(I5==I3, "Expected: I5=I3");
        
        constexpr long int fac(int n){
         return (n == 0) ? 1 : n * fac(n - 1);
        }
        constexpr long int FAC5 = fac(5);
        static_assert(FAC5==120, "Expected: FAC5 is 120");
        constexpr long int FAC10 = fac(10);
        static_assert(FAC10==3628800, "Expected: FAC10 is 362800");
        
        constexpr long int fib(int n){
          return (n == 0) ? 0 : (n == 1) ? 1 : fib(n - 1) + fib(n - 2);
        } 
        constexpr long int FIB20 = fib(20);
        static_assert(FIB20==6765, "Expected: FIB20 is 6765");

        Program: Evaluation of constexpr at run-time - C++11.
        // Illustrates that constexpr functions can be evaluated at run-time as well.
        
        #include <iostream>
        
        constexpr long int fib(int n){
          return (n == 0) ? 0 : (n == 1) ? 1 : fib(n - 1) + fib(n - 2);
        } 
        
        constexpr long int fac(int n){
         return (n == 0) ? 1 : n * fac(n - 1);
        }
        
        int main(){
          using namespace std;
        
          int i;
          cout << "Enter an integer: ";
          cin >> i;
          cout << "Fib(i): " << fib(i) << " fac(i): " << fac(i) << endl;
        }

        Program: Relaxed constexpr in C++14.
        // Constexpr as of C++14. Not yet compilable in g++. Due in gcc version 5.
        
        #include <iostream>
        constexpr long int fib(int n){
          int a = 0, b = 1, tmp;
          for(int i = 1; i <= n; ++i){
            tmp = a; a = b; b = tmp + b;
          }
          return a;
        } 
        
        constexpr long int fac(int n){
          int res = 1;
          for(int i = 1; i <= n; ++i)
            res = res * i;
          return res;
        }
        
        int main(){
          using namespace std;
        
          constexpr int FAC5 = fac(5);
          constexpr int FIB10 = fib(10);
        
          cout << "FAC5 " << FAC5 << "   FIB10: " << FIB10 << endl;
        }

        Program: Examples of a literal type, struct Point - C++11.
        // Illustrates a struct Point - a literal type -  with constexpr member functions.
        
        #include <iostream>
        #include <string>
        
        struct Point {     // A literal type 
          double x, y;
          constexpr double getx () {return x;}
          constexpr double gety () {return y;}
          constexpr Point move(double dx, double dy){return Point{x + dx, y + dy};}
        };
        
        
        // Points handled at compile-time - the last is an array of points:
        constexpr Point origo {0,0};
        constexpr Point  p1 = origo.move(3.1, 4.2);
        constexpr Point pa[] = {origo, p1, p1.move(0.9, -0.2)};
        
        int main(){
          using namespace std;
        
          cout << "(" << origo.getx() << "," << origo.gety() << ")" << endl;  // (0,0)
          cout << "(" <<    p1.getx() << "," <<    p1.gety() << ")" << endl;  // (3.1, 4.2)
        
          for(auto p: pa)
            cout << "(" <<    p.getx() << "," <<    p.gety() << ")" << endl;  // (0,0) (3.1, 4.2) (4,4)
        }

        Program: The same program - with results statically asserted.
        // Same as above, but with static_asserts that check for correct results.
        // Compiles, and therefore all static_asserts hold. 
        // Compile with:  g++ constexpr-2-statass.cpp -std=c++11 -c
        
        #include <iostream>
        #include <string>
        
        struct Point {     // A literal type 
          double x, y;
          constexpr double getx () {return x;}
          constexpr double gety () {return y;}
          constexpr Point move(double dx, double dy){return Point{x + dx, y + dy};}
        };
        
        // Points handled at compile-time - the last is an array of points:
        constexpr Point origo {0,0};
        static_assert(origo.x==0 && origo.y == 0, "Expected: Origo at (0,0)");
        
        constexpr Point  p1 = origo.move(3.1, 4.2);
        static_assert(p1.x==3.1 && p1.y == 4.2, "Expected: p1 at (3.1, 4.2)");
        
        constexpr Point pa[] = {origo, p1, p1.move(0.9, -0.2)};
        
        constexpr bool pa_is_OK(const Point pa[3]){
          return pa[0].x == 0 && pa[0].y == 0 &&
                 pa[1].x == 3.1 && pa[1].y == 4.2 &&
                 pa[2].x == 3.1+0.9 && pa[2].y == 4.2-0.2;
        }
        
        static_assert(pa_is_OK(pa), "expected: pa is as expected...");

        Program: Examples of class Circle with a constexpr constructor - C++11.
        // Illustrates class circle with aconstexpr constructors and constexpr member functions.
        // Compiles without errors.
        
        #include <iostream>
        
        constexpr double square(double x){
          return x * x;
        }
        
        constexpr double PI = 3.14159;
        
        class Circle {
          private:
            double cx, cy;
            double radius;
        
          public:
            constexpr Circle(double x, double y, double r) : cx{x}, cy{y}, radius{r}{
            }
        
            constexpr Circle(const Circle& c) : cx(c.cx), cy(c.cy), radius(c.radius){
            }
        
            constexpr double area(){
              return square(radius) * PI;
            }
        
            constexpr Circle move(double dx, double dy){
              return Circle(cx+dx, cy+dy, radius);
            }
        
            constexpr double x(){return cx;}
            constexpr double y(){return cy;}
            constexpr double r(){return radius;}
        };
        
        // Compile time use of class circle:
        constexpr Circle C1{1.1, 2.2, 4.0},
                         C2 = C1.move(0.9, 0.8);
        
        constexpr double C1_Area = C1.area();
        static_assert(C1_Area == 4.0 * 4.0 * PI, "Expected vaue of C1_Areal is 4.0 * 4.0 * PI");
        // End of compile time use of class Circle.
        
        int main(){
          using namespace std;
        
          cout << "C1: " << C1.area() << endl;  // 50.2654
          cout << "C2: " << C2.area() << endl;  // 50.2654
        
        //  cout << C1.cx << " " << C1.cy << " " << C1.radius << endl;     // Error - access to private variables.
        //  cout << C2.cx << " " << C2.cy << " " << C2.radius << endl;     // Error - access to private variables.
        
          cout << C1.x() << " " << C1.y() << " " << C1.r() << endl;        // 1.1 2.2 4
          cout << C2.x() << " " << C2.y() << " " << C2.r() << endl;        // 2 3 4
        
          // Run time use of class Circle:
          Circle *pc1{new Circle(10, 20, 5)};
          Circle c2 = pc1->move(1,-1);
          Circle c3{C2};                                       // Constructing c3 based on compile time constructed C2.
          cout << "*pc1: " << pc1->x() << " " << pc1->y() << " " << pc1->r() << endl;       // *pc1: 10 20 5
          cout << "c2: " << c2.x() << " " << c2.y() << " " << c2.r() << endl;               // c2: 11 19 5
          cout << "c3: " << c3.x() << " " << c3.y() << " " << c3.r() << endl;               // c3: 2 3 4
          delete pc1;
          // End of run time use of class Circle.
        
        }

        Selection between two types
        Slide Contents Index
        References 

        Selection between types is supported by the struct conditional in <type_traits>

        We first show an example that uses conditional - after that the struct itself is studied

        Reference
        • The C++ Prog. Lang. (4. edition): Selection of types. Page 790

        Program: An sample use of conditional.
        // Conditional example - adapted from www.cplusplus.com.  Simple stuff.
        // Illustrates std::conditional and std:is_same. 
        // Ilustrates using syntax (4ed, pages 167). 
        
        #include <iostream>
        #include <type_traits>
        
        int main() {
        
          // Establish aliases for selected types:
        
          using A = std::conditional<true, int, float>::type;                         // select int
        
          using B = std::conditional<false, int, float>::type;                        // select float
        
          using C = std::conditional<std::is_integral<A>::value, long, int>::type;    // select long - because type A is int
        
          using D = std::conditional<std::is_integral<B>::value, long, int>::type;    // select int - because B is float
        
          // Use established types:
          A a{};                                                                      // A variable of type A
          B b = [](B x) -> B{return x/2;}(10.0);                                      // Use of type B in a lambda expressions, and its immediate call
        
          // Print info about types:
          std::cout << std::boolalpha;                                                // print boolean values as false and true
                                                                                      // (rather than 0 and 1)
          std::cout << "typedefs of int:" << std::endl;
          std::cout << "A: " << std::is_same<int,A>::value << std::endl;              // A: true
          std::cout << "B: " << std::is_same<int,B>::value << std::endl;              // B: false
          std::cout << "C: " << std::is_same<int,C>::value << std::endl;              // C: false
          std::cout << "D: " << std::is_same<int,D>::value << std::endl;              // D: true
        
          return 0;
        }

        Program: Same - syntactically embellished.
        // Introducing a template alias (4ed, page 694) - a slight improvement.
        // Conditional example - adapted from www.cplusplus.com. 
        
        #include <iostream>
        #include <type_traits>
        
        // Conditional is a syntactical embellishment of the application of underlying conditional template:
        template<bool B, typename T, typename F>
        using Conditional = typename std::conditional<B, T, F>::type;                       
        
        int main() {
          using namespace std;
        
          using A = Conditional<true,int,float>;                     // select int
        
          using B = Conditional<false,int,float>;                    // select float
        
          using C = Conditional<is_integral<A>::value,long,int>;     // select long - because type A is int
        
          using D = Conditional<is_integral<B>::value,long,int>;     // select int - because B is float
        
          // ...
        }

        Program: Use of my_conditional in the example from above.
        // A slightly more realistic use of type selection.
        
        #include <iostream>
        #include <type_traits>
        
        // Conditional is a syntactial embellishment of the application of underlying conditional template.
        // We are using a template alias:
        template<bool B, typename T, typename F>
        using Conditional = typename std::conditional<B, T, F>::type;                       
        
        constexpr long int LIMIT = 5000;
        
        constexpr bool large(int n){
          return n > LIMIT;
        }
        
        int main() {
          using namespace std;
        
          const long int SZ = 1234;
          using FloatingPointT = Conditional<large(SZ),double,float>;                     // select type - float is selected in this 
                                                                                          // particular context.
          FloatingPointT x = 1234.5678;
        
          cout << "sizeof(double) = " << sizeof(double) << endl;                          // 8
          cout << "sizeof(float) = " << sizeof(float) << endl;                            // 4
          cout << "sizeof(FloatingPointT) = " << sizeof(FloatingPointT) << endl;          // 4
        
          return 0;
        }

        Program: Possible definition of conditional - here as my_conditional.
        // Possible definition of conditional - here as my_conditional - in file conditional-def.cc
        // The standard library definition is in <type_traits>
        
        template<bool C, typename T, typename F>     // Template, catching all other cases than the
        struct my_conditional {                      // specialization (below).
          using type = T;
        };
        
        template<typename T, typename F>             // Template specialization, for the false branch.
        struct my_conditional <false, T, F>{
          using type = F;
        };

        Program: Use of my_conditional - in the example from above.
        // Using my_conditional instead of std:conditional, via a programmed syntactial embellishment Conditional.
        
        #include <iostream>
        #include <type_traits>
        #include "conditional-def.cc"
        
        // Conditional is a syntactial embellishment of the underlying conditional template:
        template<bool B, typename T, typename F>
        using Conditional = typename my_conditional<B, T, F>::type;                       
        
        int main() {
          using namespace std;
        
          using A = Conditional<true,int,float>;                     // select int
          using B = Conditional<false,int,float>;                    // select float
          using C = Conditional<is_integral<A>::value,long,int>;     // select long - because type A is int
          using D = Conditional<is_integral<B>::value,long,int>;     // select int - because B is float
        
          // ...
        
          return 0;
        }

        Selection between two functions
        Slide Contents Index
        References 

        Compile time selection between two functions

        Illustrated with an example from page 787 of The C++ Prog. Lang. (4. edition)

        Reference
        • The C++ Prog. Lang. (4. edition): Page 787, 791

        Program: Selection one of two functions at compile time.
        // An illustration of function objects. Very close to the program on page 787 of "The C++ Programming Language" 4ed.
        
        #include <iostream>
        #include <type_traits>
        
        // Conditional is a syntactial embellishment of the application of underlying conditional template:
        template<bool B, typename T, typename F>
        using Conditional = typename std::conditional<B, T, F>::type;    
        
        struct X{
          void operator()(int x){
            std::cout << "X: " << x << std::endl;
          }
          // ...
        };
        
        struct Y{
          void operator()(int y){
            std::cout << "Y: " << y << std::endl;
          }
          // ...
        };
        
        void f(){
          Conditional<(sizeof(int)>4), X, Y>{}(7);       // Select either X or Y depending on the value of sizeof(int)>4.
                                                         // Y is selected, instantiated, and called on 7.
          Y{}(7);                                        // Equivalent.  Y: 7
        
          using Z = Conditional<std::is_polymorphic<X>::value, X, Y>;  // X is not polymorphic, therefore Z becomes an alias of Y.
          Z zz{};  // makes an X or a Y
          zz(8);   // calls an X og a Y.     // Y: 8
        }
        
        int main(){
          std::cout << "size(int): " << sizeof(int) << std::endl;  // 4 on my laptop.
          f();
        }

        Can we do similar run time selection of functions in C++?

        Are functions first class objects in C++?

        Conditional declarations
        Slide Contents Index
        References 

        Conditional declaration can be done with enable_if

        Illustrated on the move member in class Point<C>

        Reference
        • The C++ Prog. Lang. (4. edition): enable_if. Page 795

        Program: Class Point header file - where move is only enabled for floating point types.
        // Point<C> where move is only enabled for floating point types.
        
        #include <type_traits>
        
        // One of the usual syntactical embellishments, here of enable_if. 
        template <bool B, typename T>
        using Enable_if = typename std::enable_if<B,T>::type;
        
        template<typename C>class Point {
        private: 
          C x, y;
        
        public:
          Point(C, C);
          Point();
          C getx () const;
          C gety () const;
          Enable_if<std::is_floating_point<C>::value, Point<C>>& move(C, C);   // if C is not a floating point type, 
                                                                               // the move function is not present.
          double distance_to(Point);
        };
        
        template<class C>  std::ostream& operator<< (std::ostream&, const Point<C>&);

        Program: Implementation of Point<C> members.
        // point.cc in which move is only present if C is a floating point type.
        
        #include <cmath>
        #include <iostream>
        #include "point.h"
        
        template<typename C> Point<C>::Point(C x_coord, C y_coord):
           x(x_coord), y(y_coord){
        }
        
        template<typename C> Point<C>::Point(): x(0.0), y(0.0){
        }
        
        template<typename C> C Point<C>::getx () const{
          return x;
        }
        
        template<typename C> C Point<C>::gety () const{
          return y;
        }
        
        // if C is not a floating point type, the move function is not present.
        template<typename C> Enable_if<std::is_floating_point<C>::value, Point<C>>& Point<C>::move(C dx, C dy){
          x += dx; y += dy;                                         
          return *this;
        }
        
        template<typename C> double Point<C>::distance_to(Point<C> p){
          return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));  // Similar assumptions for - and *
        }
        
        
        template<typename C> std::ostream& operator<< 
                                (std::ostream& s, const Point<C>& p){
          return s << "(" << p.getx() << "," << p.gety() << ")" ;
        }

        Program: Use of class Point<double> with move - OK.
        // Compiles and runs, because double (in Point<double>) is a floating point type.
        
        #include <iostream>
        #include <string>
        #include "point.cc"  
        
        int main(){
          Point<double> p1,
                        p2(1,2);
        
          p1.move(1,1);                // OK
          p2.move(2,2);                // OK
        
          std::cout << "p1: " << p1 << std::endl;      // (1,1)
          std::cout << "p2: " << p2 << std::endl;      // (3,4)
        }

        Program: Use of class Point with move - does not compile.
        // Does not compiles, because int (in Point<int>) is NOT a floating point type.
        
        #include <iostream>
        #include <string>
        #include "point.cc"  
        
        int main(){
          Point<int> p1,
                     p2(1,2);
        
          p1.move(1,1);      //  error: class Point<int> has no member named move
          p2.move(2,2);      //  error: class Point<int> has no member named move
        
          std::cout << "p1: " << p1 << std::endl;      // (1,1)
          std::cout << "p2: " << p2 << std::endl;      // (3,4)
        }

        Example of type function: Integer of given byte size
        Slide Contents Index
        References 

        We show how to program a type function: Integer_of_byte_size<N>

        A function from an int to some C++ integer type

        Reference
        • The C++ Prog. Lang. (4. edition): Page 781

        • A function from int to an integer type

          • Input: N (such as 0, 1, 2, 3)

          • Output: A C++ integer type, such as unsigned char or short int

        • The concrete mapping:

          • 0 is mapped to void (it is an error)

          • 1 is mapped to usigned char

          • 2 is mapped to short int

          • 3 is mapped to void (it is an error)

        Program: First version of type function.
        // Use of the Select template struct for selection anmong a number of different types.
        // Select corresponds to the switch control structure.
        
        #include <iostream>
        #include <string>
        #include "select-stuff.cc" 
        
        // Integer<N>::type is an integer type of N bytes:    (4ed, page 782)
        template<int N>
        struct Integer{
          using Error = void;
          using type = Select<N, 
                               Error,           // 0 selects Error (void)
                               signed char,     // 1 selects singed char
                               short int,       // 2 selects short int
                               Error            // 3 selects Error (void)
                             >;
                                                                  
        };
        
        
        
        
        
        
        int main(){
          using namespace std;
        
          typename Integer<1>::type i = 65;    // similar to:   unsigned char i = 10;  // 'A'
          typename Integer<2>::type j = 66;    // similar to:   short int j = 8;
        
          cout << "i: " << i << " of size: " << sizeof(i) << endl;   // i: A of size 1
          cout << "j: " << j << " of size: " << sizeof(j) << endl;   // j: 66 of size 2
        }

        Program: Second version of type function - embellished syntax of the type function.
        // Simplifying the use of Select via use of a template alias (4ed page 694).
        
        
        #include <iostream>
        #include <string>
        #include "select-stuff.cc"
        
        // Integer<N>::type is now defined as an integer type of N bytes:    (4ed, page 782)
        template<int N>
        struct Integer{
          using Error = void;
          using type = Select<N, 
                               Error,           // 0 selects Error (void)
                               signed char,     // 1 selects singed char
                               short int,       // 2 selects short int
                               Error            // 3 selects Error (void)
                             >;
                                                                  
        };
        
        // Embellish the notation  Integer<N>::type  to Integer_of_size<N>  - made by use of a template alias (4ed, 23.6).
        template<int M>
        using Integer_of_byte_size = typename Integer<M>::type;   
        
        
        int main(){
          using namespace std;
        
          Integer_of_byte_size<1> i = 65;    // similar to:   unsigned char i = 10;  // 'A'
          Integer_of_byte_size<2> j = 66;    // similar to:   short int j = 8;
        
          cout << "i: " << i << " of size: " << sizeof(i) << endl;   // i: A of size 1
          cout << "j: " << j << " of size: " << sizeof(j) << endl;   // j: 66 of size 2
        }

        Program: The ugly and bulky selection stuff.
        // Select stuff - templates that define selection of one out of four types (4ed, page 792).
        
        struct Nil {};   // A trivial Nil type
        
        // select - declared, but not defined in the general case. Only specializations are defined.
        template <int I, typename T1 = Nil, typename T2 = Nil, typename T3 = Nil, typename T4 = Nil>
        struct select;   
        
        // A using alias Select that binds unused types to Nil
        template <int I, typename T1 = Nil, typename T2= Nil, typename T3 = Nil, typename T4 = Nil>
        using Select = typename select<I, T1, T2, T3, T4>::type;
        
        // Specializations for 0-3
        template <typename T1, typename T2, typename T3, typename T4>
        struct select<0, T1, T2, T3, T4> {using type = T1;};   // Specialization for 0
        
        template <typename T1, typename T2, typename T3, typename T4>
        struct select<1, T1, T2, T3, T4> {using type = T2;};   // Specialization for 1
        
        template <typename T1, typename T2, typename T3, typename T4>
        struct select<2, T1, T2, T3, T4> {using type = T3;};   // Specialization for 2
        
        template <typename T1, typename T2, typename T3, typename T4>
        struct select<3, T1, T2, T3, T4> {using type = T4;};   // Specialization for 3

        Generalizing Select with use of a variadic template
        Slide Contents Index
        References 

        The selection shown on the previous slides is ugly - and limited to selection of one out of 4 types

        Here we illustrate a generalization of select programmed with variadic templates

        An embellishment removes a little syntactical noice

        The Integer struct is straightforward

        Reference
        • The C++ Prog. Lang. (4. edition): Variadic templates. Page 809

        Program: Yet another version of type function - generalized to selection among an arbitrary number of types.
        // The example generalized to selection based on a bytelength from 0 to 8.
        
        #include <iostream>
        #include <string>
        #include "select-stuff-general.cc"
        
        // Integer<N>::type is now defined as an integer type of N bytes:    (4ed, page 782)
        template<int N>
        struct Integer{
          using Error = void;
          using type = Select<N, 
                               Error,           // 0 selects Error (void)
                               signed char,     // 1 selects singed char
                               short int,       // 2 selects short int
                               Error,           // 3 selects Error (void)
                               int,             // 4 selects int
                               Error,           // 5 selects Error (void)
                               Error,           // 6 selects Error (void)
                               Error,           // 7 selects Error (void)
                               long long int    // 8 selects long long int
                             >;
                                                                  
        };
        
        
        // Embellish the notation  Integer<N>::type  to Integer_of_size<N>  - made by use of a template alias (4ed, 23.6).
        template<int M>
        using Integer_of_byte_size = typename Integer<M>::type;   
        
        
        int main(){
          using namespace std;
        
        
          Integer_of_byte_size<1> i = 65;    // similar to:   unsigned char i = 10;  // 'A'
          Integer_of_byte_size<2> j = 66;    // similar to:   short int j = 66;
          Integer_of_byte_size<4> k = 67;    // similar to:   int k = 67;
          Integer_of_byte_size<8> l = 68;    // similar to:   long int l = 68;
        
          cout << "i: " << i << " of size: " << sizeof(i) << endl;   // i: A of size 1
          cout << "j: " << j << " of size: " << sizeof(j) << endl;   // j: 66 of size 2
          cout << "k: " << k << " of size: " << sizeof(k) << endl;   // k: 67 of size 4
          cout << "l: " << l << " of size: " << sizeof(l) << endl;   // l: 68 of size 8
        }

        Program: General selection stuff - shorter and more elegant - using variadic templates (C++11).
        // Select stuff - templates that define selection in the general case (4ed, page 792).
        // Uses variadic templates (4ed, 809). C++11.
        
        // select - declared, but never instantiated. The specialization below will be instantiated
        template<unsigned int N, typename... Types>
        struct select;
        
        
        // Specialization that just recurses in the base type:
        template <unsigned int N, typename T, typename... Types>   
        struct select<N, T, Types...>: select<N-1, Types...>{
        };
        
        // Specialization that represent the base case of the recursion.
        // Defines what type stands for: 
        template<typename T, typename... Types>
        struct select<0, T, Types...>{
          using type = T;
        };
        
        
        // A using alias Select that embellish the use of select - as before:
        template <unsigned int N, typename... Types>
        using Select = typename select<N, Types...>::type;

        Compile Time iteration
        Slide Contents Index
        References 

        Compile Time iteration takes place via recursion

        There is no variable state at compile time

        Iterative control structures are therefore not applicable

        Program: The factorial function defined as a constexpr function (C++11).
        // Factorial defined as a constexpr function definition.  (4ed page 793).
        // A function that can be use by the compiler, as well as on run time.
        // C++11
        
        #include <iostream>
        
        constexpr int fac(int i){
          return (i <= 0) ? 1 : i * fac(i - 1);
        }
        
        // compile-time test cases:
        static_assert(fac(5)==120,      "fac(5)  problem");
        static_assert(fac(10)==3628800, "fac(10) problem");
        
        int main(){
          using namespace std;
        
          // CALL OF fac AT COMPILE TIME:
          constexpr int res = fac(10);
          cout << "fac(10) = " << res << endl;      // fac(10) = 3628800
          cout << "fac(5) = " << fac(5) << endl;    // fac(5) = 120
        
          // CALL OF fac AT RUN TIME:
          int i;
          cout << "Enter i: ";
          cin >> i;
          cout << "fac(2*i) " << fac(2*i) << endl;  // Depends in user input of i
        }

        Program: The factorial function defined as a function template - using a template int parameter.
        // Factorial defined as a function template (4ed page 793).
        // The input N is a templates parameter.
        // C++11
        
        #include <iostream>
        
        template<int N>
        constexpr int fac(){
          return N * fac<N-1>();
        }
        
        template<>                  // A specialization for N = 1 
        constexpr int fac<1>(){
          return 1;
        }
        
        
        int main(){
          using namespace std;
        
          // call of fac at compile time:
          constexpr int res = fac<10>();
          static_assert(res==3628800, "Value of fac<10> is incorrect");
         
          cout << "fac(10) = " << res << endl;        // fac(10) = 3628800
          cout << "fac(5) = " << fac<5>() << endl;    // fac(5) = 120
        
          // attempt to call of fac at run time - not possible, however:
          int i;
          cout << "Enter i: ";
          cin >> i;
          cout << "fac(2*i) " << fac<2*i>() << endl;  // Compile time error: 
                                                      // the value of 'i' is not usable in a constant expression
        }

        Program: The factorial function programmed in struct - with recursion.
        // Factorial defined as a static int member in a struct. 
        // Can only be used a compile time
        // Does not rely on C++11 facilities.
        
        #include <iostream>
        
        // Defining and holding the factorial value in a static int member.
        template<int N>
        struct Fac{
          static const int value = N * Fac<N-1>::value;
        };
        
        template<>                  // A specialization for N = 1 
        struct Fac<1>{
          static const int value = 1;
        };
        
        
        int main(){
          using namespace std;
        
          // Call of fac at compile time:
          const int res = Fac<10>::value;
          cout << "fac(10) = " << res << endl;             // fac(10) = 3628800
          cout << "fac(5) = " << Fac<5>::value << endl;    // fac(5) = 120
        
          // Fac cannot be called with run time input.
        }

        More compile time computations - older stuff
        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++ Prog. Lang. (3. edition)


        Collected references
        Contents Index
        The C++ Prog. Lang. (3. edition): Page 57, 550
        The C++ Prog. Lang. (4. edition): Page 103, 953
        Collections in C#
        The iterator design pattern
        The C++ Prog. Lang. (3. edition): Page 551, 553, 557, 561
        The C++ Prog. Lang. (4. edition): Page 953
        The C++ Prog. Lang. (3. edition): Page 550
        The C++ Prog. Lang. (4. edition): Page 955
        Iterator categories at cplusplus.com
        The C++ Prog. Lang. (3. edition): Page 555
        The C++ Prog. Lang. (4. edition): Page 963
        insert_iterator at cplusplus.com
        The C++ Prog. Lang. (3. edition): Page 52-56
        The C++ Prog. Lang. (4. edition): Page 101
        Vectors in C++
        The C++ Prog. Lang. (4. edition): array. Page 974
        array at cplusplus.com - C++11
        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
        forward_list at cplusplus.com
        list at cplusplus.com
        vector at cplusplus.com
        The C++ Prog. Lang. (3. edition): Page 441
        C# counterpart - Collection class hierarchy
        The C++ Prog. Lang. (3. edition): Page 478
        The C++ Prog. Lang. (4. edition): Page 923
        Stream state
        The C++ Prog. Lang. (3. edition): Page 443, 462
        The C++ Prog. Lang. (4. edition): Page 896
        The C++ Prog. Lang. (4. edition): using type alias. Page 167
        The C++ Prog. Lang. (3. edition): Vector<bool>. Page 548
        The C++ Prog. Lang. (4. edition): Vector<bool>. Page 981-982
        The C++ Prog. Lang. (3. edition): Page 508
        The C++ Prog. Lang. (4. edition): Page 927
        Example: binary_search
        C Operator priorities
        The C++ Prog. Lang. (3. edition): Page 514-515, 287
        The C++ Prog. Lang. (4. edition): Page 80-82, 551
        Lambda expressions
        sort at cplusplus.com
        The C++ Prog. Lang. (3. edition): Page 518
        The C++ Prog. Lang. (4. edition): Page 966 ff.
        The C++ Prog. Lang. (4. edition): Page 700
        static_assert
        The C++ Prog. Lang. (4. edition): Page 779-781
        constexpr
        Specialization of class templates - complete and partial
        The C++ Prog. Lang. (4. edition): Type functions. Page 1018
        decltype
        The C++ Prog. Lang. (4. edition): Page 42-43, 262-264, 311-313
        Effective Modern C++: Use constexpr whenever possible. Item 15
        Constants
        The C++ Prog. Lang. (4. edition): Selection of types. Page 790
        The C++ Prog. Lang. (4. edition): Page 787, 791
        The C++ Prog. Lang. (4. edition): enable_if. Page 795
        The C++ Prog. Lang. (4. edition): Page 781
        The C++ Prog. Lang. (4. edition): Variadic templates. Page 809
        The math behind the quick power function

         

        Chapter 6: The Standard Library and Metaprogramming
        Course home     Author home     About producing this web     Previous lecture (top)     Next lecture (top)     Previous lecture (bund)     Next lecture (bund)     
        Generated: August 1, 2017, 13:31:59