Template Metaprogramming

Motivating example

#include<vector>
#include<deque>
#include<set>
#include<string>
#include<algorithm>

using namespace std;
int main(){
    vector<string> names{"Anna","Ethan","Nikhil","Avery"};
    auto anna_iter = find(name.begin(),name.end(),"Anna");
    auto avery_iter = find(name.begin(),name.end(),"Avery");
    
    return std::distance(anna_iter,avery_iter);
}

how do you implement your own distance function?

template<typename It>
size_t my_distance(It first, It last){
	return last-first;
}

the above code is O(1), which is efficient.
but the above implementation only works for random access iterator

another optimization!

template<typename It>
size_t my_distance(It first, It last){
	size_t result = 0;
    while(first!=last){
        ++first;
        ++result;
    }
    return result;
}

but the second way is O(N), for any kind of iterators, which is unexpected

How does STL achieve this?

You have to extract type information from iterator of what it is.
need to determine if it is random access iterator
run the piece of code based on the type of iterator:

Computations on Types

Comparision of values vs. type computations : A Preview

Meta-functions

template types

use them for template classes

template values

meta-function

abstractly:

It is a function that operates on some types/values(“parameters”)
and outputs some types/values(“return values”)

concretely:

It is a struct that has public member types/fields(output) which depend on what the template types/values(input) are instantiated with.

a simple example:

//input type, output value
template<typename T, typename U>
struct is_same{
    static const bool value = ????;
};

//input value, output value
template<int V, int W>
struct is_same{
    static const bool value = (V==W);
};

Template Deduction

Template Rules

Template Specialization: you can have a “generic template”, as well as “specialized” templates for particular types

Fully specialize:

why specialization?: using a bit array to store booleans is much more efficient.

partially specialize:

Some examples using Template Deduction

let’s build up a collection of predicate meta-functions

why does the second one return true?

the compiler tries to first match the specialized template
the second one got matched, so return true

kind of interesting, you can figure out the type info, because of template deduction rules

of course, same technique can be used to return a type

Actually it is a “hack”, because we are using the compiler’s template matching rules to implement an if/else statement for types(we can’t directly compare them)

Let finish our myDistance implement:

using category = typename std::iterator_traits<It>::iterator_category;
if (std::is_same<category, std::random_access_iterator_tag>::value){
    return last - first;
}else{
    size_t result = 0;
    while(first!=last){
        ++first;
        ++result;
    }
    return result;
}

need to remove the offending code when the if statement knows that part won’t be run;
pre-C++17: std::enable_if
C++17: if constexpr

using category = typename std::iterator_traits<It>::iterator_category;
if constexpr (std::is_same<category, std::random_access_iterator_tag>::value){
    return last - first;
}//else ...

what is constexpr?

you can calculate this expression at compile time.(stronger form of const)

what is if constexpr?

calculate boolean at compile-time , Replace the entire if/else with the code that will be actually be run