In the first part of this mini-series we looked at the different types of template parameter and the syntax involved in using them. In this part we’re going to look at two idioms that involve use of templates in C++, both of which have acronyms: CRTP and SFINAE.
Curious Recurring Template Pattern
From the earliest days of the availability of templates for C++ (around the mid-nineties, shortly before the publication of the C++98 standard), CRTP has been so named and known about. The pattern it describes is not difficult to comprehend – a base class has a template type parameter which is the type of a (single) derived class. What does take some explaining is that this has a use case in fully describing compile-time polymorphism (as opposed to run-time polymorphism which uses virtual functions, or compile-time “duck-typing” which is the usual behavior of template type parameters).
Compile-time polymorphism involves specifying a (public) interface in the base class, which calls member functions (and/or accesses data members) in the derived class. Let’s look at this in action, here is a simplified interface (base) class called Container which has template type parameter, here called Derived:
template<typename Derived>
class Container {
Derived& actual() {
return *static_cast<Derived*>(this);
}
const Derived& actual() const {
return *static_cast<const Derived*>(this);
}
public:
decltype(auto) front() { ... }
decltype(auto) size() { ... }
decltype(auto) operator[](size_t i) { ... }
void print(ostream& os = cout) { ... }
};
Since Container does no have any data members it is likely (through the EBO – Empty Base Optimization) to have the same address as any class which inherits from it. The (private) member function actual() provides access to the derived class to allow implementation of the interface members (discussed later); the second overload is provided for const member interface functions (if any). Importantly, a static_cast always safely succeeds in this context, in contrast to a dynamic_cast for a (run-time) polymorphic class hierarchy.
Now let’s jump ahead and look at the class which is going to derive from Container, as well as be its Derived parameter. This has a composed (private) member of type std::forward_list, as well as public begin() and end() member functions which forward onto the data member’s functions with the same names. A constructor taking a std::initializer_list is also provided:
template<typename T>
class indexed_list : public Container<indexed_list<T>> {
forward_list<T> l;
public:
indexed_list(const initializer_list<T>& init_list) {
l.assign(init_list);
}
decltype(auto) begin() {
return l.begin();
}
decltype(auto) end() {
return l.end();
}
};
So, taking a look at these two classes, the way to get them to play happily with each other is to fully define the base class members front(), size(), operator[]() and print() in terms solely of begin(), end() and functions which work with forward-iterators (the type used for std::forward_list. Below is a partially-complete program which demonstrates this (“partially” because it is not const-correct – adding cbegin() and cend() const-members to derived class indexed_list would allow this defect to be solved).
// crtp_container.cpp : interface class with derived class using CRTP
#include <forward_list>
#include <iterator>
#include <initializer_list>
#include <iostream>
using namespace std;
template<typename Derived>
class Container {
Derived& actual() {
return *static_cast<Derived*>(this);
}
const Derived& actual() const {
return *static_cast<const Derived*>(this);
}
public:
decltype(auto) front() {
return *actual().begin();
}
decltype(auto) size() {
return distance(actual().begin(), actual().end());
}
decltype(auto) operator[](size_t i) {
return *next(actual().begin(), i);
}
void print(ostream& os = cout) {
os << "{ ";
for (auto sep = ""; const auto& elem : actual()) {
os << sep << elem;
sep = ", ";
}
os << " }\n";
}
};
template<typename T>
class indexed_list : public Container<indexed_list<T>> {
forward_list<T> l;
public:
indexed_list(const initializer_list<T>& init_list) {
l.assign(init_list);
}
decltype(auto) begin() {
return l.begin();
}
decltype(auto) end() {
return l.end();
}
};
int main() {
indexed_list il{ 1, 2, 3, 4, 5 };
cout << "front(): " << il.front()
<< "\nsize(): " << il.size()
<< "\n[3]: " << il[3] << '\n';
il[4] = 99;
il.print();
}
Note the use of decltype(auto) to preserve the const-ness and reference-ness of the member functions return values. As an exercise I recommend adding functions cbegin() and cend() to indexed_list as well as making as many of the Container member functions const as possible, and providing const and non-const operator[]. The output from running this program is:
front(): 1
size(): 5
[3]: 4
{ 1, 2, 3, 4, 99 }
Note that it is never possible to do away with the “helper” derived class entirely and use a construct such as Container<std::list<int>>. The method of calling derived class members used here is stable and safe, however.
Substitution Failure Is Not An Error
Pronunciation issues aside, SFINAE is widely used to choose between multiple candidates for instantiation which may be present; those which have been rejected are said to have been “SFINAE’d out”. This is able to work because the compiler does not report an error (in some cases) when an attempt to instantiate a template for a particular type fails. This allows some compile-time choices to be made.
The following program creates a template HasValueTypeT<T> whose value data member is true if T::value_type exists (such as for all of the Standard Containers) or false if it does not (such as for built-in types). Its results can be used in static assertions as they are defined at compile-time:
// sfinae_traits.cpp : create a simple but general traits template utilizing SFINAE
#include <type_traits>
#include <vector>
#include <map>
using namespace std;
template<typename...>
using VoidT = void;
template<typename, typename = VoidT<>>
struct HasValueTypeT : false_type {
};
template<typename T>
struct HasValueTypeT<T, VoidT<typename T::value_type>> : true_type {
};
static_assert(HasValueTypeT<vector<int>>::value);
static_assert(HasValueTypeT<map<int,double>>::value);
static_assert(HasValueTypeT<bool>::value); // this line fails to compile
static_assert(HasValueTypeT<void>::value); // and so does this line
The SFINAE-related code has three parts. The first part, a using-declaration, allows creation of a built-in type from an anonymous parameter pack. The actual type is unimportant, and we’ve used void. The use of a parameter pack makes instantiations for any number (we’ve used zero or one) of template type parameters legal.
The second part is a non-specialization which inherits from std::false_type (whose ::value field is false). This is the “general” form of the template, which is always able to be instantiated, regardless of the type used as the first template type parameter.
The third part is a partial specialization which is attempted to be specialized (for all types of template type parameter T). This succeeds if, and only if, the construction of VoidT<typename T::value_type> succeeds, which it does for any class providing this typedef. The fact that the specialization inherits from std::true_type means its ::value field is true.
The learning curve in SFINAE is mainly concerned with the syntax. However, using similar techniques the presence of named data members or member functions can be tested for, and presence (or lack) and be reported with more friendly messages (for example via static_assert()).
Concepts
Just a quick word about the feature of C++ that some template afficionados have been waiting for the longest. In summary, concepts are meant to provide (static) type checking to template type parameters in a similar way that function prototypes add static type checking to function calls. (Incidentally, C++’s syntax was adopted for ISO C, checks were not present in K&R C.) Use of concepts allows for more graceful failures to attempted compilation than typically seen, where error messages run into hundreds of lines. The chance of the wrong code “accidentally compiling” is much reduced, too.
What was originally hoped for as a C++11 feature has finally been approved in recent times, so major compilers (in addition to the current GCC concepts branch) should be supporting concepts in C++ soon.
In the next article of this mini-series, we’ll take a look at an application of TMP, a branch of C++ which has been around almost as long as CRTP.
Learn Modern C++ 