CPP / C++ - Template Metaprogramming - Generic Programming

Table of Contents

1 Template Metaprogramming or Generic Programming

1.1 Overview

C++ Metaprogramming Features:

  • Templates
    • Use case:
      • Template metaprogramming or generic programming
      • Generic classes and containers
      • Generic algorithms
      • Compile-time optmization
      • Write high performance code by eliminating virtual member function calls.
    • Limitation: Unfortunately, the C++ templates cannot manipulate the AST and generate code in the way that LISP-like languages do.
  • C++11 Constexpr
    • Use cases:
      • Compile-time computations such as look up tables, math constants, CRC32, hash, string encryption and obfuscation at compile-time and so on.
  • Inline functions
    • Use cases:
      • Removing function-calls. The function code is inserted at the call-site by the compiler allowing a more efficient and perfomant code.
  • Pre-processor macros
    • Use-cases:
      • Debugging, print line number, file, current function, function signature and so on.
      • Conditional compilation
      • Conditional compilation for cross platform compatibility
      • Boilerplate code generation which cannot be done with templates or anything else.
      • Generation of reflection data.

Generic Programming / Template Metaprogramming Design Patterns:

  • Generic Functions, algorithms and containers
    • Some known use cases:
      • C++ STL introduced by Alexander Stepanov.
      • Boost Libraries
  • CRTP => Curious Recurring Template Pattern
    • Eliminates virtual function-calls overhead by emulating inheritance or dynamic polymorphism with static polymorphism or template metaprogramming.
  • Type Erasure
    • Despite the high performance and the ability to operate ony type regardless of the class hierarchy, the main shortcoming of generic programming is that, it is not possible to store unrelated types in the same containers or access them by the same pointer. The type erasure technique address those downsides by combining generic programmign and generic programming.
    • Known uses:
      • std::function (C++11)
      • std::any (C++17), Boost.any, std::variant (C++17) and Boost.variant
  • EP => Expression Template => Technique used by many scientific library for encoding DSL - Domain Specific Languages with templates.
    • Some known uses of this design pattern are:
      • Linear Algebra: libraries Blitz++, Eigen and Armadillo. Those libraries uses the EP pattern for optimizing loops at compile-time.
      • Automatic Differentiation.
  • Meta Functions or Type traits => "Functions" emulated with structs and static methods or members that can manipulate types or query type information using template specialisation.
  • SFINAE - Substitution Is Not An Error. Use cases:
    • Type instrospection at compile-time.
    • Constrain templated overload function
    • Constrain the types of a templated function for generating better error messages. (Hack for concepts)
  • Tag dispatch - Use an additional empty struct parameter for allowing the compiler to distinguish between functions of multiple signature.
  • Policy Based Design

Libraries and Frameworks for metaprogramming:

Tool for testing templates online

  • Home - Metashell - "The goal of this project is to provide an interactive template metaprogramming shell."
  • Templar - "Visualization tool for Templight C++ template debugger traces"
  • https://godbolt.org/ - Compiler explorer, allows taking a closer look at the object code (assembly and symbols) generated by templates.

Advanced Templates

  • template-template or nested templates
  • Universal references, std::forward
  • std::index_sequence
  • std::make_index_sequence
  • std::enable_if
  • dependent type with (typename) keyword
  • decltype
  • declval
  • variadic templates with tuples and variadic functions
  • Policy-based design pattern
  • SFINAE
  • CRTP

Template Metaprogramming Reference

  • Andrei Alexandrescu's Loki Library (http://loki-lib.sourceforge.net/)
    • type list
    • functor
    • singleton
    • object factory
    • visitor
    • multi methods
    • pimpl - pointer to implementation.

1.2 Template type-safe duck-typing or structural typing

In dynamically programming languages like Python, Ruby and etc, a function or method can accept any object implementing the methods referred in the function body regardless of the object base or interface. For instance, in the code below the function describeArea will work with any class implementing the methods .area() and .name() not matter the object's base class.

This ability to work with any object which has that requested types, in this case .area() and .name() is called duck-typying. Other languages with duck-typing ability are Smalltalk, Groovy, C#, Scala and Objective-C. The advantage of duck-typing is that function or methods can work with classes without an inheritance hierarchy or a common base class. 

def describeArea(shape):
    print("Shape is      = " + shape.name())
    print("Shape area is = " + str(shape.area()))

class Square:
    def __init__(self, side):
        self.side = side 
    def area(self):
        return self.side * self.side
    def name(self):
        return "square"

class Circle:
    def __init__(self, radius):
        self.radius = radius
    def area(self):
        return self.radius * self.radius  * 3.1415
    def name(self):
        return "circle"

Running: 

>>> s = Square(10)
>>> c = Circle(3)
>>>

>>> describeArea(s)
Shape is      = square
Shape area is = 100
>>> 
>>> describeArea(c)
Shape is      = circle
Shape area is = 28.273500000000002
>>> 
>>>

C++ "Duck-typing" or type-safe structural typing

C++ templates feature supports a more type-safe duck-typing as the feature allows to write functions or methods which works with any object implementing the methods requested in the template code regardless of passed types have a common class hierarchy or a base class. However, unlike Python or Scala's duck typing, C++'s template doesn't have performance penalty due to dynamic polymorphism or reflection as it generates code at compile-time for each parameter type.

The C++'s template duck-typing is also called static polymorphism as a contrast to dynamic polymorphism which requires that all objects passed to a function or method implement the same base class.

Example: The function describeArea works with any object implementing the methods area() and name(), however unlike Python and other dynamically typed languages, if an object that doesn't implement none of those mentioned methods is passed as argument, a compile error will be generated rather than a runtime error.

The advantage of C++ template is that it eliminates the runtime overhead of dynamic polymorphism or virtual function calls, therefore it makes the code more performant and loosely coupled as it can work with any class regardless of any inheritance hierarchy. 

#include <iostream>

// Works with any type T which implements .name() or .area()
template <class T>
void describeArea(const T& obj){
     std::cout << "Shape is = " << obj.name() << std::endl;
     std::cout << "Area is  = " << obj.area() << std::endl;
     std::cout << "---------" << std::endl;
}

class Circle{
private:
    double m_radius;
public:
    Circle(double radius): m_radius(radius) {};
    double area() const {
       return 3.1415 * m_radius * m_radius;
    }
    const char* name() const {
        return "circle";
    }   
};

class Square{
private:
   double m_side;
public:
   Square(double side): m_side(side) {};
   double area() const {
      return m_side * m_side;
   }
   const char* name() const {
      return "square";
   }
};

int main(){
    Square s(4.0);
    Circle c(3.0);
    describeArea(s);
    describeArea(c);
    return 0;
}

Running:

  • The template generates multiple versions of the function describeArea specific for each type, for instance, it generates the overload functions describeArea(const Circle&) and describeArea(const Square&).
  • Static polymorphism is a high performance alternative to dynamic polymorphism, inheritance, and virtual methods since all called functions are resolved at compile-time.
$ clang++ -std=c++11 templateDuckTyping.cpp -o out.bin && ./out.bin
Shape is = square
Area is  = 16
---------
Shape is = circle
Area is  = 28.2735
---------

Generated functions:

  • Once the template is instantiated, it generates the following overloaded functions as object-code (compiled-code):
// Overloaded describeArea for Circle class 
void describeArea(const Circle& obj){
     std::cout << "Shape is = " << obj.name() << std::endl;
     std::cout << "Area is  = " << obj.area() << std::endl;
     std::cout << "---------" << std::endl;
}

// Overloaded describeArea for Square class  
void describeArea(const Square& obj){
     std::cout << "Shape is = " << obj.name() << std::endl;
     std::cout << "Area is  = " << obj.area() << std::endl;
     std::cout << "---------" << std::endl;
}

Generated Object-Code

Main function assembly (object-code): 

main:                                   # @main
        push    rbp
        mov     rbp, rsp
        ... ... ... ... ... ... ... ... 
        call    void describeArea<Square>(Square const&) ;; Mangled name:  _Z12describeAreaI6SquareEvRKT_ 
        lea     rdi, [rbp - 24]
        call    void describeArea<Circle>(Circle const&) ;; Mangled name: _Z12describeAreaI6CircleEvRKT_ 
        ... ... ... ... ... ... ... ... 
        ret

As C++ supports function overloading and the object code need a unique function name for every function, the compiler generates an unique name for every function overload, classes and template classes. This process of generating an unique this name is called name mangling or name decoration which is unique to every compiler. Due to the name mangling, the compiler (Clang) encodes the symbol of the overloaded function describeArea<Square> as _Z12describeAreaI6SquareEvRKT_ and the symbol of the overloaded function describeArea<Circle> as _Z12describeAreaI6CircleEvRKT_.

Generated object code for function overload: describeArea<Square>(Square const&). 

;; Mangled name: _Z12describeAreaI6SquareEvRKT_
void describeArea<Square>(Square const&):         # @void describeArea<Square>(Square const&)
        push    rbp
        mov     rbp, rsp
        sub     rsp, 48
        mov     qword ptr [rbp - 8], rdi
   ... ... ... ... ... ... ... ... ...

Generated object code for function overload: describeArea<Circle>(Circle const&). 

;; Mangled name:  _Z12describeAreaI6CircleEvRKT_
void describeArea<Circle>(Circle const&):         # @void describeArea<Circle>(Circle const&)
        push    rbp
        mov     rbp, rsp
        sub     rsp, 48
        mov qword ptr [rbp - 8], rdi
        movabs  rdi, offset std::__1::cout
        movabs  rsi, offset .L.str
   ... ... ... ... ... ... ... ... ...

Summary:

  • Type-safe code generator: The main difference between C++ generics (templates metaprogramming) and the generics of other languages such as Java and C# is that C++ templates generates code at compile-time and never erases type information, therefore C++ templates are more performant.
  • The C++ generic programming has the name metaprogramming (template metaprogramming) because it generates code at compile-time just like Lisp macros metaprogramming, although with more limitations. For short: C++ templates are type-safe code generators.
  • Templates have zero cost and follows the C++ motto, "don't pay for what you don't use" they only generate code when requested or instantiated, in other words, when there is any reference to them in the code, for instance, std::vector<double>, std::vector<int> and so on.
  • Templates are widely used in the STL (Standard Template Library) and the Boost Library and many other libraries.

Disadvantages:

  • Generally, templates must be in header files what increases the compile-time.
  • Hard to hide or obfuscate templates in proprietary code as they need to be exposed in header files.
  • Template code can be hard to understand and it may be hard to figure out the set of types parameters that can satisfy the template constraints.
  • Hard to restrict type parameters that a template can take. The requirements of a template type parameters are called concepts and there is no language feature for making concepts explicit.
  • Templates can generate long and cryptic error messages.
  • Templates can increase the executable size, since they generate object-code for overloaded functions generated by function templates and also object code for classes generated by class templates. It may not be a problem for desktop applications, but it can be a drawback for embedded systems with limited ROM size.

1.3 Class Template

1.3.1 Example: Generic stack class

Note:

  • A class template is not a class, it is factory of classes and has zero cost until it is used or instantiated. For instance, Stack<int> and Stack<std::string> are different classes and cannot be stored in containers or accessed with the same pointer.
  • When Stack<int> or Stack<double> appears in the code, the compiler generates an unique object code for each of those template instantiation. The C++ generics doesn't have type erasure like java where all objects can be casted to an instance of Object.
  • All the template code must be always in the header files.

Class Template Example: 

#include <iostream> 
#include <deque> 
#include <string>

template<class T>
class Stack{
private:
        std::deque<T> _stack;
public:
    struct stack_empty_error: public std::exception{
        const char* what() const throw(){
           return " ==> Error: stack empty." ;
        }
    };
    void push(const T& t){
        _stack.push_back(t);
    }
    T pop(){
        if(_stack.empty())
            throw stack_empty_error();
        auto x = _stack.back();
        _stack.pop_back();
        return x;
    }
    T peek(){
        if(_stack.empty())
            throw stack_empty_error();
        return _stack.back();
    }
    size_t size(){  return _stack.size(); }
    bool   empty(){ return _stack.empty(); }
    void   clear(){ _stack.clear(); }
    void print(){
        std::cout << " stack: ";
        for(const auto& x: _stack)
            std::cout << " " << x ;
        std::cout << "\n";
    }
};

Usage example:

  • Instantiate class template with int parameter.
>> Stack<int> s1;
>> s1.push(10)
>> s1.push(20)
>> s1.push(-30)
>> s1.push(15)
>> 
>> s1.size()
(unsigned long) 4
>> 
>> s1.empty()
(bool) false

>> s1.print()
 stack:  10 20 -30 15

>> s1.peek()
(int) 15

>> s1.pop()
(int) 15
>> s1.pop()
(int) -30
>> s1.pop()
(int) 20
>> s1.pop()
(int) 10
>> s1.pop()
Error in <TRint::HandleTermInput()>: Stack<int>::stack_empty_error caught:  ==> Error: stack empty.
>> 

>> s1.size()
(unsigned long) 0
>> s1.empty()
(bool) true
>> 
>>
  • Instantiate class template with std::string parameter.
> Stack<std::string> sd;
>> sd.push("hello")
>> sd.push("c++")
>> sd.push("templates")
>> sd.push("test")
>> 
>> sd.size()
(unsigned long) 4
>> sd.empty()
(bool) false
>> sd.peek()
(std::basic_string<char, std::char_traits<char>, std::allocator<char> >) "test"
>> 
>> sd.print()
 stack:  hello c++ templates test
>> 
>> sd.pop()
(std::basic_string<char, std::char_traits<char>, std::allocator<char> >) "test"
>> sd.pop()
(std::basic_string<char, std::char_traits<char>, std::allocator<char> >) "templates"
>> sd.pop()
(std::basic_string<char, std::char_traits<char>, std::allocator<char> >) "c++"
>> sd.pop()
(std::basic_string<char, std::char_traits<char>, std::allocator<char> >) "hello"
>>
  • Generic client code for the class stack:
// Non-destructive print -> Creates a copy invoking copy constructor 
template<typename T>
void printStack(Stack<T> t){
    while(!t.empty())
       std::cout << t.pop() << " ";
    std::cout << "\n";
    std::cout.flush();
}

template<class T>
void fillStack(Stack<T> &t, const std::deque<T>& data){
     for(const auto& d: data)
         t.push(d);
}
  • Running client code.
>> Stack<double> stack_double1;
>> fillStack(stack_double1, {2.0, 5.0, 6.0, 9.0})
>> 
>> stack_double1.size()
(unsigned long) 4
>> stack_double1.peek()
(double) 9.0000000
>> 

>> printStack(stack_double1)
9 6 5 2 
>> 
>> printStack(stack_double1)
9 6 5 2 

>> Stack<std::string> stack_string;
>> fillStack(stack_string, {"hello", "hpc", "C++", "RULEZ", "peformance", "matters"})

>> printStack(stack_string)
matters peformance RULEZ C++ hpc hello

>> printStack<std::string>(stack_string)
matters peformance RULEZ C++ hpc hello 
>> 

>> stack_string.clear()
>> printStack3<std::string>(stack_string)

>>

1.3.2 Example: Tuple of three elements

Code: 

#include <iostream>
#include <string>

template <class A, class B, class C>
struct tuple3{
     // Empty constructor - necessary to store by value the tuple
     // in STL containers.
     tuple3(){}
     tuple3(const A& a, const B& b, const C& c)
        : a(a), b(b), c(c){     
     }
     A a;
     B b;
     C c;   
};

template <class A, class B, class C>
auto getA(const tuple3<A, B, C>&  t) -> A{
     return t.a;    
}

template <class A, class B, class C>
auto getB(const tuple3<A, B, C>&  t) -> B{
     return t.b;    
}

template <class A, class B, class C>
auto getC(const tuple3<A, B, C>&  t) -> C{
     return t.c;    
}

template <class A, class B, class C>
void printTuple1(const tuple3<A, B, C>& t){
     std::cout << "tuple3{"
               << " a = " << t.a
               << " b = " << t.b
               << " c = " << t.c
               << " } "
               << "\n";
}

template <class A, class B, class C>
auto printTuple2(const tuple3<A, B, C>& t) -> void {
     std::cout << "tuple3{"
               << " a = " << t.a
               << " b = " << t.b
               << " c = " << t.c
               << " } "
               << "\n";
}

Running: 

>> tuple3<double, char, std::string> h(100.23, 'x', "world")
(tuple3<double, char, std::string> &) @0x7f3ea8607010
>> 
>> h.a
(double) 100.23000
>> h.b
(char) 'x'
>> h.c
(std::basic_string<char, std::char_traits<char>, std::allocator<char> > &) "world"
>> 

>> getA(h)
(double) 100.23000
>> getB(h)
(char) 'x'
>> getC(h)
(std::basic_string<char, std::char_traits<char>, std::allocator<char> >) "world"

// Types parameter are deduced by the compiler.
>> printTuple1(h)
tuple3{ a = 100.23 b = x c = world } 

>> printTuple2(h)
tuple3{ a = 100.23 b = x c = world } 
>> 

>> printTuple1<double, char, std::string>(h)
tuple3{ a = -100 b = x c = world } 
>>

auto tdata = std::deque<tuple3<int, char, std::string>>{
        {100, 'x', "C++"},
        {200, 'z', "Forth"},
        {-900, 'k', "Lisp"},
        {66, 'p', "route"}};

for(const auto& t: tlist) printTuple1(t);

>> for(const auto& t: tdata) printTuple1(t);
tuple3{ a = 100 b = x c = C++ } 
tuple3{ a = 200 b = z c = Forth } 
tuple3{ a = -900 b = k c = Lisp } 
tuple3{ a = 66 b = p c = route } 
>> 

// Compiler fails to deduce arguments 
>> std::for_each(tdata.begin(), tdata.end(), printTuple1)
ROOT_prompt_32:1:1: error: no matching function for call to 'for_each'
std::for_each(tdata.begin(), tdata.end(), printTuple1)
^~~~~~~~~

>> std::for_each(tdata.begin(), tdata.end(), printTuple1<int, char, std::string>);
tuple3{ a = 100 b = x c = C++ } 
tuple3{ a = 200 b = z c = Forth } 
tuple3{ a = -900 b = k c = Lisp } 
tuple3{ a = 66 b = p c = route } 
>>

>> std::for_each(tdata.begin(), tdata.end(), &printTuple1<int, char, std::string>);
tuple3{ a = 100 b = x c = C++ } 
tuple3{ a = 200 b = z c = Forth } 
tuple3{ a = -900 b = k c = Lisp } 
tuple3{ a = 66 b = p c = route } 
>>

1.4 Generic Programming "Concepts"

  • Concepts:
    • "Concepts" is a set of requirements (implicit interface) that a template parameter must fulfill in order to instantiate a template.
    • The name "concepts" was coined by Alexander Stepanov, author of the STL and one of the main proponents of generic programming.
    • A type that satisfies or fulfill a given concept is said to model this concept.
  • Concept Language Feature:
    • A shortcoming of templates is the implicit requirements that makes the code harder to read and understand and lead to verbose and unhelpful error messages. The aim of "concept" language feature is to make the template type requirements explicit and fully specified for constraining the type parameters to type satisfying the concept and improve the readability and error messages.
    • The C++11, C++14 and C++17 does not have the "concepts" language feature, however it is being introduced in the upcoming C++20 standard. So, until it is not fully mainstream, the reader has to figure out or deduce the requirement of the template parameter or it should be specified in the comments.
    • C++20 Concepts: Constraints and concepts (since C++20) - cppreference.com
  • Named Requirements

Some STL Named Requirements:

Concept Expression Description
or "STL Named Requirement"    
DefaultConstructible T obj{}; T obj; T(); T{} Type T is default constructible.
CopyConstructible T a(b); T a{b}; T a = b; Type T has a copy constructor.
EqualityComparable x == y The type has the (==) equality operator returning bool.
     

References

1.5 Non-class template parameters

1.5.1 Overview

It is possible to use the following kinds of template parameters.

  • class or typename
  • Integers
  • Function pointer
  • Member function pointer

1.5.2 Integer as template parameter

// n => Numeric template argument with default value 3 
template<size_t n = 3, typename Action>
void repeat(Action fn){
    for(size_t i = n; i > 0; i--)
       fn();
}

This templated function, repeat<n>, generates a different functions for every different value of n. For instance, it will generate the functions repeat<1> for n = 1, repeat<3> for n = 3, repeat<10> for n = 10 and so on. It can be tested at https://godbolt.org/.

Running: 

>> repeat<1>([]{ std::cout << "Repeat n times" << std::endl; });
Repeat n times

>> repeat([]{ std::cout << "Repeat n times" << std::endl; });
Repeat n times
Repeat n times
Repeat n times

>> repeat<>([]{ std::cout << "Repeat n times" << std::endl; });
Repeat n times
Repeat n times
Repeat n times

>> repeat<5>([]{ std::cout << "Repeat n times" << std::endl; });
Repeat n times
Repeat n times
Repeat n times
Repeat n times
Repeat n times

1.5.3 Function pointer as template parameter

Syntax 1: 

#include <iostream>
#include <iomanip>
#include <cmath>

template<double (*mfunction) (size_t)>
void tabulateFunPTR(size_t n)
{
    std::cout << std::fixed << std::setprecision(3);
    for(size_t i = 0; i < n; i++)
        std::cout << std::setw(5) << i
                  << std::setw(10) << mfunction(i)
                  << std::endl;
}

Syntax 2: 

template<double mfunction (size_t)>
void tabulateFunPTRB(size_t n)
{
    std::cout << std::fixed << std::setprecision(3);
    for(size_t i = 0; i < n; i++)
        std::cout << std::setw(5) << i
                  << std::setw(10) << mfunction(i)
                  << std::endl;
}

Syntax 3: 

// It is also possible the following syntax with auto keyword.
template<auto mfunction (size_t) -> double>
void tabulateFunPTRC(size_t n)
{
    std::cout << std::fixed << std::setprecision(3);
    for(size_t i = 0; i < n; i++)
        std::cout << std::setw(5) << i
                  << std::setw(10) << mfunction(i)
                  << std::endl;
}

Running: 

>> tabulateFunPTR<exp>(4)
    0     1.000
    1     2.718
    2     7.389
    3    20.086

>> tabulateFunPTR<sqrt>(9)
    0     0.000
    1     1.000
    2     1.414
    3     1.732
    4     2.000
    5     2.236
    6     2.449
    7     2.646
    8     2.828

>> tabulateFunPTRB<cbrt>(4)
    0     0.000
    1     1.000
    2     1.260
    3     1.442

>> tabulateFunPTRC<std::exp>(5)
    0     1.000
    1     2.718
    2     7.389
    3    20.086
    4    54.598

1.5.4 Class templates as template parameters

AKA: template template.

Example 1:

Every STL container has two type parameters, the element type and the allocator type which has the element type as parameter. In the following code, the type parameter named Container is used for changing the STL container used by the stack class. 

#include <iostream>
#include <vector>
#include <deque>
#include <list>

template<
     // Type of stack element 
     typename Element,
     // Every STL container has two type parameters Container<Element, Allocator>
     // The allocator has the type parameter Allocator<Element>
     template<typename, typename> class Container = std::deque
     >
class Stack{
private:
    Container<Element, std::allocator<Element>> _stack;
public:
    void push(const Element& t){
         _stack.push_back(t);
    }
    Element pop(){
         auto x = _stack.back();
         _stack.pop_back();
         return x;
    }
    size_t size(){  return _stack.size(); }
    bool   empty(){ return _stack.empty(); }
    void   clear(){ _stack.clear(); }
    void print(){
         std::cout << " stack: ";
         for(const auto& x: _stack)
                 std::cout << " " << x ;
         std::cout << "\n";
    }
};

Running: 

>> Stack<int> s1;
>> s1.push(10), s1.push(15), s1.push(25); s1.print()
 stack:  10 15 25
>> 

>> Stack<std::string, std::vector> s2;
>> s2.push("C++"), s2.push("IOT"), s2.push("Network"), s2.print();
 stack:  C++ IOT Network
>> 

>> auto sn = Stack<char, std::list>{};
>> sn.push('x'), sn.push('y'), sn.push('w'), sn.push('k'), sn.print();
 stack:  x y w k
>>

Example 2: Generic higher-order function which can peform a fold-operation on any STL sequence container.

  • Version A - Using for-range based loop.
template<
     typename Acc,
     typename Element,  
     typename Func,
     template<typename> class Allocator,
     template<typename, typename> class Container
     >
Acc foldContainerA(Acc init, const Container<Element, Allocator<Element>>& cont, Func func)
{
     Acc acc {init};
     for(const auto& x: cont) acc = func(acc, x);
     return acc;
}
  • Version B - Using iterator based loop
template<
    typename Acc,
    typename Element,   
    typename Func,
    template<typename> class Allocator,
    template<typename, typename> class Container
    >
Acc foldContainerB(Acc init, const Container<Element, Allocator<Element>>& cont, Func func)
{
    Acc acc {init};
    // Dependent name 
    using Iterator = typename Container<Element, Allocator<Element>>::const_iterator;
    // Or: typedef typename Container<Element, Allocator<Element>>::const_iterator Iterator;
    for(Iterator it = cont.begin(); it < cont.end(); it++)
            acc = func(acc, *it);
    return acc;
}

Running: 

#include <functional>

>> std::vector<int> xsa{1, 2, 3, 4, 5, 6};

>> foldContainerA<int>(0, xsa, [](int acc, int x){ return 10 * acc + x;})
(int) 123456
>> 

>> foldContainerB<int>(0, xsa, [](int acc, int x){ return 10 * acc + x;})
(int) 123456

// 1 + 2 + 3 + 4 + 5 + 6
>> foldContainerA<int>(0, xsa, [](int acc, int x){ return acc + x;})
(int) 21

>> foldContainerB<int>(0, xsa, [](int acc, int x){ return  acc + x;})
(int) 21

>> foldContainerA<int>(0, xsa, std::plus<int>())
(int) 21
>> 

>> std::deque<int> xsb{1, 2, 3, 4, 5};

>> foldContainerA<int>(0, xsb, std::plus<int>())
(int) 15

>> foldContainerA<int>(1, xsb, std::multiplies<int>())
(int) 120
>> 

>> foldContainerB<int>(1, xsb, std::multiplies<int>())
(int) 120

1.6 Templates and STL Containers

1.6.1 Overview

Templates can be used for writing more generic and resuable code which operates like functions or STL algorithms on any type of iterator or container.

1.6.2 Example 1 - iterating over containers

This example shows how to implement generic code which operates on any type of container or iterator in modern C++.

Code highlights: 

namespace IterUtils{
        template<class Iterator>
        double sumContainer(const Iterator& begin, const Iterator& end){
            double sum = 0.0;
            for(Iterator it = begin; it != end; ++it)
                sum += *it;
            return sum;
        }

        // Sum elements of any type <Container> with methods .begin() and .end()
        // returnign iterators.
        template<class U, class Container>
        auto sumContainer2(const Container& container) -> U{
            U sum{}; // Uniform initialization
            for(auto it = container.begin(); it != container.end(); ++it)
               sum += *it;
            return sum;
        }

        template<class Iterator>
        auto printContainer(
                const Iterator& begin,
                const Iterator& end,
                const std::string& sep = ", " ) -> void
        {
                for(Iterator it = begin; it != end; ++it)
                        std::cout <<  *it << sep;
        }

        template<class Container>
        auto printContainer2(
                  const Container& cont
                 ,const std::string& sep = ", "
                ) -> void
        {
           // C++11 For-range based loop
           for(const auto& x: cont)
                   std::cout <<  x << sep;
        }

        // Higher order function
        // The parameter actions accepts any type which can be called like
        // a function returning void.
        //
        // Note: It doesn't matter as it is possible to use both class T or typename T.
        template<typename Container, typename Function>
        auto for_each (const Container cont, Function action) -> void
        {
            for(const auto& x: cont) action(x);
        }

}; // ----- End of namespace IterUtils ----- //

Program output: 

$ clang++ template-iterator-container.cpp -o template-iterator-container.bin -g -std=c++11 -Wall -Wextra 
$ ./template-iterator-container.bin

=========== Experiment 1 - sumContainer
template-iterator-container.cpp:95: ; iu::sumContainer(&carray[0], &carray[0] + arrsize) = 16
template-iterator-container.cpp:96: ; iu::sumContainer(vec1.begin(), vec1.end()) = 16
template-iterator-container.cpp:97: ; iu::sumContainer(list1.begin(), list1.end()) = 16
template-iterator-container.cpp:98: ; iu::sumContainer(deque1.begin(), deque1.end()) = 16

=========== Experiment 2 - sumContainer2 
template-iterator-container.cpp:101: ; iu::sumContainer2<double>(vec1) = 16
template-iterator-container.cpp:102: ; iu::sumContainer2<int>(vec1) = 15
template-iterator-container.cpp:103: ; iu::sumContainer2<double>(list1) = 16
template-iterator-container.cpp:104: ; iu::sumContainer2<int>(list2) = 114

=========== Experiment 3 - printContainer 

Contents of carray  = 1, 2, 4.5, 2.5, 6, 
Contents of vec1  = 1, 2, 4.5, 2.5, 6, 
Contents of vec2  = c++, templates, awesome, binary, 
Contents of list1 = 1, 2, 4.5, 2.5, 6, 

=========== Experiment 4 - printContainer2 

Contents of vec1  = 1, 2, 4.5, 2.5, 6, 
Contents of vec2  = c++, templates, awesome, binary, 
Contents of list1 = 1, 2, 4.5, 2.5, 6, 

=========== Experiment 5 - for_each higher order function 

Contents of vec1  = 1, 2, 4.5, 2.5, 6, 
Contents of vec2  = c++, templates, awesome, binary, c++, templates, awesome, binary, 
Contents of m1  = 
  earth-gravity     9.810
          euler     2.718
             pi     3.142
              x     2.345

1.6.3 Example 2 - print any sequential container (typename)

template<class Container>
void printContents(Container& c){
     // Dependent type declaration 
     typename Container::iterator i;
     for(i = c.begin(); i != c.end(); i++)
             std::cout << " " << *i << "\n";
     std::cout << "\n";
}

Running: 

>> std::vector<double> xs{10.23, -24.23, 25.2, 100.34};
>> std::list<std::string> ds{"hello world", "C++", "HPC", "processor"};
>> 
>> printContents(xs)
 10.23
 -24.23
 25.2
 100.34

>> printContents(ds)
 hello world
 C++
 HPC
 processor

1.6.4 Example 3 - print map container

template<typename KEY, typename VALUE>
void printMap(std::map<KEY, VALUE>& mp, int w1 = 10, int w2 = 10){
     typename map<KEY, VALUE>::iterator it;
     for(it = mp.begin(); it != mp.end(); it++)
          std::cout << std::setw(w1) << it->first
                    << std::setw(w2) << it->second 
                    << "\n";
     std::cout << "\n";
}

Or, using for-range based loop: 

template<typename KEY, typename VALUE>
void printMap2(std::map<KEY, VALUE>& mp, int w1 = 10, int w2 = 10){
     for(const auto& p: mp)
         std::cout << std::setw(w1) << p.first
                   << std::setw(w2) << p.second 
                   << "\n";
     std::cout << "\n";
}

Running: 

>> std::map<std::string, int> m1 {{"x", 200}, {"y", 1000}, {"z", 3400}};
>> printMap(m1)
         x       200
         y      1000
         z      3400

>> printMap2(m1)
         x       200
         y      1000
         z      3400

>> auto m2 = std::map<int, std::string> {{100, "Argentina"}, {900, "Colombia"}, {80, "Brazil"}, {600, "Chile"}};
>> printMap(m2)
        80    Brazil
       100 Argentina
       600     Chile
       900  Colombia

1.6.5 Example 4 - print any associative container

template<typename Container>
void printAssoc(const Container& mp, int w1 = 10, int w2 = 10){
     for(const auto& it : mp)
        std::cout << std::setw(w1) << it.first
                  << std::setw(w2) << it.second 
                  << "\n";
     std::cout << "\n";
}

Running: 

auto m1a = std::map<std::string, int> {{"x", 200}, {"y", 1000}, {"z", 3400}};
auto m2a = std::unordered_map<std::string, int> {{"x", 200}, {"y", 1000}, {"z", 3400}};

 >> printAssoc(m1a)
          x       200
          y      1000
          z      3400

 >> printAssoc(m2a)
          z      3400
          y      1000
          x       200

1.7 Templates with Ranges

Example 1: 

template<class Range, class Function>
void forEachRange(const Range& range, Function func){
    for(const auto& x: range) func(x);
}

Testing: 

auto xs = std::vector<int>{1, 2, 3, 4, 5, 6, 7};

>> forEachRange(xs, [](int x){ std::cout << " x = " << x << std::endl;})
 x = 1
 x = 2
 x = 3
 x = 4
 x = 5
 x = 6
 x = 7

 >> auto list = std::deque<std::string>{ "c++", "asm", "rust", "DLang"};

 >> forEachRange(::list, [](const std::string& x){ 
                              std::cout << " => " << x << st => c++; })
  => asm
  => rust
  => DLang

Example 2: 

template<class Range, class Acc, class Function>
Acc foldRange(const Range& range, const Acc& init, Function func){
    auto acc = init;
    for(const auto& x: range) acc = func(acc, x);
    return acc;
}

Testing: 

//---------- std::vector --------------//

>> auto xs = std::vector<int>{1, 2, 3, 4, 5, 6, 7};
>> 1 + 2 + 3 + 4 + 5 + 6 + 7
(int) 28
>> foldRange(xs, 0, std::plus<int>())
(int) 28

>> 1 * 2 * 3 * 4 * 5 * 6 * 7
(int) 5040
>> foldRange(xs, 1, std::multiplies<int>())
(int) 5040

>> foldRange(xs, 0, [](int acc, int x){ return 10 * acc + x; })
(int) 1234567
>> 

//---------- std::deque -------------------//

>> auto ys = std::deque<int>{1, 2, 3, 4, 5, 6, 7};

>> foldRange(ys, 0, std::plus<int>())
(int) 28

>> foldRange(ys, 1, std::multiplies<int>())
(int) 5040
>> 

// ------------- std::set -----------------//

>> auto zs = std::set<int>{1, 2, 3, 4, 5, 6, 7};
>> 
>> foldRange(zs, 1, std::multiplies<int>())
(int) 5040
>>

1.8 Basic Template Specialization

Code example showing template specialization. As the code shows, the template specilization can be used for type introspection, type identification and implement reflection. 

#include <iostream>
#include <iomanip>    // Stream manipulator std::fixed, std::setw ... 
#include <vector>
#include <cmath>      // sin, cos, tan, exp ... M_PI, M_E ...
#include <functional> // std::function 

// ============= Example 1 ===============================//

// Check whether type is float point 
template<class T>
auto isFPNumber() -> bool {
     return false;
}
// Template specialization of isFPNumber for type float
template<> auto isFPNumber<float>() -> bool {
     return true;
}
// Template specialization of isFPNumber for type double 
template<> auto isFPNumber<double>() -> bool {
     return true;
}

// ============= Example 2 - Template specialization for runtime type identification ====//
// Note: this technique can be used for implemeting custom C++ reflection 

// Return name of a given type 
template<class Type>
auto TypeName() -> const char* { return "unknown"; }

#define REGISTER_TYPE(type)  template<> \
        auto TypeName<type>() -> const char* { return #type; } 

// Specialization for int type 
template<>
auto TypeName<int>() -> const char* { return "int"; }

// Automate boilerplate code using macros.
REGISTER_TYPE(bool);
REGISTER_TYPE(std::string);
REGISTER_TYPE(const char*);
REGISTER_TYPE(float);
REGISTER_TYPE(double);
REGISTER_TYPE(long);
REGISTER_TYPE(unsigned);
REGISTER_TYPE(char);
REGISTER_TYPE(long long);

// ============= Example 3 - Template with int argument specialization ===//
template<int>
const char* getNumberName(){
        return "I down't known";
}
template<> const char* getNumberName<0>(){ return "zero"; }
template<> const char* getNumberName<1>(){ return "one"; }
template<> const char* getNumberName<2>(){ return "two"; }
template<> const char* getNumberName<3>(){ return "three"; }

// ============= Example 4 - Template with bool argument specialization ====//
template<bool>
struct boolTemplate;

template<> struct boolTemplate<false>{
        static auto getName() -> const char* { return "false"; }
};
template<> struct boolTemplate<true>{
        static auto getName() -> const char* { return "true"; }
};

// ============= Example 5 - Check whether types are equal ====//
// Partial template specialization 

template<class A, class B>
struct type_equal{
        static bool get(){ return false; }
        enum { value = 0 };
};

// Partial specialisation
template<class A>
struct type_equal<A, A>{
        static bool get(){ return true; }
        enum { value = 1};
};

int main(){
      const char nl = '\n';
      std::cout << std::boolalpha;

      std::cout << nl << "EXPERIMENT 1 - Check whether type is float pointer" << nl;
      std::cout << "--------------------------------------------" << nl;    
      std::cout << "is float point type<int>    ? = " << isFPNumber<int>() << nl;
      std::cout << "is float point type<char>   ? = " << isFPNumber<char>() << nl;
      std::cout << "is float point type<float>  ? = " << isFPNumber<float>() << nl;
      std::cout << "is float point type<double> ? = " << isFPNumber<float>() << nl;

      std::cout << nl << "EXPERIMENT 2 - Type introspection" << nl;
      std::cout << "--------------------------------------------" << nl;    
      std::cout << "type = " << TypeName<int>() << nl;
      std::cout << "type = " << TypeName<char>() << nl;
      std::cout << "type = " << TypeName<float>() << nl;
      std::cout << "type = " << TypeName<const char*>() << nl;
      std::cout << "type = " << TypeName<std::string>() << nl;  

      std::cout << nl << "EXPERIMENT 3 - Templates with integers as arguments" << nl;
      std::cout << "--------------------------------------------" << nl;
      std::cout << "getNumberName<0>() = " << getNumberName<0>() << nl;
      std::cout << "getNumberName<1>() = " << getNumberName<1>() << nl;
      std::cout << "getNumberName<2>() = " << getNumberName<2>() << nl;
      std::cout << "getNumberName<10>() = " << getNumberName<10>() << nl;
      std::cout << "getNumberName<14>() = " << getNumberName<14>() << nl;

      std::cout << nl << "EXPERIMENT 4 - Templates with bool as arguments" << nl;
      std::cout << "--------------------------------------------" << nl;    
      std::cout << "boolTemplate<false>::getName>()  = " << boolTemplate<false>::getName() << nl;
      std::cout << "boolTemplate<true>::getName>()   = " << boolTemplate<true>::getName() << nl;

      std::cout << nl << "Check whether types are equal" << nl;
      std::cout << "type_equal<int, char>::get()       = "  << type_equal<int, char>::get() << nl;  
      std::cout << "type_equal<char, double>::get()    = "  << type_equal<char, double>::get() << nl;
      std::cout << "type_equal<double, double>::get()  = "  << type_equal<double, double>::get() << nl;
      std::cout << "type_equal<int, int>::get()        = "  << type_equal<int, int>::get() << nl;

      if(type_equal<int, double>::value)
           std::cout << "[1] Types are equal\n";
      else
           std::cout << "[1] Types are not equal\n";

      if(type_equal<double, double>::value)
          std::cout << "[2] Types are equal\n";
      else
         std::cout << "[2] Types are not equal\n";
        return 0;
}

Program output: 

$ clang++ template-specialization1.cpp -o template-specialization1.bin -g -std=c++11 -Wall -Wextra 
$ ./template-specialization1.bin

EXPERIMENT 1 - Check whether type is float pointer
--------------------------------------------
is float point type<int>    ? = false
is float point type<char>   ? = false
is float point type<float>  ? = true
is float point type<double> ? = true

EXPERIMENT 2 - Type introspection
--------------------------------------------
type = int
type = char
type = float
type = const char*
type = std::string

EXPERIMENT 3 - Templates with integers as arguments
--------------------------------------------
getNumberName<0>() = zero
getNumberName<1>() = one
getNumberName<2>() = two
getNumberName<10>() = I down't known
getNumberName<14>() = I down't known

EXPERIMENT 4 - Templates with bool as arguments
--------------------------------------------
boolTemplate<false>::getName>()  = false
boolTemplate<true>::getName>()   = true

Check whether types are equal
type_equal<int, char>::get()       = false
type_equal<char, double>::get()    = false
type_equal<double, double>::get()  = true
type_equal<int, int>::get()        = true
[1] Types are not equal
[2] Types are equal

1.9 Template Type Alias - 'using' (C++11)

In addition to be useful for creating type alias, the keyword "using" can also be used for defining template type alias or parametrized type alias.

Basic Example:

Type alias for shared_ptr: 

template<typename T>
using sh = std::shared_ptr<T>

// Usage: 
std::vector<sh<DataObjeect>> objects;

Type alias for unique_ptr: 

template<typename T>
using up = std::unique_ptr<T>

// Usage: 
std::vector<up<DataObjeect>> objects;

Type alias for polymorphic objects containers: 

 #include <memory>
 #include <vector> 

 // Vector of shared pointer for storing polymorphic objects (shared ownership)
 template<typename T>
 using SHVector<T> = std::vector<std::shared_ptr<T>>;

 // Vector of shared pointer for storing polymorphic objects (unique ownership)
 template<typename T>
 using UPVector<T> = std::vector<std::unique_ptr<T>>;


 class Base{
   ... 
   public:
     ~Base() = default;
     virtual double Price(double x) const = 0 ;
 };

class DerivedA: public Base{
  ... 
  double Price(double x) const override 
  {
      ... // Compute Price --- // 
  }
};

class DerivedB: public Base{
  ... 
  double Price(double x) const override 
 {
  ... // Compute Price --- // 
  }
};


// Usage: 
SHVector<Base> list;
list.reserve(10);
list.push_back( std::make_shared<Base>());
list.push_back( std::make_shared<DerivedA>(arg0, arg1, arg2, ... argN));
list.push_back( std::make_shared<DerivedB>(arg0, arg1, arg2, ... argN));

for(auto const& impl : list) 
  std::cout << "Price = " << impl->Price(10.0) << std::endl;

Example: std::function container type alias

Type synonym: 

template<class T>
using Action = std::function<T (int)>;

Usage: 

template<class T>
void doTimes(int n, Action<T> action){
     for(int i = 0; i < n; i++)
        std::cout << " i = 0; x = " << action(i) << "\n";
}

>> doTimes<double>(3, [](int i){ return 3.0 * i + 4.5; })
 i = 0; x = 4.5
 i = 0; x = 7.5
 i = 0; x = 10.5
>> 

>> doTimes<char>(6, [](int i){ return 65 + i; })
 i = 0; x = A
 i = 0; x = B
 i = 0; x = C
 i = 0; x = D
 i = 0; x = E
 i = 0; x = F
>>

1.10 Templates with default arguments

Example: Array allocated on the stack memory.

  • File: default-template-args.C
#include <iostream>
#include <string>
#include <ostream> 

// Array allocated on stack with size 10.
template <typename Element, size_t Size = 10>
class Array{
private:
        Element m_data [Size];
public:
   auto size() -> size_t {
       return Size;
   }
   auto fill(const Element& t) -> void{
       for(size_t i = 0; i < Size; i++)
           m_data[i] = t;
   }
   auto operator [] (size_t index) -> Element& {
       return m_data[index];
   }
   auto begin() const -> decltype(std::begin(m_data)) {
       return std::begin(m_data);
   }
   auto end() const -> decltype(std::end(m_data)) {
       return std::end(m_data);
   }
   auto print(const std::string& name, std::ostream& os = std::cout) const -> void{
       os << name << " = ";
       for(auto& x: *this)
          os << x << " " << std::flush;
       os << "\n";
   }
};

void default_template_args(){
     Array<double> s1;
     std::cout << "s1.size() = " << s1.size() << "\n";
     s1.fill(3.0);
     s1[0] = 8.23;
     s1[1] = -10.2;
     s1[3] = 0.0;
     s1.print("s1");

     Array<std::string, 4> s2;
     std::cout << "s2.size() = " << s2.size() << "\n";
     s2.fill("C++");
     s2.print("s2");
     s2[0] = "PlusPlus";
     s2[1] = "CPP";
     s2[2] = "ASM";
     s2.print("s2");
}

Running on CLING REPL: 

>> .X default-template-args.C 
s1.size() = 10
s1 = 8.23 -10.2 3 0 3 3 3 3 3 3 
s2.size() = 4
s2 = C++ C++ C++ C++ 
s2 = PlusPlus CPP ASM C++

1.11 Templates with C-arrays

File: array_template.cpp 

#include <iostream>
#include <iomanip>

/* Pass array by reference: T (&arr) [N} */
template<typename T, size_t N>
auto array_info(  const char* name, T (& arr) [N] )
{
    std::cout << "\n [INFO] Information of array: " << name << std::endl;
    std::cout << " => Array size = " << N << std::endl;

    std::cout <<" => Array value = ";
    for(size_t i = 0; i < N ; i++) {
        std::cout << " " << arr[i];
    }
    std::cout << std::endl;

}

// Template specialization for 'char'
template<size_t N>
auto array_info(const char* name, char (& arr) [N])
{
    std::cout << "\n [INFO] Information of array: " << name << std::endl;
    std::cout << " => Array size [1] = " << N << std::endl;
    std::cout << " => Array size [2] = " << std::size(arr) << std::endl;

    std::cout <<" => Array value [char] = ";
    for(size_t i = 0; i < N ; i++) {
        if(std::isprint(arr[i]))
            std::cout << " " << arr[i];
        else
            std::cout << " \\x" << static_cast<int>(arr[i]);
    }
    std::cout << std::endl;
}

int main(int argc, char** argv)
{
    std::cout << std::fixed << std::setprecision(3);

    double arr1 [] = { 3.505, 10.5, -90.25, 100.56, 3.1515};
    array_info("arr1", arr1);

    char arr2 [10] = {'a', 'k', 'j', 'm'};
    array_info("arr2", arr2);

    const char* arr3 [] = { "Hello", "world", "C++20" };
    array_info("arr3", arr3);
    return 0;
}

Program output: 

[INFO] Information of array: arr1
=> Array size = 5
=> Array value =  3.505 10.500 -90.250 100.560 3.151

[INFO] Information of array: arr2
=> Array size [1] = 10
=> Array size [2] = 10
=> Array value [char] =  a k j m \x0 \x0 \x0 \x0 \x0 \x0

[INFO] Information of array: arr3
=> Array size = 3
=> Array value =  Hello world C++20

1.12 Implementing Higher Order Functions with templates

/**   File:     template-hof1.cpp 
  *  Brief:    Shows how to implement template higher order functions which operates on containers.
  *  Features: Template metaprogramming, C++11, functional programming and STL.
  ****************************************************************************/
#include <iostream>
#include <cmath>
#include <list>
#include <deque>
#include <vector>
#include <functional> 
#include <iomanip>

/** Apply a function to every element of a container */
template<class ELEM, class ALLOC, template<class, class> class CONTAINER>
void forRange1(CONTAINER<ELEM, ALLOC>& cont, std::function<void (ELEM&)> fn){
     for(auto i =  std::begin(cont); i != std::end(cont); i++)
       fn(*i);
}

/** Apply a function to every element of a container */
template<class CONTAINER>
void forRange2(CONTAINER& cont, std::function<void (decltype(cont.front()))> fn){
    for(auto i =  std::begin(cont); i != std::end(cont); i++)
       fn(*i);
}

/** Template for folding over a container in a similar way to the higher order function fold. 
 * Note: 
 * + CONTAINER parameter accepts any argument which has .begin() and .end() methods 
 *   returning iterators. 
 * + STEPFN type parameters accepts any function-object, function pointer or lambda 
 *   whith the following signature: (ACC, X) => ACC where ACC is the accumulator type 
 *   and X is the type of the container element. 
 */
template<class CONTAINER, class ACC, class STEPFN>
auto foldRange(CONTAINER& cont, const ACC& init, STEPFN fn) -> ACC {
     ACC acc{init};
     for(auto i =  std::begin(cont); i != std::end(cont); i++)
        acc = fn(*i, acc);
     return acc;
}

int main(){
        std::ios_base::sync_with_stdio(false);

        std::vector<int> vec{1, 2, 400, 100};
        std::list<int>   lst{1, 2, 400, 100};

        // Requires template argument 
        std::cout << "===== EXPERIMENT 1 =================\n";
                std::cout << "forRange1 - Vector" << "\n";
        forRange1<int>(vec, [](int x){ std::cout << std::setw(5) << x << " "; });
        std::cout << "\n";
        std::cout << "forRange1 - List" << "\n";
        forRange1<int>(lst, [](int x){ std::cout << std::setw(5) << x << " "; });
        std::cout << "\n";

        // Doesn't require the template argument as the compiler can infer its type.
        std::cout << "===== EXPERIMENT 2 =================\n";
        std::cout << "forRange1 - Vector" << "\n";
        forRange2(vec, [](int x){ std::cout << std::setw(5) << x << " "; });
        std::cout << "\n";
        std::cout << "forRange1 - list" << "\n";
        forRange2(lst, [](int x){ std::cout << std::setw(5) << x << " "; });
        std::cout << "\n";

        std::cout << "===== EXPERIMENT 3 =================\n";
        int result1 = foldRange(vec, 0, [](int x, int acc){
                                                return x + acc;
                                          });   
        std::cout << "sum(vec1) = " << result1 << "\n" ;
        int result2 = foldRange(lst, 0, std::plus<int>());  
        std::cout << "sum(lst) = " << result2 << "\n" ;

        std::cout << "product(lst) = " << foldRange(lst, 1, std::multiplies<int>()) << "\n" ;
        return 0;
}

Output: 

clang++ template-hof1.cpp -o template-hof1.bin -g -std=c++11 -Wall -Wextra && ./template-hof1.bin
===== EXPERIMENT 1 =================
forRange1 - Vector
    1     2   400   100 
forRange1 - List
    1     2   400   100 
===== EXPERIMENT 2 =================
forRange1 - Vector
    1     2   400   100 
forRange1 - list
    1     2   400   100 
===== EXPERIMENT 3 =================
sum(vec1) = 503
sum(lst) = 503
product(lst) = 80000

1.13 Metafunctions or type traits

1.13.1 Overview

Metafunction (aka type traits) is a template metaprogramming technique for type introspection, type manipulation and type computation. This idiom uses templates, template specialization, structs (classes with everything public) and constexpr in C++11.

This section contains examples about template metafunctions. For more information about this subject and further reading, see:

A meta function has the forms:

  • Meta function which returns type.
// Doesn't matter using typename T1, typename T2
// or using class T1, class T2 ..
template<class T1, class T2 ...>
struct meta_function {
    // Before C++11
    // Meta function which returns type 
    using type = ... ;
};

template<typename T1, typename T2 ...>
struct meta_function {
    // Before C++11
    // Meta function which returns type 
    using type = ... ;
};

// Before C++11 
template<class T1, class T2 ...>
struct meta_function {
   typedef ... ... type;
};

// Usage: 
using type_synonym =  meta_function<T1, T2, ...>::type ;
// Or in before C++11
typedef  meta_function<T1, T2, ...>::type type_synonym;
  • Meta function which returns value.
// At least C++11
template<class T1, class T2 ...>
struct meta_function {
    // Requires at aleast C++11
    // Meta function which returns type 
    static constexpr TYPE value = ... 
};

// Before C++11
template<class T1, class T2 ...>
struct meta_function {
    // Requires at aleast C++11
    // Meta function which returns type 
    static const TYPE value = ... 
};

// Usage:
TYPE result = meta_function<T1, T2, ..>::value;

Further References:

1.13.2 Example

Example

Example in:

Highlights:

  • The metafunction isPointer checks whether a given type is a pointer.
template<class T>
struct isPointer{
    static constexpr bool value = false;
    constexpr bool operator()() const { return false; }
};

template<class T>
struct isPointer<T*>{
    static constexpr bool value = true;
    constexpr bool operator()() const { return true; }
};

Sample usage: 

std::cout << "isPointer<short*>::value  = " << isPointer<short*>::value << "\n";
std::cout << "isPointer<short>::value   = " << isPointer<short>::value << "\n";
std::cout << "isPointer<double>::value  = " << isPointer<double>::value << "\n";
std::cout << "isPointer<double*>::value = " << isPointer<double*>::value << "\n";

Output: 

isPointer<short*>::value  = true
isPointer<short>::value   = false
isPointer<double>::value  = false
isPointer<double*>::value = true
  • The meta function removePointer turns any pointer type into a non-pointer type removing the star operator.
// Partial specilization
template<class T> struct removePointer{
    typedef T type;
};
template<class T> struct removePointer<T*>{
    typedef T type;
};

Usage: 

disp(Typeinfo<removePointer<double>::type>::name);
disp(Typeinfo<removePointer<double*>::type>::name);
disp(Typeinfo<removePointer<const char*>::type>::name);

Output: 

template-metafunction.cpp:175: ; Typeinfo<removePointer<double>::type>::name = double
template-metafunction.cpp:176: ; Typeinfo<removePointer<double*>::type>::name = double
template-metafunction.cpp:177: ; Typeinfo<removePointer<const char*>::type>::name = const char
  • The metafunction Typeinfo computes basic information about types at compile-time. As this "metafunction" relies on template specialization, it requires defining template specialization for all supported types what can be cumbersome. In order to avoid the specialization boilerplate code, the macro REGISTER_TYPE_INFO is used to register the supported types.
template<typename T>
struct Typeinfo{
     static constexpr const char* name   = "unknown";
     static constexpr size_t      size   = sizeof(T);
     static constexpr bool        isNumber   = false;
     static constexpr bool        isPointer = ::isPointer<T>::value;
     static constexpr bool        isConst    = ::isConst<T>::value;     
};

// Macro for type registration 
#define REGISTER_TYPE_INFO(type, isNumberFlag) \
        template<> struct Typeinfo<type>{ \
                static constexpr const char* name       = #type; \
                static constexpr size_t      size       = sizeof(type); \
                static constexpr bool        isNumber   = isNumberFlag; \
                static constexpr bool        isPointer  = ::isPointer<type>::value; \
                static constexpr bool        isConst    = ::isConst<type>::value;   \
        }

 // Type registration 
 REGISTER_TYPE_INFO(bool, false);
 REGISTER_TYPE_INFO(char, false);

Usage example: 

std::cout << "Type info for " << Typeinfo<int>>::name 
          << " size = " << Typeinfo<int>::size 
          << " isPointer = " << Typeinfo<int>::isPointer 
          << "\n";

Complete Program output: (file:src/template-metafunction.cpp) 

$ clang++ template-metafunction.cpp -o template-metafunction.bin -g -std=c++11 -Wall -Wextra  
./template-metafunction.bin

isPointerOLD<short*>::value  = 1
isPointerOLD<short>::value   = 0
isPointerOLD<double>::value  = 0
isPointerOLD<double*>::value = 1
isPointer<short*>::value  = true
isPointer<short>::value   = false
isPointer<double>::value  = false
isPointer<double*>::value = true
isPointer<short*>()()  = true
isPointer<short>()()   = false
isPointer<double>()()  = false
isPointer<double*>()() = true
Type Info: name =            bool ; bytes =    1 ; isNumber = false ; isPointer = false ; isConst = false
Type Info: name =            char ; bytes =    1 ; isNumber = false ; isPointer = false ; isConst = false
Type Info: name =     std::string ; bytes =   32 ; isNumber = false ; isPointer = false ; isConst = false
Type Info: name =             int ; bytes =    4 ; isNumber =  true ; isPointer = false ; isConst = false
Type Info: name =           short ; bytes =    2 ; isNumber =  true ; isPointer = false ; isConst = false
Type Info: name =           float ; bytes =    4 ; isNumber =  true ; isPointer = false ; isConst = false
Type Info: name =          double ; bytes =    8 ; isNumber =  true ; isPointer = false ; isConst = false
Type Info: name =     const char* ; bytes =    8 ; isNumber =  true ; isPointer =  true ; isConst =  true
Type Info: name =          float* ; bytes =    8 ; isNumber = false ; isPointer =  true ; isConst = false
Type Info: name =         double* ; bytes =    8 ; isNumber = false ; isPointer =  true ; isConst = false
Type Info: name =   const double& ; bytes =    8 ; isNumber = false ; isPointer = false ; isConst =  true
template-metafunction.cpp:175: ; Typeinfo<removePointer<double>::type>::name = double
template-metafunction.cpp:176: ; Typeinfo<removePointer<double*>::type>::name = double
template-metafunction.cpp:177: ; Typeinfo<removePointer<const char*>::type>::name = const char

1.14 Predefined type traits in <type_traits>

The C++11 header <type_traits> (before boost.type_traits) provide many useful type traits, also known as metafunction, for querying and transforming types at compile-time. In addition to those operations, the type traits available in this header can also be used for optimizing templates by specializing them for specific types.

Documentation:

Examples:

  • To use the C++11's type traits, it is necessary to include the header <type_traits>
#include <iostream> 
#include <string> 
#include <type_traits>
  • Type trait std::is_void
    • Checks whether type is void.
>> std::is_void<void>::value
(const bool) true
>> 
>> std::is_void<int>::value
(const bool) false
>> std::is_void<void*>::value
(const bool) false
>> 
>> std::is_void<bool>::value
(const bool) false
>> 

template<class T>
void inspectType(){
     if(std::is_void<T>::value)
        std::cout << "Type is void" << "\n";
     else
        std::cout << "Type is not void" << "\n";
}

>> 
>> inspectType<void>()
Type is void
>> inspectType<bool>()
Type is not void
>> inspectType<int>()
Type is not void
>>
  • Check whether type is float point: std::is_floating_point
>> std::is_floating_point<float>::value
(const bool) true
>> std::is_floating_point<double>::value
(const bool) true
>> std::is_floating_point<long double>::value
(const bool) true
>> std::is_floating_point<int>::value
(const bool) false
>> std::is_floating_point<char>::value
(const bool) false
>>
  • Check whether type is interger: std::is_integral
>> 
>> std::is_integral<int>::value
(const bool) true
>> std::is_integral<long>::value
(const bool) true
>> std::is_integral<char>::value
(const bool) true
>> std::is_integral<unsigned char>::value
(const bool) true
>> std::is_integral<double>::value
(const bool) false
>> std::is_integral<bool>::value
(const bool) true
>> std::is_integral<void>::value
(const bool) false
>>
  • Check whether type is const
>> std::is_const<int>::value
(const bool) false
>> std::is_const<const int>::value
(const bool) true
>> std::is_const<const char*>::value
(const bool) false
>> std::is_const<const std::string&>::value
(const bool) false
  • Check whether type is a reference (&)
>> 
>> std::is_reference<int&>::value
(const bool) true
>> std::is_reference<const int&>::value
(const bool) true
>> std::is_reference<double&>::value
(const bool) true
>> std::is_reference<double>::value
(const bool) false
>> std::is_reference<double*>::value
(const bool) false
>>

Type relationship

  • Check whether type are equal.
// Returns true if types are the same 
>> std::is_same<int, int>::value
(const bool) true
>> std::is_same<int, float>::value
(const bool) false
>> std::is_same<float, float>::value
(const bool) true
>>
  • Checks whether types are derived.
    • std::is_base_of<A, B>::value returns true if A is a base type (superclass) of B or B is derived class of A.
class A{
public:
};
class B: public A{
public:
};
class Z{
};

>> std::is_base_of<A, B>::value
(const bool) true
>> std::is_base_of<B, A>::value
(const bool) false
>> 
>> std::is_base_of<B, Z>::value
(const bool) false
>> std::is_base_of<Z, A>::value
(const bool) false
>>

1.15 Variadic Templates

This code shows examples about variadic templates in C++11 and newer standards.

File: file:src/template-variadic.cpp

Code Highlights:

  • Print a sequence of heterogenous arguments.
template<typename T>
void printTypes(const T& x){    
     std::cout << std::left << std::setw(15) << x
               << std::setw(10) << std::right << " size = "
               << std::setw(2) << sizeof(x) << "\n";
     std::clog << " [TRACE] Base case => x = " << x << "\n";
}
// Variadic template arguments 
template<typename T, typename ... Types>
void printTypes(const T& x, const Types ... args){
     std::cout << std::left << std::setw(15) << x
               << std::setw(10) << std::right << " size = "
               << std::setw(2) << sizeof(x) << "\n";
     printTypes(args ...);
}

Usage: 

printTypes("hello world", 10, 'x', 20.23f, true, NAN);

Ouput: 

hello world       size = 12
10                size =  4
x                 size =  1
20.23             size =  4
1                 size =  1
nan               size =  4
  • Create a function that applies a member function to a given object.
template<class T, class R, class ... Args>
auto makeCommand(
     // Pointer to member function 
     R (T::* pMemfn) (Args ... args),
     // Member function arguments 
     Args ... arglist) -> std::function<R (T& obj)> {
     return [=](T& obj){ return (obj.*pMemfn)(arglist ...); };
}

Usage: 

CNCMachine mach1("7Z9FA");
CNCMachine mach2("MY9FT");
auto setSpeed10 = makeCommand(&CNCMachine::setSpeed, 10);
auto shutdown   = makeCommand(&CNCMachine::shutdown);
setSpeed10(mach1);
setSpeed10(mach2);
shutdown(mach2);
  • Dynamic load an [U] nix-shared library or shared object.
/** Type synonym for shared library handler 
 *  Requires: #include <dlfcn.h> and -ldl linker flag */
using LibHandle = std::unique_ptr<void, std::function<void (void*)>>;

auto loadDLL(const std::string& libPath) -> LibHandle {
     // Return unique_ptr for RAAI -> Resource Acquisition is Initialization
     // releasing closing handle when the unique_ptr goes out of scope. 
     return LibHandle(
             dlopen(libPath.c_str(), RTLD_LAZY),
             [](void* h){
                std::cout << " [INFO] Shared library handle released OK." << "\n";
                dlclose(h);
             });        
}

/** Load symbol from shared library 
  *  Requires: #include <dlfcn.h> and -ldl linker flag */
template<typename Function>
auto loadSymbol(const LibHandle& handle, const std::string& symbol) -> Function* {
     void* voidptr = dlsym(handle.get(), symbol.c_str());
     if(voidptr == nullptr)
       return nullptr;
     return reinterpret_cast<Function*>(voidptr);
}

Usage: 

// GNU Scientific Library - Linear Algebra CBLAS 
auto handle1 = loadDLL("/usr/lib64/libgslcblas.so");
using cblas_daxpy_type = void (int, double, const double*, int, double*, int);
auto cblas_daxpy = loadSymbol<cblas_daxpy_type>(handle1, "cblas_daxpy");
// Or 
auto cblas_daxpy = loadSymbol<void (int, double, const double*, int, double*, int)>(handle1, "cblas_daxpy");

auto xs = std::vector<double>{ 3.0, 5.0, 6.0, 10.0, 8.0};
auto ys = std::vector<double>{ 2.0, 2.0, 2.0,  2.0, 2.0};
printContainer("xs", xs);
printContainer("ys", ys);
// Compute xs * 4.0 + ys
cblas_daxpy(xs.size(), 4.0, &xs[0], 1, &ys[0], 1);
printContainer("ys", ys);

Output: 

 [INFO]  Loaded clblas_daxpy OK!
xs = 3, 5, 6, 10, 8, 
ys = 2, 2, 2, 2, 2, 
ys = 14, 22, 26, 42, 34, 
 [INFO] Shared library handle released OK.

Complete Output: 

$ g++ template-variadic.cpp -o template-variadic.bin -g -std=c++11 -Wall -Wextra -ldl 
$ ./template-variadic.bin

EXPERIMENT 1 = Function of many argument for printing all of them
---------------------------------------
hello world       size = 12
10                size =  4
x                 size =  1
20.23             size =  4
1                 size =  1
nan               size =  4
 [TRACE] Base case => x = nan

EXPERIMENT 2 = Indirect method invocation
--------------------------------------
[MACHINE] id = 7Z9FA Set machine speed to level 10
[MACHINE] id = MY9FT Set machine speed to level 10
[MACHINE] id = 7Z9FA  Equipment to position set to  x = 10 ; y = -20
[MACHINE] id = MY9FT  Equipment to position set to  x = 10 ; y = -20
[MACHINE] id = 7Z9FA Shutdown equipment
[MACHINE] id = MY9FT Shutdown equipment

EXPERIMENT 3 = Dynamic Loading from shared library (libgslcblas.so) 
--------------------------------------
 [INFO]  Loaded clblas_daxpy OK!
xs = 3, 5, 6, 10, 8, 
ys = 2, 2, 2, 2, 2, 
ys = 14, 22, 26, 42, 34, 
 [INFO] Shared library handle released OK.

References:

1.16 Variadic Templates - sizeof… operator

The operator sizeof…(args) is used for counting the number of template arguments.

  • Class or function with type parameters.
template<class ... ARGUMENTS>
Return FUNCTION(ARGUMENTS ... arguments){
  ..... 
}

template<class ... ARGUMENTS>
struct AStruct{
  ..... 
};
  • Operator: sizeof…(ARGUMENTS)
size_t NumberOfTypeArguments = sizeof...(ARGUMENTS);
  • Count number of type parameters
template<typename ... Args>
void countArgs1(){
     std::cout << "Number of args is equal to = " << sizeof...(Args) << "\n";
}

Running: 

>> countArgs1()
Number of args is equal to = 0

>> countArgs1<int, double, char>()
Number of args is equal to = 3

>> countArgs1<int, double, char, std::string>()
Number of args is equal to = 4
  • Count number of template numeric arguments
template<size_t ... Number>
void countNumberArguments(){
     std::cout << "Number of args is equal to = " << sizeof...(Number) << "\n";
}

Running: 

>> countNumberArguments()
Number of args is equal to = 0

>> countNumberArguments<>()
Number of args is equal to = 0

>> countNumberArguments<1>()
Number of args is equal to = 1

>> countNumberArguments<1, 3>()
Number of args is equal to = 2

>> countNumberArguments<1, 3, 5, 6, 7, 10>()
Number of args is equal to = 6
  • Count number of function arguments
// Or:
template<class ... Params>
void countParameters(Params ... params){
     std::cout << "Number of parameters equal to = " << sizeof...(params) << "\n";
}

Running: 

>> countParameters()
Number of parameters equal to = 0

>> countParameters(10)
Number of parameters equal to = 1

>> countParameters('x')
Number of parameters equal to = 1

>> countParameters(12, 'x', "hello world", 3.34)
Number of parameters equal to = 4

1.17 Variadic Templates arguments expansion

  • Example 0:

Expand numeric template arguments into a std::vector. 

template<size_t ... Numbers>
auto getNumberParameters() -> std::vector<size_t>
{
    return std::vector<size_t> { Numbers ... };
}

Running: 

>> .L script-parampack.C
>> 
>> getNumberParameters()
(std::vector<size_t>) {}
>> getNumberParameters<>()
(std::vector<size_t>) {}
>> 
>> getNumberParameters<0>()
(std::vector<size_t>) { 0 }
>> getNumberParameters<0, 10, 56, 100, 5, 3>()
(std::vector<size_t>) { 0, 10, 56, 100, 5, 3 }
>>
  • Example 1:

Get deque container containing the size in bytes of every type from the parameter pack (arguments of a variadic template). 

// Return a deque containing the size in bytes of each type from the
// parameter pack (types arguments).
template<typename ... Types>
auto getSizeList() -> std::deque<size_t> {
     // { ... } Intializer list - used for 
     // C++11 default intialization feature. 
     return std::deque<size_t> { sizeof(Types) ... };   
}

Running: 

>> getSizeList()
(std::deque<size_t>) {}

>> getSizeList<>()
(std::deque<size_t>) {}

>> getSizeList<char>()
(std::deque<size_t>) { 1 }

>> getSizeList<double>()
(std::deque<size_t>) { 8 }

>> getSizeList<char, int, double, long double, std::string>()
(std::deque<size_t>) { 1, 4, 8, 16, 32 }
  • Example 2:

Example: modify example 1 for requiring at least one type parameter. 

template<typename Type0, typename ... Types>
auto getSizeList2() -> std::deque<size_t> {
     return std::deque<size_t> { sizeof(Type0), sizeof(Types) ... };    
}

Running: 

>> getSizeList2<>()
ROOT_prompt_2:1:1: error: no matching function for call to 'getSizeList2'
getSizeList2<>()
^~~~~~~~~~~~~~
/home/archbox/root-scripts/script-parampack.C:41:6: note: candidate template ignored: couldn't infer template argument 'Type0'
auto getSizeList2() -> std::deque<size_t> {
   ^
>> getSizeList2<char>()
(std::deque<size_t>) { 1 }

>> getSizeList2<double>()
(std::deque<size_t>) { 8 }

>> getSizeList2<double, int, char, long double, std::string>()
(std::deque<size_t>) { 8, 4, 1, 16, 32 }
>>

Example 3:

Print RTTI (Runtime Type Information) about types parameters. 

struct TypeInfo
{
    TypeInfo(const std::string& name, unsigned int hash_code, size_t size)
     : name(name),
       hash_code(hash_code),
       size(size)
    {       
    }
    std::string   name;
    unsigned long hash_code;
    size_t        size; 
};

template<typename ... Types>
auto printTypesInfoFromRTTI() -> void
{
    auto tlist = std::vector<TypeInfo> {
            TypeInfo{
               typeid(Types).name(),
               typeid(Types).hash_code(),
               sizeof(Types)
                    } ... };
    std::cout << std::setw(5)  << "Name"
              << std::setw(5)  << "Size"
              << std::setw(15) << "Hash"
              << "\n";
    std::stringstream ss;   
    for(const auto& x: tlist){
        ss.str("");
        ss.clear();
        ss << "0x" << std::hex << x.hash_code;
        std::cout << std::right
                  << std::setw(5)  << x.name
                  << std::setw(5)  << x.size
                  << std::setw(15) << ss.str()
                  << "\n";
        }
} //--- End of printTypesInfoFromRTTI() ----- //

Running (ROOT/Cling REPL): 

>> printTypesInfoFromRTTI<>()
 Name Size           Hash
>> 
>> printTypesInfoFromRTTI<char>()
 Name Size           Hash
    c    1     0x2479fc8d
>> 
>> printTypesInfoFromRTTI<char, int, double, long double>()
 Name Size           Hash
    c    1     0x2479fc8d
    i    4     0xb675de06
    d    8     0x44573475
    e   16     0xbbbbed2c

1.18 C++17 Variadic Template - Fold Expressions

C++17 fold expression features allow to expand and process variadic template type arguments, also known as parameter pack, without complicated recursion and function overloads.

Syntax:

Index Syntax Description
1 ( pack op … ) Unary Right Fold
2 ( … op pack) Unarfy Left Fold
3 (pack op … op init) Binary Right Fold
4 (init op … op pack) Binary Left Fold
  • Pack - Parameter pack
  • init - "an expression that does not contain an unexpanded parameter pack and does not contain an operator with precedence lower than cast at the top level (formally, a cast-expression)"
  • OP - Operator that can be any of the 32 supported operators:
+ - * / % ^ & | = < > << >> += -= *= /= %= ^= &= 
|= <<= >>= == != <= >= && || , .* ->*.

Example:

Compilation: 

# Compile with GCC 
$ g++ fold-expressions1.cpp -o fold-expressions1.bin -std=c++1z -g -O0 -Wall
# Compile with Clang 
$ clang++ fold-expressions1.cpp -o fold-expressions1.bin -std=c++1z -g -O0 -Wall
# Run 
$ ./fold-expressions1.bin

Headers: 

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <functional>
#include <tuple>
#include <any>

Function multiply: 

template<typename ... Args>
auto multiply(Args ... args)
{
    return (args * ...);
}

Function printArguments: 

template<typename ... Args>
void printArguments(Args&& ...  args )
{
   ((std::cout << typeid(args).name()  << " " << args << std::endl), ...);
}

Function GetTypesFromArgs1: 

template<typename ... Args>
std::vector<std::type_info const*>
GetTypesFromArgs1(){
    std::vector<std::type_info const*> tinfo;
    std::cout << "Received " << sizeof...(Args)
              << " types arguments" << std::endl;
    ((tinfo.push_back(&typeid(Args))), ...) ;
    return tinfo;
}

Function GetTypesFromArgs2: 

template<typename ... Args>
std::vector<std::type_info const*>
GetTypesFromArgs2(Args const& ... args){    
    std::cout << "Received " << sizeof...(Args)
              << " types arguments" << std::endl;
    return {&typeid(args) ...};
}

Main Function:

Experiment 1: 

std::cout << "\n ======= EXPERIMENT 1 ===============\n";   
std::cout << " => Result 1 = " << multiply(1, 2, 3, 4, 5, 6) << std::endl;
std::cout << " => Result 2 = " << multiply(3.5, 1.65, 0.25, 10.98, 100.5, 6) << std::endl;

Output: 

======= EXPERIMENT 1 ===============
=> Result 1 = 720
=> Result 2 = 9558.98

Experiment 2: 

std::cout << "\n ======= EXPERIMENT 2 ===============\n";
printArguments(10, 200.5, "hello world", 'x');

Output: 

 ======= EXPERIMENT 2 ===============
i 10
d 200.5
A12_c hello world
c x

Experiment 3: 

std::cout << "\n ======= EXPERIMENT 3 ===============\n";
auto tinfo = GetTypesFromArgs1<int, double, const char*, std::string>();
for(auto const& t: tinfo)
{
     std::cout << "Name = " << t->name()
               << " - id = " << t->hash_code()
               << std::endl;
}

Output: 

======= EXPERIMENT 3 ===============
Received 4 types arguments
Name = i - id = 6253375586064260614
Name = d - id = 14494284460613645429
Name = PKc - id = 3698062409364629473
Name = NSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE - id = 5774750460303204477

Experiment 4: 

std::cout << "\n ======= EXPERIMENT 4 ===============\n";
auto tinfo2 = GetTypesFromArgs2(200, 'x', 9.87, std::string("hello world"), "CPP17");
for(auto const& t: tinfo2)
{
     std::cout << "Name = " << t->name()
               << " - id = " << t->hash_code()
               << std::endl;
}

Output: 

 ======= EXPERIMENT 4 ===============
Received 5 types arguments
Name = i - id = 6253375586064260614
Name = c - id = 10959529184379665549
Name = d - id = 14494284460613645429
Name = NSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE - id = 5774750460303204477
Name = A6_c - id = 15419073316311588377

1.19 SFINAE - Substution Is Not a Failure

1.19.1 Fundamentals

SFINAE stands for Substition Failure Is Not An Error. It was introduced by David Vandervood in book "C++ Templates: The Complete Guide". The SFINAE technique is peformed by adding new overload functions (function with same name and different type signatures) for preveting compilation error during the template parameter type substitution. When a substition failure happens, the compiler looks for a the next function overload, if the substition fails again and there are no more candidates, the compiler will generate an error.

Example: 1 

#include <iostream>

struct AStruct{
   using ASubtype = int;
};

class AStructB{
public:   
   using ASubtype = const char*;
};

template<typename T> void AfunctionTemplate(typename T::ASubtype value) {
   std::cout << " Type contains ASubtype = TRUE " << std::endl;
   std::cout << " Value = " << value << std::endl;
}

Testing: 

// Template substution worked. OK. 
>> AfunctionTemplate<AStruct>(200)
 Type contains ASubtype = TRUE 
 Value = 200

// Template substution worked. OK. 
 >> AfunctionTemplate<AStructB>("PARAMETER")
  Type contains ASubtype = TRUE 
  Value = PARAMETER

// Template substution error. Failed. 
>> AfunctionTemplate(600)
ROOT_prompt_13:1:1: error: no matching function for call to 'AfunctionTemplate'
AfunctionTemplate(600)
^~~~~~~~~~~~~~~~~
ROOT_prompt_3:1:27: note: candidate template ignored: couldn't infer template argument 'T'
template<typename T> void AfunctionTemplate(typename T::ASubtype value) {

// Template substution error. Failed. 
>> AfunctionTemplate("Hello world")
ROOT_prompt_14:1:1: error: no matching function for call to 'AfunctionTemplate'
AfunctionTemplate("Hello world")
^~~~~~~~~~~~~~~~~
ROOT_prompt_3:1:27: note: candidate template ignored: couldn't infer template argument 'T'
template<typename T> void AfunctionTemplate(typename T::ASubtype value) {

By defining a two new overload functions which can match the type arguments, the substition failure of the first overload function with the type parameters int and const char* will no longer be an error as the compiler will select the next two overoads. 

// Note: This overload function is not a function template, just a free function
void AfunctionTemplate(int value) {
     std::cout << " Overload 2 => [INT] Type contains ASubtype = FALSE " << std::endl;
     std::cout << " Value = " << value << std::endl;
}

// Note: This overload function is not a function template, just a free function
void AfunctionTemplate(const char* value) {
     std::cout << " Overload 3 => [CONST CHAR*] Type contains ASubtype = FALSE " << std::endl;
     std::cout << " Value = " << value << std::endl;
}

>> AfunctionTemplate(400)
 Overload 2 => [INT] Type contains ASubtype = FALSE 
 Value = 400
>> 

// Implicit conversion 
>> AfunctionTemplate('x')
 Overload 2 => [INT] Type contains ASubtype = FALSE 
 Value = 120
>> 

>> AfunctionTemplate("Hello world SFINAE")
 Overload 3 => [CONST CHAR*] Type contains ASubtype = FALSE 
 Value = Hello world SFINAE

If there is no overload candidate matching the type argument, then the type substition failure will become an error: 

>> AfunctionTemplate(std::string("A std::string object"))

ROOT_prompt_31:1:1: error: no matching function for call to 'AfunctionTemplate'
AfunctionTemplate(std::string("A std::string object"))
^~~~~~~~~~~~~~~~~
ROOT_prompt_16:1:6: note: candidate function not viable: no known conversion from 'std::string' (aka
      'basic_string<char>') to 'int' for 1st argument
void AfunctionTemplate(int value) {
     ^
ROOT_prompt_20:1:6: note: candidate function not viable: no known conversion from 'std::string' (aka
      'basic_string<char>') to 'const char *' for 1st argument
void AfunctionTemplate(const char* value) {
     ^
ROOT_prompt_8:1:27: note: candidate template ignored: couldn't infer template argument 'T'
template<typename T> void AfunctionTemplate(typename T::ASubtype value) {
                          ^

The substition failure error can again be eliminated by defiing a new overload: 

template<typename T> void AfunctionTemplate(T value) {
     std::cout << " Overload 4 => [Match Any Type] contains ASubtype = FALSE " << std::endl;
}

// Deduce type T as std::string 
>> AfunctionTemplate(std::string("A std::string object"))
 Overload 4 => [Match Any Type] contains ASubtype = FALSE 
>> 

>> AfunctionTemplate<std::string>(std::string("A std::string object"))
 Overload 4 => [Match Any Type] contains ASubtype = FALSE 

>> AfunctionTemplate<std::string>("A std::string object")
 Overload 4 => [Match Any Type] contains ASubtype = FALSE 
>> 

// Deduce type std::vector<double>
> AfunctionTemplate(std::vector<double>{200.34, -100.6, 6.1546})
 Overload 4 => [Match Any Type] contains ASubtype = FALSE 

// Deduce type std::vector<double>
> AfunctionTemplate<std::vector<double>>({200.34, -100.6, 6.1546})
 Overload 4 => [Match Any Type] contains ASubtype = FALSE

Case 2 

struct AStruct{
   using ASubtype = int;
};

class AStructB{
public:   
   using ASubtype = const char*;
};

// Clever trick found at: http://cppedinburgh.uk/slides/201508-concepts-bottom-up-view.pdf
template<typename T, typename T::ASubtype* = nullptr> bool FunctionTest(T const& value) {
    return true;
}

Before defining the second overload function: 

>> AStruct a;
>> AStructB b;

>> FunctionTest(a)
(bool) true
>> FunctionTest(b)
(bool) true

>> FunctionTest(100)
ROOT_prompt_14:1:1: error: no matching function for call to 'FunctionTest'
FunctionTest(100)
^~~~~~~~~~~~
ROOT_prompt_9:1:60: note: candidate template ignored: substitution failure [with T = int]: type 'int'
      cannot be used prior to '::' because it has no members
template<typename T, typename T::ASubtype* = nullptr> bool FunctionTest(...

After defining the second overload function: 

bool FunctionTest(int const& value) {
    std::cout << " [2] Value = " << value << std::endl;
    return false;
}  
bool FunctionTest(const char* value) {
    std::cout << " [3] Value = " << value << std::endl;
    return false;
}  

>> FunctionTest(100)
 [2] Value = 100
(bool) false

>> FunctionTest("C++20")
 [3] Value = C++20
(bool) false
>>

1.19.2 Metafunction or type trait std::enable_if

The metafunction (aka type trait) std::enable_if is used for conditionally selectig a given overload function template from an overload set when the boolean argument is true or removing the function from the overload resolution when the boolean argument is false (SFINAE).

Use cases:

  • Select a given overload function when a condition is true.
  • Constrain template arguments by only allowing the templated function or class be used with types matching a predicate metafunction. When the predicate evaluates to false, a compile-time error happens.

Definition

The metafunction or type trait std::enable_if could be defined as:

  • Base template:

When the flag is false, the subtype type is not defined and the expression enable_if<false, T>::type is not valid, then compiler looks for the next overload function matching the template type arguments. 

template<bool Flag, class T = void>
struct enable_if{ };
  • Paratial specialization:

When the flag is true, the expression enable_if<true, T>::type is defined and returns the type T. 

template<class T = void>
struct enable_if<true>
{ 
   using type = T;
};

Example: The following code has a templated function classifyType with two overaloads, the first overload only works with integral types (int, char, long, …) and the second with float types (float, double and long double). If the function is used with non integral or float points type argument, a compilation error happens. 

#include <iostream>
#include <type_traits>

// First Overload classifyType
/** Note: when the predicate std::is_integral<T>::value is true, 
  * the expression: typename std::enable_if<std::is_integral<T>::value, void>::type
  * evaluates to void. When the predicate is false  this overload 
  * (implementation) is discarded. (SFINAE)
  */
template<class T> 
typename std::enable_if<std::is_integral<T>::value, void>::type
classifyType(T value) {
   std::cout << " Type = integral ; " << " 3 * value = " << 3 * value << std::endl;
}

// Second Overload of classifyType
template<class T> 
typename std::enable_if<std::is_floating_point<T>::value, void>::type
classifyType(T value) {
   std::cout << " Type = floating point ; " << " 25% x value = " << 0.25 * value << std::endl;
}

int main(){
  classifyType(20);
  classifyType(100L);
  classifyType('x');

  double z = 9.34;
  classifyType(z);
  float x = 3.1415; 
  classifyType(x);
  return 0;
}

Output: 

Type = integral ;  3 * value = 60
Type = integral ;  3 * value = 300
Type = integral ;  3 * value = 360
Type = floating point ;  25% x value = 2.335
Type = floating point ;  25% x value = 0.785375

The templated functions could also be written as: 

template<class T> 
auto classifyType(T value) 
   -> typename std::enable_if<std::is_integral<T>::value, void>::type
{
   std::cout << " Type = integral ; " << " 3 * value = " << 3 * value << std::endl;
}

template<class T> 
auto classifyType(T value) 
  -> typename std::enable_if<std::is_floating_point<T>::value, void>::type
{
   std::cout << " Type = floating point ; " << " 25% x value = " << 0.25 * value << std::endl;
}

The code could also be written in a another way as: 

#include <iostream>
#include <type_traits>

// First Overload of classifyType 
// => Only works with char, int, long, unsigned, ... 
template<typename T>    
void classifyType(T value, 
                  typename std::enable_if<std::is_integral<T>::value, void>::type* = nullptr) 
{
   std::cout << " Type = integral ; " << " 3 * value = " << 3 * value << std::endl;
}

// Second Overload of classifyType 
// => Only works with float, double or long double 
 template<typename T>    
 void classifyType(T value, 
                   typename std::enable_if<std::is_floating_point<T>::value, void>::type* = nullptr) 
 {
   std::cout << " Type = floating point ; " << " 25% x value = " << 0.25 * value << std::endl;
 }

The metafunction std::enable_if can be removed from the function signature by writing the code as: 

// First Overload classifyType
template<class T, typename std::enable_if<std::is_integral<T>::value, void>::type* = nullptr> 
void classifyType(T value) {
   std::cout << " Type = integral ; " << " 3 * value = " << 3 * value << std::endl;
}

// Second Overload of classifyType
template<class T, typename std::enable_if<std::is_floating_point<T>::value, void>::type* = nullptr>    
void classifyType(T value) {
   std::cout << " Type = floating point ; " << " 25% x value = " << 0.25 * value << std::endl;
}

1.19.3 Metafunction or type trait std::enalbe_if_t

The metafunction std::enable_if_t simplifies the usage of std::enable_if as it can be used as a dummy template argument instead of being used as return type.

Definition: 

template< bool B, class T = void >
using enable_if_t = typename enable_if<B,T>::type;

Example: 

#include <iostream>
#include <type_traits>

template< typename T, std::enable_if_t<std::is_integral<T>::value>* = nullptr>    
auto classifyType(T value) -> void 
{
   std::cout << " Type = integral ; " << " 3 * value = " << 3 * value << std::endl;
}

// Second Overload of classifyType
template< typename T, std::enable_if_t<std::is_floating_point<T>::value>* = nullptr>    
auto classifyType(T value) -> void 
{
   std::cout << " Type = floating point ; " << " 25% x value = " << 0.25 * value << std::endl;
}

int main(){
  classifyType(20);
  classifyType(100L);
  classifyType('x');

  double z = 9.34;
  classifyType(z);
  float x = 3.1415; 
  classifyType(x);
  return 0;
}

Output: 

Type = integral ;  3 * value = 60
Type = integral ;  3 * value = 300
Type = integral ;  3 * value = 360
Type = floating point ;  25% x value = 2.335
Type = floating point ;  25% x value = 0.785375

1.20 SFINAE - Type instrospection

1.20.1 Example 1 - Check whether type has default constructor

This example based on the book "Template the complete guide" shows a metafunction which can check whether a type has a default constructor, it means a constructor without any arguments. 

template<typename T> struct HasDefaultConstructor{
private:
   /** If the expressions decltype(X()) fails,
     *  then, the type X has no default constructor 
     *  and SFINAE happens and this function is 
     *  excluded from the overload resolution.
     */
     template<typename X, typename = decltype(X())>
     static auto testConstructor(void*) -> char;

    /** Fallback - template with dummy parameter */
    template<typename X>
    static auto testConstructor(...) -> long;       
public:
    /* If the class has default constructor,
     * the returned type of testConstructor<T>(nullptr)
     * is char, otherwise, it is long.
     */
     static constexpr bool value
     = std::is_same<decltype(testConstructor<T>(nullptr)), char>::value; 
};

Testing: 

>> HasDefaultConstructor<double>::value
(const bool) true

>> struct A{};
>> HasDefaultConstructor<A>::value
(const bool) true

>> struct X{ X() = delete; }
>> HasDefaultConstructor<X>::value
(const bool) false
>>

1.20.2 Example 2 - Check whether type has .end() member function

template<typename T> struct HasEndMemberFunction{
private:
     template<typename X, typename = decltype(std::declval<X>().end())>
     static auto check(void*) -> char;

     template<typename X>
     static auto check(...) -> long;        
public:
    static constexpr bool value
    = std::is_same<decltype(check<T>(nullptr)), char>::value; 
};

Testing: 

>> HasEndMemberFunction<int>()
(HasEndMemberFunction<int>) @0x2d63b70

>> HasEndMemberFunction<int>::value
(const bool) false

>> HasEndMemberFunction<double>::value
(const bool) false

>> HasEndMemberFunction<std::vector<double>>::value
(const bool) true

>> HasEndMemberFunction<std::deque<double>>::value
(const bool) true
>>

1.20.3 Example 3 - Check whether type is printable

This metafunction IsPrintable checks whether type is printable, in other words, whether it can be printed with (<<) operator: 

/**  @brief Checks whether type is printable, or supports the insertion operator (<<).  
 *   @details This metafunction tests
 *   whether type supports the operator (<<) or std::ostream&
 *   operator<<(std::ostream& os, const RHS& rhs)
 * 
 *   @tparam - Any type, int, char, class, std::string, std::vector ... 
 */
template<typename T>
struct IsPrintable{
    template<typename X, typename = decltype(std::cout << std::declval<X>())>
    static auto check(void*) -> char;

    template<typename X>
    static auto check(...) -> long;  

    static constexpr bool value =
      std::is_same<decltype(check<T>(nullptr)), char>::value; 
};

Main function: 

std::cout << std::boolalpha;
std::cout << "        IsPrintable<int> = " << IsPrintable<int>::value << "\n";
std::cout << "IsPrintable<std::string> = " << IsPrintable<std::string>::value << "\n";
std::cout << "  IsPrintable<SomeClass> = " << IsPrintable<SomeClass>::value << "\n";
std::cout << "      IsPrintable<Point> = " << IsPrintable<Point>::value << "\n";

Testing: 

$ clang++ sfinae_is_printable.cpp -o sfinae_is_printable.bin -std=c++1z -g -O0 -Wall && ./sfinae_is_printable.bin

        IsPrintable<int> = true
IsPrintable<std::string> = true
  IsPrintable<SomeClass> = false
      IsPrintable<Point> = true

1.20.4 Example 4 - Print type if it is printable (C++17 if constexpr)

Example: Print a type whether is printable or not. If the type is not printable notify that it cannot be printed. Note: printable here means that the operator (<<) or (std::ostream& <<) is defined for the type.

File:

Compiling: 

$ clang++ sfinae-print.cpp -o sfinae-print.bin -std=c++1z -g -O0 -Wall && ./sfinae-print.bin

Headers: 

#include <iostream>
#include <type_traits>

#include <string>
#include <vector>

Type trait or metafunction IsPrintable: 

template<typename T>
struct IsPrintable{
        template<typename X, typename = decltype(std::cout << std::declval<X>())>
        static auto check(void*) -> char;

        template<typename X> 
        static auto check(...) -> long;  

        static constexpr bool value =
            std::is_same<decltype(check<T>(nullptr)), char>::value; 
};
  • Function printIfPrintableA
    • Uses std::enable_if as function-return type
// Overload selected when type is printable 
template<typename T>
typename std::enable_if<IsPrintable<T>::value, void>::type
printIfPrintableA(const char* text, T const& value)
{
     std::cout << "[printIfPrintableA] "
               << "Value of object of type <" << text << "> = " << value << "\n";
}

// Overload selected when type is not printable. Or does not have the
// operator (<<) defined for it.
template<typename T>
typename std::enable_if<!IsPrintable<T>::value, void>::type                                                               
printIfPrintableA(const char* text, T const& value)
{
     std::cout << "[printIfPrintableA] "
               << "Value of object of type <" << text << "> = " << "[NOT PRINTABLE]" << "\n";
}
  • Function printIfPrintableB
    • Version B uses: Uses std::enable_if as trailing-return type (C++11)
template<typename T>
auto printIfPrintableB(const char* text, T const& value)
        -> typename std::enable_if<IsPrintable<T>::value, void>::type
{
        std::cout << "[printIfPrintableB] "
                  << "Value of object of type <"
                  << text << "> = " << value << "\n";
}

template<typename T>
auto printIfPrintableB(const char* text, T const& value)
        -> typename std::enable_if<!IsPrintable<T>::value, void>::type                                                                
{
        std::cout << "[printIfPrintableB] "
                  << "Value of object of type <" << text
                  << "> = " << "[NOT PRINTABLE]" << "\n";
}
  • Function printIfPrintableC
    • Version C: Uses std::enable_if as template type parameter.
template<typename T,
         typename std::enable_if<IsPrintable<T>::value, void>::type* = nullptr>
void printIfPrintableC(const char* text, T const& value)
{
     std::cout << "[printIfPrintableC] "
               << "Value of object of type <"
               << text << "> = " << value << "\n";
}

template<typename T,
         typename std::enable_if<!IsPrintable<T>::value, void>::type* = nullptr>
void printIfPrintableC(const char* text, T const& value)
{
      std::cout << "[printIfPrintableC] "
                << "Value of object of type <"
                << text << "> = " << "[NOT PRINTABLE]" << "\n";
}
  • Function printIfPrintableD
    • Version D: Uses C++17 if constexpr for eliminating SFINAE function overload boilerplate.
template<typename T>
void printIfPrintableD(const char* text, T const& value)
{

   std::cout << "[printIfPrintableD] "
             << "Value of object of type <" << text << "> = ";
   if constexpr (IsPrintable<T>::value)
       std::cout << value << "\n";
   else
      std::cout << "[NOT PRINTABLE]" << "\n";                    
}
  • Testing Classes:
// Not printable type 
struct SomeClass{   
};

// Printable class (defines operator <<)
struct Point{
   int x;
   int y;
   Point(int x, int y): x(x), y(y) { }
   friend auto operator<<(std::ostream& os, Point const& p) -> std::ostream& {
       return os << "Point{ " << p.x << " " << p.y << "} \n";
   }
};

Main Function

  • Experiment A:
std::cout << std::boolalpha;

std::cout << "\n======= EXPERIMENT A ======================\n"; 
printIfPrintableA("int", 100);
printIfPrintableA("double", 20.4);
printIfPrintableA("SomeClass", SomeClass());
printIfPrintableA("Point", Point{5, 6});

Output: 

======= EXPERIMENT A ======================
[printIfPrintableA] Value of object of type <int> = 100
[printIfPrintableA] Value of object of type <double> = 20.4
[printIfPrintableA] Value of object of type <SomeClass> = [NOT PRINTABLE]
[printIfPrintableA] Value of object of type <Point> = Point{ 5 6}
  • Experiment B:
std::cout << "\n======= EXPERIMENT B ======================\n";
printIfPrintableB("int", 100);
printIfPrintableB("double", 20.4);
printIfPrintableB("SomeClass", SomeClass());
printIfPrintableB("Point", Point{15, 20});

Output: 

======= EXPERIMENT B ======================
[printIfPrintableB] Value of object of type <int> = 100
[printIfPrintableB] Value of object of type <double> = 20.4
[printIfPrintableB] Value of object of type <SomeClass> = [NOT PRINTABLE]
[printIfPrintableB] Value of object of type <Point> = Point{ 15 20}
  • Experiment C:
std::cout << "\n======= EXPERIMENT C ======================\n";
printIfPrintableC("int", 100);
printIfPrintableC("double", 20.4);
printIfPrintableC("SomeClass", SomeClass());
printIfPrintableC("Point", Point{15, 20});

Output: 

======= EXPERIMENT C ======================
[printIfPrintableC] Value of object of type <int> = 100
[printIfPrintableC] Value of object of type <double> = 20.4
[printIfPrintableC] Value of object of type <SomeClass> = [NOT PRINTABLE]
[printIfPrintableC] Value of object of type <Point> = Point{ 15 20}
  • Experiment D:
std::cout << "\n======= EXPERIMENT D (C++17) ===============\n";
printIfPrintableD("int", 100);
printIfPrintableD("double", 20.4);
printIfPrintableD("SomeClass", SomeClass());
printIfPrintableD("Point", Point{15, 20});

Output: 

======= EXPERIMENT D (C++17) ===============
[printIfPrintableD] Value of object of type <int> = 100
[printIfPrintableD] Value of object of type <double> = 20.4
[printIfPrintableD] Value of object of type <SomeClass> = [NOT PRINTABLE]
[printIfPrintableD] Value of object of type <Point> = Point{ 15 20}

1.21 Compile-time computations with constexpr specifier

1.21.1 Overview

The constexpr specifier enables compile-time computations in a cleaner and more readable way than compile-time computations with recursive template metaprogramming.

Documentation:

C++ Standards:

  • C++11 => Introduced constexpr, however it only allows constexpr values and recursive constexpr functions without local variables and loops.
  • C++14 => Constexpr functions supports local variables and loops.

Benefits:

  • Replace compile-time computations with complicated recursive template metaprogramming.
  • Improve performance since the computations will no longer happen at runtime.
  • Eliminate hard-coded constants and macros.

Possible use cases:

  • Compute hash of string at compile-time
  • Compile-time obfuscation of strings with XOR
  • Compile-time computation of numerical constants such as Pi, Euler's number and so on.
  • Look-up table for embedded systems
  • Save embedded systems ROM (Read-Only memory) space.

Constexpr functions cannot contain:

  • Calls to functions evaluated at runtime such as std::sin, std::cos, … Constexpr functions can only call other constexpr functions.
  • Print statements such as std::cout <<<; std::puts(…)
  • goto statements
  • Exception handling, try-catch blocks
  • Lambda expressions
  • Heap-allocation (free-store allocation): new, delete, dynamic_cast

Papers

1.21.2 Basic Example - constexpr functions

Source:

Compilation: 

# Compile 
$ clang++ constexpr-function.cpp -o constexpr-function.bin -std=c++1z -g -O0 -Wall 
# Run 
$ ./constexpr-function.bin

Type alias: 

using BigInt = unsigned long;

Compile-time factorial computation using recusive template metaprogramming (old C++): 

// ====== Recursive template metaprogramming (Wikipedia) ====
// Code taken from Wikipedia:
//  + https://en.wikipedia.org/wiki/Template_metaprogramming
template <BigInt N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0> 
{
    enum { value = 1 };
};

C++11 Constexpr function for compile-time factorial computation (Version A): 

// Version A => 
constexpr BigInt factorialA(BigInt n){
   return n == 1 ? 1 : n * factorialA(n - 1);
}

C++14 Constexpr function for compile-time factorial computation (Version B): 

// Version B => Since C++14 (Not possible in C++11)
constexpr BigInt factorialB(BigInt n)
{
   BigInt acc = 1;
   for(size_t i = 1; i <= n; i++)
       acc = acc * i;
   return acc;
}

C++14 Constexpr function for compile-time factorial computation (Version C): 

// Version C => Since C++14 
constexpr auto factorialC(BigInt n) -> BigInt
{
   BigInt acc = 1;
   for(size_t i = 1; i <= n; i++)
           acc = acc * i;
   return acc;
}

Main function: 

std::cout << " ======== Old C++ ============= " << "\n";

std::cout << "Factorial(4) = " << Factorial<4>::value << "\n";
std::cout << "Factorial(5) = " << Factorial<5>::value << "\n";

static_assert(Factorial<4>::value == 24, "Error: result supposed to be equal to 24");
static_assert(Factorial<5>::value == 120, "");
static_assert(Factorial<6>::value == 720, "");

std::cout << " ======== New C++ >= C++11 ============= " << "\n";

constexpr BigInt factA4 = factorialA(4);
constexpr BigInt factA5 = factorialA(5);
constexpr BigInt factB4 = factorialB(4);
constexpr BigInt factB5 = factorialB(5);

std::cout << "factorialA(4) = " << factA4 << "\n";
std::cout << "factorialA(5) = " << factA5 << "\n";
std::cout << "factorialB(4) = " << factB4 << "\n";
std::cout << "factorialB(5) = " << factB5 << "\n";

// Note: factorial(6) will not is not computed at compile-time.
// Instead, it is be computed at runtime, and the compiler
// generates an ordinary function named factorialB 
std::cout << "factorialB(6) = " << factorialB(6) << "\n";

// Generates compilation error when false
static_assert(factorialA(4) == 24, "");
static_assert(factorialA(5) == 120, "");
static_assert(factorialB(4) == 24, "");
static_assert(factorialB(5) == 120, "");
static_assert(factorialC(6) == 720, "");
static_assert(factorialC(7) == 7 * 720, "");

Program Output: 

$ ./constexpr-function.bin
 ======== Old C++ ============= 
Factorial(4) = 24
Factorial(5) = 120
 ======== New C++ >= C++11 ============= 
factorialA(4) = 24
factorialA(5) = 120
factorialB(4) = 24
factorialB(5) = 120

Analysis:

  • Compile-time computation:

The function-call factorialB(5) is evaluated at compile-time to 120. 

constexpr BigInt factB5 = factorialB(5);

The following line is compiled as show in the comment: 

// --- Highlighted line 
std::cout << "factorialB(5) = " << factB5 << "\n";

// --- Compiled as: 
std::cout << "factorialB(5) = " << 120 << "\n";
  • The static_assert function is similar to the assert function, however static_assert operates on compile-time yielding a compilation error if the boolean argument (predicates) evaluates to false. If the predicate argument is true, a compilation error happens:

Predicate evalutes to true => Nothing happens. 

static_assert(factorialA(5) == 120, "");

By making the predicate false by changing 120 to 125, the following compile error happens: 

$ clang++ constexpr-function.cpp -o constexpr-function.bin -std=c++1z -g -O0 -Wall
constexpr-function.cpp:89:2: error: static_assert failed ""
        static_assert(factorialA(5) == 125, "");
        ^             ~~~~~~~~~~~~~~~~~~~~
1 error generated.
  • No everything is computed at compile-time, the following code block is computed at runtime. Constexpr function can also be computed at runtime if needed, in this case the compiler generates an ordinary function and its object-code.
// Note: factorial(6) will not is not computed at compile-time.
// Instead, it is be computed at runtime, and the compiler
// generates an ordinary function named factorialB 
std::cout << "factorialB(6) = " << factorialB(6) << "\n";

According to goldbot, this call generates the following object-code (x64 assembly): 

factorialB(unsigned long):
        push    rbp
        mov     rbp, rsp
        mov     QWORD PTR [rbp-24], rdi
        mov     QWORD PTR [rbp-8], 1
        mov     QWORD PTR [rbp-16], 1
.L3:
        mov     rax, QWORD PTR [rbp-16]
        cmp     rax, QWORD PTR [rbp-24]
        ja      .L2
        mov     rax, QWORD PTR [rbp-8]
        imul    rax, QWORD PTR [rbp-16]
        mov     QWORD PTR [rbp-8], rax
        add     QWORD PTR [rbp-16], 1
        jmp     .L3
        ret

1.22 C++20 Concepts [DRAFT]

1.22.1 Overview

Some major shortcoming of C++ generic programming are duck typing and the long error messages which makes harder to read and debug generic code. Those drawbacks stem from lack of language constructs to express generic programming, concepts, which are the type requirements that type arguments must satisfy in order to instantiate a template or function templates.

C++20 addresses those generic programming issues by providing concepts and type requirement as core language features which improves type checking, error messages and code readability.

Benefits summary:

  • Better code readability and documentation
    • Formal specification of concepts as code which improves readability and documentation of generic code. Without concepts language feature, concepts should be specified by comments and code examples which may be out of sync with the code.
  • Better and shorter error messages with more context information.
  • Better for IDEs and tooling
  • No SFINAE
    • Eliminates the need for cryptic SFINAE tricks which improves the code readability and maintainability.

Related documentation:

Headers files (CppReference):

  • <concepts> =>> Standard library concepts
  • <type_traits> =>> Type metafunctions for performing computation on types.

Papers:

1.22.2 Concepts as type predicates

In C++20, concepts core-language features are type predicates evaluated at compile-time which can be used for specifying and enforcing template type constraints.

The following expression declares the concept Shape which requires that type T must have the member functions T::area() which returns a double, and the member function T::name() which returns any type convertible to std::string. 

#include <concepts>
#include <string>

/** C++20 Concept Declaration */
template<typename T>
concept Shape = require(T obj) {

   // The type T must have a member function T::area() that returns double type.
   { obj.area() } -> std::same_as<double>;

   // The type T must have a member function T::name() that
   // returns a type convertible to std::string
   { obj.name() } -> std::convertible_to<std::string>;
};

This Shape concept can be used for specifying and constraining template arguments as it is shown in the following code. 

template<Shape T>
void show_informationA(const T& sh)
{
    std::cout << " Shape { name = " << sh.name()
              << " ; area = " << sh.area()  << "  } "
              << '\n';
}

template<typename T> requires Shape<T>
void show_informationB(const T& sh)
{
    std::cout << " Shape { name = " << sh.name()
              << " ; area = " << sh.area()  << "  } "
              << '\n';
}

In this piece of code, some types, that satisfy and does not satisfy the concept Shape, are defined. 

struct Circle
{
     /// ... ... //
     const char* name(){ return "circle"; }
     double      area(){ return pi * radius * radius;  }

     void nonCommonMethod1() {
        ....
     }
};

class Rectangle
{
public:
     // ... ... //
       const char* name(){ return "rectangle"; }
       double      area(){ return width * height;  }

       void nonCommonMethod2() {
          ....
       }
};

// Does not satisfy the concept as this type lacks the
// member function area()
struct Blob
{
     /// ... ... //
     const char* name(){ return "blob"; }
     void nonCommonMethod1() {
        ....
     }
};

This next code shows that, that attempting to instantiate the previous templated functions with types not satisfying the Shape concept results in compile-time error. 

void main()
{
   // Works => Code compiles
   Rectangle r1;
   show_informationA(r1);
   show_informationB(r1);

   // Works => Code compiles
   static_assert( Shape<Rectangle> );
   static_assert( Shape<decltype(r1)> );

   // Works => Code compiles
   Circle c1;
   show_informationA(c1);
   show_informationB(c1);
   show_informationB<Circle>(c1);

   // Works => Code compiles
   static_assert( Shape<Circle> );
   static_assert( Shape<decltype(c1)> )

   // Compile-time ERROR!!
   static_assert( Shape<int> );
   static_assert( Shape<std::string> );
   static_assert( Shape<Blob> );
}

1.22.3 Concepts from type predicates

Simple concepts can be defined from custom type predicates or type predicates from the header. The concept IntegralA and IntegralB, which are built using the type predicate std::is_integral from the header (<type_traits), accept any integer type such as short, int, uint8_t, long and so on. 

#include <type_traits> 
/* Concept: IntegralA  
 * std::is_integral_v<T>::value => Evaluates to bool 
 */
template<typename T>
concept IntegralA = std::is_integral_v<T>;

/* Concept: IntegralB - 
 *   std::is_integral<T>::value => Evaluates to bool at compile-time 
 */
template<typename T>
concept IntegralB = std::is_integral<T>::value;

// ------------ Usage Example -------------//

template<typename T> requires IntegralA<T>
auto my_function_A1(T x, T y) -> T
{
   return 10 + x * y * 20;
}

template<IntegralA T>
auto my_function_A2(T x, T y) -> T
{
   return 10 + x * y * 20;
}

template<IntegralB T>
auto my_function_B1(T x, T y) -> T
{
   return 10 + x * y * 20;
}

template<class T> requires Integral<B>
auto my_function_B1(T x, T y) -> T
{
   return 10 + x * y * 20;
}

// Compiles   
static_assert(  IntegralA<int> );
static_assert(  IntegralA<uint8_t> );
static_assert(  IntegralB<long> );

// Error: DO NOT COMPILE!!
static_assert(  IntegralA<std::string> );
static_assert(  IntegralB<float> );

Concepts can also be built from other pre-existing concepts:

  • The concept CompositeConcept is comprised of a conjuction (and operation) of 3 concepts. A type that satisfy the CompositeConcept concept, must fullfil all requirements of conjuction concepts, namely, Incrementable, Decrementable and std::is_base_v.
template<class X>
concept Incrementable = requires(X obj)
{
   { obj++ } -> std::same_as<X>;
};

template<class X>
concept Decrementeable = requires(X obj)
{
   { obj-- } -> std::same_as<X>;
};

template<typename T>
concept CompositeConcept = 
           std::is_base_v<T, BaseClass> 
       &&  Incrementable<T>
       &&  Decrementeable<T>
       ;

Usage of CompositeConcept: 

template<CompositeConcept T>
void some_functionA(T&& x)
{
  // ... ... ///
}

template<typename T> requires CompositeConcept<T>
void some_functionB(T&& x)
{
  // ... ... ///
}

template<class T> 
     requires CompositeConcept<T>
void some_functionC(T&& x)
{
  // ... ... ///
}

Templates can also constrain arguments using conjuction (AND) of multiple concepts: 

/** Function Declaration */
template<typename T> 
 requires  std::is_base_v<T, BaseClass> 
       &&  Incrementable<T>
       &&  Decrementeable<T>
void some_functionC(T&& x);

/** Function Definition */
template<typename T> 
 requires  std::is_base_v<T, BaseClass> 
       &&  Incrementable<T>
       &&  Decrementeable<T>
void some_functionC(T&& x)
{
  // ... ... ///
}

1.22.4 Compiling code with C++20 concepts

Sample code containing concepts and template type constraints (requires):

  • File: concepts1.cpp
#include <iostream>
#include <string> 
#include <sstream>
#include <concepts>
 // #include <utility>

template<typename T>
concept CallableObject = requires(T obj) {
   { obj() } -> std::same_as<void>;

};

/* Templated function wihout concepts */
template<typename T>
void dotimes_a(int n, T&& func)
{
  for(int i = 0; i < n; i++) { func(); }
}

/** Templated function with concepts */
template<CallableObject T>
void dotimes_b(int n, T&& func)
{
  for(int i = 0; i < n; i++) { func(); }
}

/** Templated function with type constraint */
template<typename T> requires CallableObject<T>
void dotimes_c(int n, T&& func)
{
  for(int i = 0; i < n; i++) { func(); }
}


/** Matches any type for which 
  * the friend function (<<) is defined. 
  */
template<typename T> 
concept Printable = requires(T x){
  { std::cout << x };                            
};

template<typename T> requires Printable<T>
std::string to_string(T const& obj)
{
   std::stringstream ss;
   ss << obj;
   return ss.str();
}

struct LinFun{
  double a; 
  double b; 

  double operator()(double x) const { return a * x + b; } 

  friend std::ostream& operator<<(std::ostream& os, LinFun const& obj)
  {
     return os << " Linfun => a = " << obj.a << " ; b = " << obj.b ;
  }
};

int main(){

  std::puts(" ======== [INFO] Started Ok. ===================");

  // Causes compile-time error, when concept is not satisfied 
  // static_assert( Printable<decltype(std::cout)>   ); => STATIC ASSERTION FAILURE 
  static_assert( Printable<int>         );
  static_assert( Printable<std::string> );
  static_assert( Printable<double>      );
  static_assert( Printable<LinFun>      );


  // Evaluated at compile-time: 
  if constexpr ( Printable<LinFun> )
  {
     std::cout << " Type LinFun models the concept Printable<T> \n";
     auto q = LinFun{4, 5};
     std::string s = to_string( q );
     s = " Function: "  + s + " => functor(5.64) =  " +  std::to_string(q(5.64));
     std::cout << " s => " << s << '\n';                                                                         

  } 

  std::cout << " Object = " << to_string(LinFun{4, 5}) << "\n\n";

  int n = 5;

  int a = 0; 
  auto lamb1 = [&a](){ std::cout << " [A] i = " << a++ << "\n"; };
  dotimes_a(n, lamb1);
  static_assert( CallableObject<decltype(lamb1)> );

  // static_assert( CallableObject<int> );

  int b = 0; 
  dotimes_b(n, [&b](){ 
     std::cout << " [B] i = " << b++ << "\n";   
  });

  int c = 0; 

  dotimes_b(n, [&c](){ 
     std::cout << " [C] i = " << c++ << "\n";   
  });

  return 0;
}

Current compilers information: 

 # GNU GCC (G++) Version
 $ >> g++ --version
 g++ (GCC) 10.1.1 20200507 (Red Hat 10.1.1-1)
 Copyright (C) 2020 Free Software Foundation, Inc.
 This is free software; see the source for copying conditions.  There is NO
 warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

# Clang++ LLVM Version 
 $ >> clang --version
 clang version 10.0.0 (Fedora 10.0.0-2.fc32)
 Target: x86_64-unknown-linux-gnu
 Thread model: posix
 InstalledDir: /usr/bin

Building: 

# Built on Linux Fedora 32 (x86-64 64 bits)

# Building with GCC (GNU C/C++ Compiler)
$ >> g++ concepts-basic.cpp -o out.bin -std=c++2a -ggdb -Wall -Wextra 

# Building with Clang++ LLVM compiler 
$ >> clang++ concepts-basic.cpp -o out2.bin -std=c++2a -ggdb -Wall -Wextra

Running: 

$ >> ./out.bin 
======== [INFO] Started Ok. ===================
Type LinFun models the concept Printable<T> 
s =>  Function:  Linfun => a = 4 ; b = 5 => functor(5.64) =  27.560000
Object =  Linfun => a = 4 ; b = 5

[A] i = 0
[A] i = 1
[A] i = 2
[A] i = 3
[A] i = 4
[B] i = 0
[B] i = 1
[B] i = 2
[B] i = 3
[B] i = 4
[C] i = 0
[C] i = 1
[C] i = 2
[C] i = 3
[C] i = 4

1.23 References and Bookmarks

1.23.2 Standard Library Facilities for Metaprogramming

  • <type_traits> Type traits (aka metafunctions) - utilities for querying, transforming and manipulating types at compile-time.
  • iterator library
  • iterator tags - std::input_iterator_tag, std::output_iterator_tag, std::forward_iterator_tag
  • std::decay - Remove cv-qualifiers, turns int& into int, int&& int int, char* into char, int[2] into int*, and so on.
  • std::iterator
  • std::end, std::cend
  • std::iterator_traits
  • constexpr (C++11) - Compile-time computations.
  • std::enable_if - Allows to restrict a function overload, alternative implementation of a function with different signature, based on a type predicate. For instance, it can be used to define a function overload which is selected only when the type predicate std::is_integral is evaluates to true (the type is any of int, long, short and so on.). Another overload, which only applies to float point types, can be defined by using the type predicate std::is_floating_point.
    • Summary: Allows to define function overloads which matches a given type predicate metafunction (type trait).
  • std::conditional
  • parameter_pack -> Variadic template arguments.
  • sizeof… operator -> Get size of parameter pack (arguments of variadic template.)
  • fold expression (C++17) - Allows unpacking template variadic paremeters in a easier way without complicated recursion boilerplate.
  • if constexpr (C++17)

1.23.3 Videos

1.23.4 Papers and technical documents

Papers and technical documents about Generic Programming and Template Metaprogramming

Created: 2021-06-04 Fri 15:07

Validate