Tricky basics


Dependent name
==============


The keyword typename was introduced into C++ during the standardization
to clarify that an identifier inside a template is a type (or not).


template <typename T>
class MyClass
{
   typename T::SubType * ptr;
   //...
};


Without the typename, the name SubType would be considered as a static member.
Thus it would be a concrete variable or object. As a result, the expression:


  T::SubType * ptr


would be a multiplication. In general, typename has to be used whenever
a name depends on a template type.

There is may apperance of this situation in STL, like:


  typename T::const_iterator pos;



Two phase lookup and Using "this"
================================


For class templates with base classes, using a name x by itself is not
always equivalent to this->x, even though a member x is inherited:


#include <iostream>

void bar()
{
  std::cout << "::bar()" << std::endl;
}

template <typename T>
class Base
{
public:
    void bar() { std::cout << "Base::bar()" << std::endl; }
};

template <typename T>
class Derived : public Base<T>
{
public:
    void foo() { bar(); }       // calls external bar() or error !!
};

int main()
{
    Derived<int> d;
    d.foo();
    return 0;
}




$ ./a.out
::bar()



template <typename T>
class Derived : public Base<T>
{
public:
    void foo() { this->bar(); }       // calls Base::bar()
};



$ ./a.out
Base::bar()





Template template parameters
============================



It can be usefull to allow a template parameter itself to be a class template.


std::stack< int, std::vector<int> > vstack;


It would be nice to write it in the following simplified form:


std::stack< int, std::vector> vstack;


To provide it, let us define the stack in the following way:


template <typename T,
   template <typename ELEM> class CONT = std::deque>
class stack
{
protected:
	CONT<T> c;
	//...
};


What is the difference? In the second form, the second template parameter
is declared as being a class template. The default value has changed from
std::deque<T> to std::deque. This parameter has to be a class template,
which is instantiated for the type that is passed as the first template
parameter.



Explicit call of default constructor
====================================


The fundamental types, like int, double, etc. has no default constructor.
To ensure initialization of such values as template parameters, we can use
the explicit call of constructor.


template<typename T>
void foo()
{
    T x = T();
    // ...
}


To make sure, that this happens with the subobjects to, you should use
the initializer list of the constructor:


template<typename T>
class MyClass
{
public:
    MyClass() : x() {}
private:
    T x;
};



Mixins
======


This is mixin in C++ terminology (back to Jannis Smaragdakis et.al)
In Scala, mixin is completely different.



// Mixin

template <class Base>
class Mixin : public Base  { ... };

class Base { ... };



The interesting thing is, that in normal object-oriented style base is
always implemented before derived. Here we can implement inheritance
delaying the definition of the base.


//
//  suppose Graph has succ_node() and succ_edge()
//
template <class Graph>
class Counting : public Graph
{
public:
    Counting() : nodes_visited(0), edges_visited(0)  { }
    node succ_node( node v)
    {
        ++nodes_visited;
        return Graph::succ_node(v);
    }
    node succ_edge( node v)
    {
        ++edges_visited;
        return Graph::succ_edge(v);
    }
private:
    int nodes_visited;
    int edges_visited;
};

Counting< Ugraph >  counted_ugraph;
Counting< Dgraph >  counted_dgraph;




Mixin issues
============


Be care with the lazy instantiation:


//
//  be care with lazy instantiation
//
template <class Sortable>
class WontWork : public Sortable
{
public:
    void sort(X x)
    {
        Sortable::srot(x);  // !!misspelled
    }
};

WontWork w;


If the client never calls w.sort there is no error message!




Liskov substitutional principle
===============================


In 1977 Barbara Liskov defined her substitutional principle: an object
from the subtype can appear in every place where its supertype's objects
can. That is one of the most fundamental rule in object-orientation:
a derived object can appear everywhere the base object can.


The problem is, that mixins look like subtypes, but they behave differently..


class Base { ... };
class Derived : public base { ... };

template <class T> class Mixin : public T { ... };

Base        b;
Derived     d;

Mixin<Base>     mb;
Mixin<Derived>  md;

b  = d      // OK
mb = md;    // Error!



Typical usage:
std::shared_ptr<Base>    bp;
std::shared_ptr<Derived> dp;

bp = dp;  // ok, because of templated copy operations only





The Curiously Recurring Template Pattern (CRTP)
===============================================



// The Curiously Recurring Template Pattern (CRTP)
template <typename T>
struct Base
{
    // ...
};

struct Derived : Base<Derived>
{
    // ...
};




Static polymorphism
===================


template <class Derived>
struct base
{
    void interface()
    {
         // ...
         static_cast<Derived*>(this)->implementation();
         // ...
    }
};

struct derived : base<derived>
{
     void implementation();
};





Explicite Template Instantiation
================================


Templates are instantiated in a lazy way: only those fnctions will
be generated which are eplicitelly called.

This default rule can be overruled be the explicite instantiation.


template<typename T>
void print(const T& ) { ... }

template<typename T>
class MyClass
{
	// ...
};

template void print<int>(const int &);	// generate print<int>

template MyClass<double>::MyClass();	// generate constructor 

template class MyClass<long>;		// generate the whole class




Extern templates (since C++11)
==============================


see more details in: [N1448==03-0031] Mat Marcus and Gabriel Dos Reis:
Controlling Implicit Template Instantiation.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1448.pdf


To avoid multiply instantiations among translation units,
in C++11 templates can be declared extern.


Normal "inclusion" method:

- we define the template in header
- include the header into many source file
  and use and instantiate templates in every source.
- the linker drops the unnecessary objects.

The problem: code bloat. Every object will contain all instantiations.


Many cases we would like to place the instantiations into one place,
like a shared object, and the client code will only use it.



For ordinary functions we can declare a function:

int foo(int);	// declaration only


but for templates we have no syntax for that:

template int bar(int); // explicit instantiation

template<> int bar(int); // explicit specialization



The C++11 syntax is:


#include "x.h"

extern template class X<int>;	// surpress implicit instantiation

void f( X<int>& xx )
{
    // use X<int>, but not instantiate 
}



Additional advance: associated types are not instantiated.




C++11 template arguments
========================


In C++98 local or unnamed types can not be used as template arguments.
In C++11 this restriction was removed:


struct    // unnamed type
{
    void operator()(int n) const
    {
        std::cout << n << " ";
    }
} unnamed;

template <typename T>
void f( const std::vector<T>& v )
{
    struct func   // local type
    {
        void operator()(T n) const
        {
            std::cout << n << " ";
        }
    };
    std::for_each( v.begin(), v.end(), func());  // error in C++98
                                                 // works since C++11

    std::for_each( v.begin(), v.end(), unnamed); // error in C++98
                                                 // works since C++11

    std::for_each( v.begin(), v.end(), [](int n) // lambda also works
                                       {
                                           std::cout << n << " ";
                                       });  //  ok in C++11
}



#include <iostream>

enum { blue, green, yellow, red};  // unnamed type

template <typename T>
void f2( const T& t)
{
  std::cout << t << std::endl;
}
int main()
{
  f2(yellow);
  return 0;
}


$ g++ -ansi -pedantic -Wall -W  templ3.cpp
templ3.cpp: In function ‘int main()’:
templ3.cpp:12:12: error: no matching function for call to ‘f2(<anonymous enum>)’
  f2(yellow);
            ^
templ3.cpp:12:12: note: candidate is:
templ3.cpp:6:6: note: template<class T> void f2(const T&)
 void f2( const T& t)
      ^
templ3.cpp:6:6: note:   template argument deduction/substitution failed:
templ3.cpp: In substitution of ‘template<class T> void f2(const T&) [with T = <anonymous enum>]’:
templ3.cpp:12:12:   required from here
templ3.cpp:12:12: error: ‘<anonymous enum>’ is/uses anonymous type
   f2(yellow);
            ^
templ3.cpp:12:12: error:   trying to instantiate ‘template<class T> void f2(const T&)’

$ g++ -ansi -pedantic -Wall -W -std=c++11 templ3.cpp
(cc)ezolpor@md-mtas2:~/work/uni/lecture/multiparadigm/xx$ ./a.out 2
$ ./a.out
2





Type alias (since C++11)
========================


- A type alias declaration introduces a name which can be used as a synonym.
  It does not introduce a new type and can not change the meaning of an
  existing type.

- An alias template is a template which, when specialized, is equivalent to
  the result of substituting the template arguments of the alias template.




using myint = int;
template <class T> using ptr_t = T*;

void f(int) { }
// void f(myint) { }   syntax error: redeclaration of f(int)

// make mystring one parameter template
template <class CharT> using mystring =
    std::basic_string<CharT,std::char_traits<CharT>>;

int main()
{
  int i = 1;
  myint mi = i;

  ptr_t<int> p = new int;
  return 0;
}


// type alias can introduce a member typedef name
template<typename T>
struct Container {
    using value_type = T;
};
// which can be used in generic programming
template<typename Container>
void fn2(const Container& c)
{
    typename Container::value_type n;
}





Variable templates (since C++14)
===============================


Before C++14 it was implemented as static data member of a class template
or as a constexpr function template returning the value.


// g++ 4.9.2 error, clang++ 3.5.0 ok
template <class T>
constexpr T pi = T(3.141592);

template <typename T>
T area(T r)
{
    return pi<T> * r * r;
}

int main()
{
    double ar = area(4.0);
    return 0;
}



struct limits
{
    template <typename T>
    static const T min;	   // declaration
};

template <typename T>
const T limits::min = { }; // definition of a static data member template


Fun:

#include <iostream>

template <class T>
T pi = T(3.141592);

int main()
{
    pi<int> = 32;
    std::cout << pi<double> << std::endl;
    std::cout << pi<int> << std::endl;
    return 0;
}


$ ./a.out
3.14159
32




Variadic templates (since C++11)
================================



#include <iostream>

template<typename T>
T sum(T v)
{
  return v;
}

template<typename T, typename... Args>
T sum(T first, Args... args)
{
  return first + sum(args...);
}

int main()
{
  long lsum = sum(1, 2, 3, 8, 7);

  std::string s1 = "x", s2 = "aa", s3 = "bb", s4 = "yy";
  std::string ssum = sum(s1, s2, s3, s4);

  std::cout << lsum << " " << ssum << std::endl;
  return 0;
}


$ ./a.out
21 xaabbyy


typename ...Args    <--------- template parameter pack
Args... args        <--------- function parameter pack


T sum(T, Args...) [T = int, Args = <int, int, int, int>]
T sum(T, Args...) [T = int, Args = <int, int, int>]
T sum(T, Args...) [T = int, Args = <int, int>]
T sum(T, Args...) [T = int, Args = <int>]
T sum(T) [T = int]






template<typename T>
bool pair_comparer(T a, T b)
{
    return a == b;
}

template<typename T, typename... Args>
bool pair_comparer(T a, T b, Args... args) {
    return a == b && pair_comparer(args...);
}


int main()
{
  std::cout << pair_comparer(1, 1, 3, 3, 5, 6) << std::endl;
  return 0;
}



int main()
{
  std::cout << pair_comparer(1, 1, 3, 3, 5, 6, 7) << std::endl;
  return 0;
}


var.cpp: In function ‘bool pair_comparer(T, T, Args ...) [with T = int, Args = {int}]’:
var.cpp:12:43:   recursively instantiated from ‘bool pair_comparer(T, T, Args ...) [with T = int, Args = {int, int, int}]’
var.cpp:12:43:   instantiated from ‘bool pair_comparer(T, T, Args ...) [with T = int, Args = {int, int, int, int, int}]’
var.cpp:18:43:   instantiated from here
var.cpp:12:43: error: no matching function for call to ‘pair_comparer(int&)’
var.cpp:12:43: note: candidates are:
var.cpp:5:6: note: template<class T> bool pair_comparer(T, T)
var.cpp:11:6: note: template<class T, class ... Args> bool pair_comparer(T, T, Args ...)



Add:


template<typename T>
bool pair_comparer(T a)
{
    return false;
}




Perfect forwarding:


std::unique_ptr<FooType> f = std::make_unique<FooType>(1, "str", 2.13);



template<typename T, typename... Args>
unique_ptr<T> make_unique(Args&&... args)
{
    return unique_ptr<T>(new T(std::forward<Args>(args)...));
}



The parameter pack can appear in various places:


template<class A, class B, class...C> void func(A arg1, B arg2, C...arg3)
{
    container<A,B,C...> t1;  // expands to container<A,B,E1,E2,E3> 
    container<C...,A,B> t2;  // expands to container<E1,E2,E3,A,B> 
    container<A,C...,B> t3;  // expands to container<A,E1,E2,E3,B> 
}




Mixins reloaded:


struct A {};
struct B {};
struct C {};

template<class... Mixins>
class X : public Mixins...
{
public:

    //X(const Mixins&... mixins) : Mixins(mixins)... { }
};

int main()
{
  X<A,B,C> xx;
  return 0;
}



With constructor parameters:


struct A {};
struct B {};
struct C {};

template<class... Mixins>
class X : public Mixins...
{
public:
    X(const Mixins&... mixins) : Mixins(mixins)... { }
};

int main()
{
  A a;
  B b;
  C c;
  X<A,B,C> xx(a,b,c);
  return 0;
}



Lambda capture:



template<class ...Args>
void f(Args... args)
{
    auto lm = [&, args...] { return g(args...); };
    lm();
}



Sizeof:


template<class... Types>
struct count
{
    static const std::size_t value = sizeof...(Types);
};




Variadic templates -- advanced
==============================




#include <sstream>
#include <iostream>
#include <vector>

template <typename T>
std::string to_string_impl(const T& t)
{
  std::stringstream ss;
  ss << t;
  return ss.str();
}

std::vector<std::string> to_string()
{
  return {};
}

template <typename P1, typename ...Param>
std::vector<std::string> to_string(const P1& p1, const Param&... params)
{
  std::vector<std::string> s;
  s.push_back(to_string_impl(p1));

  const auto remainder = to_string(params...);
  s.insert(s.end(), remainder.begin(), remainder.end());
  return s;
}

int main()
{
  const auto vec = to_string("hello", 1, 4.5);

  for (const auto& x : vec)
  {
    std::cout << x << ' ';
  }
  std::cout << std::endl;
}



// Jason Turner: https://www.youtube.com/watch?v=o1EvPhz6UNE

#include <sstream>
#include <iostream>
#include <vector>

template <typename T>
std::string to_string_impl(const T& t)
{
  std::stringstream ss;
  ss << t;
  return ss.str();
}

template <typename ...Param>
std::vector<std::string> to_string(const Param&... params)
{
  return { to_string_impl(params)... };   // std::initializer_list
}

int main()
{
  const auto vec = to_string("hello", 1, 4.5);

  for (const auto& x : vec)
  {
    std::cout << x << ' ';
  }
  std::cout << std::endl;
}



#include <sstream>
#include <iostream>
#include <vector>

// C++14 generic lambda -- but bigger code is generated
template <typename ...Param>
std::vector<std::string> to_string(const Param&... params)
{
  const auto to_string_impl = [](const auto& t) {
                                    std::stringstream ss;
                                    ss << t;
                                    return ss.str();
                               };
  return { to_string_impl(params)... };
}

int main()
{
  const auto vec = to_string("hello", 1, 4.5);

  for (const auto& x : vec)
  {
    std::cout << x << ' ';
  }
  std::cout << std::endl;
}



Fold expressions in C++17
=========================


Reduces (folds) a parameter pack over a binary operator

Syntax:

( pack  op … )		 unary right fold   E1 op (…op(En-1 op En))
( pack  op …  op  init ) binary right fold  E1 op (…op(En-1 op (En op i)))
( …  op  pack)		 unary left fold    ((E1 op E2) op…) op En
( init  op  …  op pack ) binary left fold   (((i op E1) op E2) op…) op En



template <typename... Args>
bool all(Args... args) { return ( ... && args); }

int main()
{
    bool b = all( i1, i2, i3, i4);
        // = ((i1 && i2) && i3) && i4;
}




#include <iostream>

template <typename ...T>
auto sum(T... t)
{
  typename std::common_type<T...>::type result{};
  std::initializer_list<int>{ (result += t, 0)... };
  return result;
}

int main()
{
  std::cout << sum(1,2,3.0,4.5) << std::endl;
}


In C++17 there will be fold expressions


#include <iostream>

template <typename ...T>
auto sum(T... t)
{
  return ( t + ... );
}

template <typename ...T>
auto avg(T... t)
{
  return ( t + ... ) / sizeof...(t);
}

int main()
{
  std::cout << sum(1,2,3.0,4.5) << std::endl;
  std::cout << avg(1,2,3.0,4.5) << std::endl;
}