In this chapter, we’ll have a taste of template metaprogramming. Template metaprogramming collectively refers to various C++ template-based techniques that perform computations and validations at compile time as opposed to run time.
We’ll use the example of the std::distance() function template which we
encountered in the last chapter. Recall that the function calculates the number
of hops between two iterators. We explained that std::distance() will use two
different algorithms depending on the category of iterator – a simple O(1)
computation for random access iterators or an O(N) walk for forward iterators.
Now we’ll explore various techniques for switching between the algorithms at
compile time.
We’ll implement our own MyDistance() function template in multiple stages.
We’ll start with a template metaprogramming technique called tag dispatching,
which has been around even before the start of modern C++, marked by C++11. Then
we’ll explore a technique known as SFINAE, which stands for Substitution Failure
Is Not An Error, using the std::enable_if facility introduced in C++11.
We’ll then switch over to using C++17’s if constexpr statement, which will
make our MyDistance() implementation much more succinct and readable. Finally,
we’ll implement MyDistance() using C++20’s concepts, allowing us to explicitly
state the type requirements of each algorithm.
Let’s start by considering the following naive implementation of MyDistance():
template <typename I>
size_t MyDistance(I b, I e) {
return e - b;
}
int main() {
// Simply assuming random access iterator
vector v { 100, 101, 102, 103, 104 }; // OK
// forward_list v { 100, 101, 102, 103, 104 }; // compiler error
// int v[5] { 100, 101, 102, 103, 104 }; // also OK
auto b = ranges::begin(v);
auto e = ranges::end(v);
cout << "Number of elements: " << MyDistance(b, e) << '\n';
}
First off, note that instead of v.begin() and v.end(), we use
ranges::begin(v) and ranges::end(v). The ranges namespace contains C++20’s
new ranges library. A range is a generalization of a sequence of elements in STL
denoted by a half-open interval, [begin, end). We’ll revisit ranges later. For
now, we’re using the ranges::begin() and ranges::end() function templates to
uniformly handle STL containers and C arrays. If v is an STL container,
ranges::begin(v) and ranges::end(v) are equivalent to v.begin() and
v.end(), respectively. In the case above with int v[5], where v is a C
array, ranges::begin(v) and ranges::end(v) are equivalent to &v[0] and
v + 5, respectively.
This implementation of MyDistance() simply assumes that the type I
implements an operator-() overload. That assumption is true for vector’s
random access iterator and the raw pointers to the elements in the C array, but
it is not true for the less capable forward_list iterator. As such, the code
fails to compile if we use a forward_list. We need to employ a different
algorithm for less capable iterators that do not implement operator-().
Recall the hierarchy of iterator categories that we discussed a couple of chapters ago. C++ formalizes these relationships as an inheritance hierarchy of empty structs known as iterator tags:
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};
struct contiguous_iterator_tag : public random_access_iterator_tag {};
Each STL iterator contains an iterator_category type alias that refers to one
of these iterator tags. For example, the definition of forward_list::iterator
contains a type alias that looks something like this:
using iterator_category = forward_iterator_tag;
These iterator tags allow us to choose between two algorithms using a technique known as tag dispatching:
template <typename I>
size_t __doMyDistance(I b, I e, random_access_iterator_tag) {
return e - b;
}
template <typename I>
size_t __doMyDistance(I b, I e, forward_iterator_tag) {
size_t n = 0;
while (b != e) {
++n;
++b;
}
return n;
}
template <typename I>
size_t MyDistance(I b, I e) {
return __doMyDistance(b, e, typename I::iterator_category{});
// return __doMyDistance(b, e,
// typename iterator_traits<I>::iterator_category{});
}
The MyDistance() function template now delegates to one of the two
__doMyDistance() helper function templates, which take an additional unused
iterator tag parameter. MyDistance() constructs an instance of the iterator’s
tag and passes it to the helper function. The compiler will choose the best
overload by comparing possible derived-to-base-class conversions. For example, a
contiguous_iterator_tag can be upcasted to both random_access_iterator_tag
and forward_iterator_tag, but it’s closer to the former. A
bidirectional_iterator_tag can only reach forward_iterator_tag. The decision
as to which helper function to invoke is therefore made entirely at compile
time.
Note that we could’ve written code that chooses which helper function to invoke based on the iterator’s type at run time. The point of the tag dispatching technique is to make that decision entirely at compile time instead.
Our implementation now works with both vector and forward_list. However, it now
fails to compile if we use a C array because the raw pointer is not a class and
therefore it cannot contain the necessary iterator_category nested type alias.
We can solve this problem by retrieving the iterator_category through the
std::iterator_traits<I> wrapper class template that looks something like this:
template <typename T>
struct iterator_traits {
...
using iterator_category = typename T::iterator_category;
...
};
// Specialization for raw pointer
template <typename T>
struct iterator_traits<T*> {
...
using iterator_category = contiguous_iterator_tag;
...
};
For any STL iterator class I, iterator_traits<I>::iterator_category resolves
to I::iterator_category. For a raw pointer type T*, STL provides a
specialization, iterator_traits<T*>, whose iterator_category type alias
resolves to random_access_iterator_tag.
We can eliminate the tag dipatching layer in our implementation of
MyDistance() by using another template metaprogramming technique called
SFINAE. C++11 introduced the std::enable_if facility that makes it easier to
use the SFINAE technique. Let’s start by studying a couple of STL helper
facilities first.
std::enable_ifenable_if is a class template that takes a value parameter, bool B, and a
type parameter, T:
template <bool B, typename T>
struct enable_if {};
// Specialization for `true` value parameter
template <typename T>
struct enable_if<true, T> { using type = T; };
The enable_if class template is specialized for the case where the boolean
value parameter is true. In that case, the struct is defined with a nested type
alias type that resolves to the type parameter T. Consider the following two
examples below:
enable_if<true, size_t>::type x = 5; // Same as: size_t x = 5;
enable_if<false, size_t>::type y = 5; // Compiler error
The declaration of x compiles just fine because the enable_if struct defines
the nested type alias type to be size_t. On the other hand, the declaration
of y fails to compile because the value parameter false chooses the
definition of the struct that does not contain the nested type alias type.
std::is_same_vNext, let’s consider the STL class template is_same. It is defined as
something like this:
template <typename T, typename U>
struct is_same {
static constexpr bool value = false;
};
// Specialization for T == U
template <typename T>
struct is_same<T, T> {
static constexpr bool value = true;
};
For any two types T and U, where T and U are not the same, the is_same
struct is defined to have a data member value that is false. The template is
also specialized for the case where T and U are the same, in which case
value is true.
The data member is defined as static and constexpr. A static data member is
a per-class member, rather than a per-instance member. We refer to a static data
member m of a class C using the syntax C::m. Marking the member as
constexpr will tells the compiler that it can be used in expressions that are
evaluated at compile time.
For example, the first static assertion below compiles but the second one does not:
static_assert(
is_same<random_access_iterator_tag,
iterator_traits<vector<int>::iterator>::iterator_category
>::value); // OK
static_assert(
is_same<random_access_iterator_tag,
iterator_traits<forward_list<int>::iterator>::iterator_category
>::value); // Compiler error
For convenience, STL also defines std::is_same_v:
template <typename T, typename U>
constexpr bool is_same_v = is_same<T, U>::value;
is_same_v<T,U> is a variable template that refers to the family of value
static members of the is_same<T,U> struct for various types T and U. We
can rewrite the valid assertion from above using is_same_v:
static_assert(
is_same_v<random_access_iterator_tag,
iterator_traits<vector<int>::iterator>::iterator_category>);
enable_ifWe are now ready to implement two overloads of MyDistance() using the SFINAE
technique, one for random_access_iterator_tag and one for
forward_iterator_tag:
template <typename I>
std::enable_if<is_same_v<random_access_iterator_tag,
typename iterator_traits<I>::iterator_category>, size_t>::type
MyDistance(I b, I e) {
return e - b;
}
template <typename I>
std::enable_if<is_same_v<forward_iterator_tag,
typename iterator_traits<I>::iterator_category>, size_t>::type
MyDistance(I b, I e) {
size_t n = 0;
while (b != e) {
++n;
++b;
}
return n;
}
int main() {
// SFINAE
vector v { 100, 101, 102, 103, 104 }; // OK, random_access_iterator_tag
// forward_list v { 100, 101, 102, 103, 104 }; // OK, forward_iterator_tag
// int v[5] { 100, 101, 102, 103, 104 }; // OK, random_access_iterator_tag
// list v { 100, 101, 102, 103, 104 }; // Error: bidirectional_iterator_tag
auto b = ranges::begin(v);
auto e = ranges::end(v);
cout << "Number of elements: " << MyDistance(b, e) << '\n';
}
Consider the return type of the first overload of MyDistance(). We are
wrapping the size_t return type in an enable_if check against the iterator
type parameter I. We check if I is a random access iterator using
is_same_v. If so, accessing enable_if::type is valid and resolves to
size_t. If not, there is no enable_if::type so the whole return type
expression is ill-formed.
Let’s walk through what happens when we call MyDistance() with vector
iterators. The compiler will determine which of the MyDistance() candidates
are viable. For the first overload, the return type resolves to size_t because
vector’s iterator is a random access iterator. For the second one, however, the
return type is ill-formed because vector’s iterator is not a forward iterator.
(Although it derives from forward iterator, is_same_v is performing an exact
match.)
The crux of the SFINAE technique is that the ill-formed second overload does not lead to a compiler error. Rather, the compiler will simply remove the ill-formed overload from the set of viable options. This is why the technique is called Substitution Failure Is Not An Error.
For simplicity, we opted for an exact match on the iterator tag instead of
testing for the inheritance relationship as we did in the tag dispatching case.
We could have used std::is_base_of_v to follow the semantics of the tag
dispatching version. In that case, the second overload would’ve had to test if
the given tag derives from forward_iterator_tag but not from
random_access_iterator_tag. Due to our choice here, using list iterators
wouldn’t match either of the two overloads and result in a compiler error.
You may be wondering why the iterator_traits<I>::iterator_category of vector
iterators and raw pointers is random_accesss_iterator_tag instead of
contiguous_iterator_tag. Although they are both contiguous iterators
conceptually, because contiguous_iterator_tag was only introduced in C++20,
their iterator tags were not changed for the sake of backwards compatibility.
if constexpr statementC++17 introduced the if constexpr statement, which allows compile time
branching based on a constexpr expression. We can leverage this feature to
rewrite MyDistance() succinctly as a single function template:
template <typename I>
size_t MyDistance(I b, I e) {
if constexpr (is_base_of_v<random_access_iterator_tag,
typename iterator_traits<I>::iterator_category>) {
return e - b;
} else {
size_t n = 0;
while (b != e) {
++n;
++b;
}
return n;
}
}
The if-else structure allows us to go back to the semantics of testing the
inheritance hierarchy without complicating the logic. The is_base_of_v
variable template will evaluate to true if the iteratory category of I is
the same as or derives from random_access_iterator_tag. In that case, the O(1)
implementation is selected. Otherwise, we fall through to the else block and
select the O(N) implementation. The compiler will only generate one branch of
the code. This implementation of MyDistance() is succinct and readable and
works for all containers plus C arrays.
Consider, however, the following nonsensical call to MyDistance() using two
std::string literals.
cout << MyDistance("AAA"s, "BBB"s) << '\n';
We get a compilation error because of the ill-formed expression
iterator_traits<string>::iterator_category. It would be nicer if the compiler
could tell us explicitly that the arguments we are passing are not iterators. In
other words, we would like a way to explicitly declare that the template type
parameter I should be an iterator instead of indirectly enforcing that
requirement by looking up the type’s iterator category tag.
C++20 introduced concepts, which allows us to explicitly state type requirements. A concept is a compile time predicate that evaluates to true if a given set of types satisfy the constraints laid out by the concept.
STL offers many helpful concepts, including concepts defined for each of the
iterator categories. We can use the forward_iterator concept to constrain the
type parameter I for MyDistance(). All we have to do is add a requires
clause:
template <typename I>
requires forward_iterator<I>
size_t MyDistance(I b, I e) {
if constexpr (is_base_of_v<random_access_iterator_tag,
typename iterator_traits<I>::iterator_category>) {
return e - b;
} else {
size_t n = 0;
while (b != e) {
++n;
++b;
}
return n;
}
}
This is the same constexpr-based implementation of MyDistance() that we saw
in the previous section, except that the compiler will now enforce that the type
I satisfies the constraints laid out by the forward_iterator concept. We
will show how to implement your own concept shortly, but for now, we can imagine
that the forward_iterator concept checks that the type I can be
dereferenced, incremented, and has an iterator tag that derives from
forward_iterator_tag.
Instead of using a requires clause to specify the constraining concept, C++
allows you to replace the keyword typename with the constraining concept. We
can simplify our MyDistance() definition as follows:
template <forward_iterator I>
size_t MyDistance(I b, I e) { ... }
The problematic MyDistance("AAA"s, "BBB"s) invocation will now fail to compile
with a much more descriptive error message. The compiler tells you that there
was no matching function for the call MyDistance(string, string) because the
MyDistance() function template requires forward iterators.
autoA concept can also precede an auto placeholder type specifier. For example, we can specify the random_access_iterator concept to constrain the iterators b and e as follows:
...
random_access_iterator auto b = ranges::begin(v);
random_access_iterator auto e = ranges::end(v);
cout << "Number of elements: " << MyDistance(b, e) << '\n';
This code snippet would compile if v is a vector or array, but would fail to
compile if v is a list. Using concepts to constrain the type of a variable
declared with auto can improve readability and type-safety.
As an example of how to define our own concept, here is a simplified version of
std::bidirectional_iterator:
template <typename I>
concept MyBidirectionalIterator =
forward_iterator<I> &&
derived_from<typename iterator_traits<I>::iterator_category,
bidirectional_iterator_tag> &&
requires (I i) {
{ --i } -> std::same_as<I&>;
{ i-- } -> std::same_as<I>;
};
Our MyBidirectionalIterator concept is defined as a conjuction of three
constraints. We first enforce the existing forward_iterator concept on the
given type I. We then need to simply address the additional functionality of
bidirectional iterators. The second constraint uses the std::derived_from
concept to check that I’s iterator tag derives from
bidirectional_iterator_tag.
Third, we check that the iterator can be decremented. We use a requires
expression, which allows us to list a sequence of expressions that must be valid
and impose type requirements on them. For example, the following requires
expression enforces that the type I implements both prefix and postix
decrement:
requires (I i) {
--i;
i--;
};
Our concept additionally enforces that these expressions evalulate to I& and
I, respectively, using the std::same_as concept:
requires (I i) {
{ --i } -> std::same_as<I&>;
{ i-- } -> std::same_as<I>;
};
We can constrain the iterators b and e using our MyBidirectionalIterator
concept to make the code compiler for vector, array, and list (but not
forward_list):
MyBidirectionalIterator auto b = ranges::begin(v);
MyBidirectionalIterator auto e = ranges::end(v);
cout << "Number of elements: " << MyDistance(b, e) << '\n';
Last updated: 2025-11-05