A priori, there might be no reason to think that templates and inheritance interact in interesting ways. If anything, we know from Chapter 13 that deriving from dependent base classes forces us to deal carefully with unqualified names. However, it turns out that some interesting techniques combine these two features, including the Curiously Recurring Template Pattern (CRTP) and mixins. In this chapter, we describe a few of these techniques.
C++ classes are often “empty,” which means that their internal representation does not require any bits of memory at run time. This is the case typically for classes that contain only type members, nonvirtual function members, and static data members. Nonstatic data members, virtual functions, and virtual base classes, on the other hand, do require some memory at running time.
Even empty classes, however, have nonzero size. Try the following program if you’d like to verify this:
inherit/empty.cpp
#include <iostream>
class EmptyClass {
};
int main()
{
std::cout << "sizeof(EmptyClass):" << sizeof(EmptyClass) << ’\n’;
}
For many platforms, this program will print 1 as size of EmptyClass. A few systems impose more strict alignment requirements on class types and may print another small integer (typically, 4).
The designers of C++ had various reasons to avoid zero-size classes. For example, an array of zerosize classes would presumably have size zero too, but then the usual properties of pointer arithmetic would no longer apply. For example, let’s assume ZeroSizedT is a zero-size type:
ZeroSizedT z[10];
…
&z[i] - &z[j] //compute distance between pointers/addresses
Normally, the difference in the previous example is obtained by dividing the number of bytes between the two addresses by the size of the type to which it is pointing, but when that size is zero this is clearly not satisfactory.
However, even though there are no zero-size types in C++, the C++ standard does specify that when an empty class is used as a base class, no space needs to be allocated for it provided that it does not cause it to be allocated to the same address as another object or subobject of the same type. Let’s look at some examples to clarify what this empty base class optimization (EBCO) means in practice. Consider the following program:
inherit/ebco1.cpp
#include <iostream>
class Empty {
using Int = int;// type alias members don’t make a class nonempty
};
class EmptyToo : public Empty {
};
class EmptyThree : public EmptyToo {
};
int main()
{
std::cout << "sizeof(Empty): " << sizeof(Empty) << ’\n’;
std::cout << "sizeof(EmptyToo): " << sizeof(EmptyToo) << ’\n’;
std::cout << "sizeof(EmptyThree): " << sizeof(EmptyThree) << ’\n’;
}
If your compiler implements the EBCO, it will print the same size for every class, but none of these classes has size zero (see Figure 21.1). This means that within class EmptyToo, the class Empty is not given any space. Note also that an empty class with optimized empty bases (and no other bases) is also empty. This explains why class EmptyThree can also have the same size as class Empty. If your compiler does not implement the EBCO, it will print different sizes (see Figure 21.2).
Figure 21.1. Layout of EmptyThree by a compiler that implements the EBCO
Figure 21.2. Layout of EmptyThree by a compiler that does not implement the EBCO
Consider an example that runs into a constraint of the EBCO:
inherit/ebco2.cpp
#include <iostream>!
class Empty {
using Int = int; // type alias members don’t make a class nonempty
};
class EmptyToo : public Empty {
};
class NonEmpty : public Empty, public EmptyToo {
};
int main()
{
std::cout <<"sizeof(Empty): " << sizeof(Empty) <<’\n’;
std::cout <<"sizeof(EmptyToo): " << sizeof(EmptyToo) <<’\n’;
std::cout <<"sizeof(NonEmpty): " << sizeof(NonEmpty) <<’\n’;
}
It may come as a surprise that class NonEmpty is not an empty class. After all, it does not have any members and neither do its base classes. However, the base classes Empty and EmptyToo of NonEmpty cannot be allocated to the same address because this would cause the base class Empty of EmptyToo to end up at the same address as the base class Empty of class NonEmpty. In other words, two subobjects of the same type would end up at the same offset, and this is not permitted by the object layout rules of C++. It may be conceivable to decide that one of the Empty base subobjects is placed at offset “0 bytes” and the other at offset “1 byte,” but the complete NonEmpty object still cannot have a size of 1 byte because in an array of two NonEmpty objects, an Empty subobject of the first element cannot end up at the same address as an Empty subobject of the second element (see Figure 21.3).
Figure 21.3. Layout of NonEmpty by a compiler that implements the EBCO
The rationale for the constraint on the EBCO stems from the fact that it is desirable to be able to compare whether two pointers point to the same object. Because pointers are nearly always internally represented as just addresses, we must ensure that two different addresses (i.e., pointer values) correspond to two different objects.
The constraint may not seem very significant. However, in practice, it is often encountered because many classes tend to inherit from a small set of empty classes that define some common type aliases. When two subobjects of such classes are used in the same complete object, the optimization is inhibited.
Even with this constraint, the EBCO is an important optimization for template libraries because a number of techniques rely on the introduction of base classes simply for the purpose of introducing new type aliases or providing extra functionality without adding new data. Several such techniques will be described in this chapter.
The EBCO has no equivalent for data members because (among other things) it would create some problems with the representation of pointers to members. As a result, it is sometimes desirable to implement as a (private) base class what would at first sight be thought of as a member variable. However, this is not without its challenges.
The problem is most interesting in the context of templates because template parameters are often substituted with empty class types, but in general we cannot rely on this rule. If nothing is known about a template type parameter, the EBCO cannot easily be exploited. Indeed, consider the following trivial example:
template<typename T1, typename T2>
class MyClass {
private:
T1 a;
T2 b;
…
};
It is entirely possible that one or both template parameters are substituted by an empty class type. If this is the case, then the representation of MyClass<T1,T2> may be suboptimal and may waste a word of memory for every instance of a MyClass<T1,T2>.
This can be avoided by making the template arguments base classes instead:
template<typename T1, typename T2>
class MyClass : private T1, private T2 {
};
However, this straightforward alternative has its own set of problems:
• It doesn’t work when T1 or T2 is substituted with a nonclass type or with a union type.
• It also doesn’t work when the two parameters are substituted with the same type (although this can be addressed fairly easily by adding another layer of inheritance; see page 513).
• The class may be final, in which case attempts to inherit from it will cause an error.
Even if we satisfactorily addressed these problems, a very serious problem persists: Adding a base class can fundamentally modify the interface of the given class. For our MyClass class, this may not seem significant because there are very few interface elements to affect, but as we see later in this chapter, inheriting from a template parameter can affect whether a member function is virtual. Clearly, this approach to exploiting the EBCO is fraught with all kinds of trouble.
A more practical tool can be devised for the common case when a template parameter is known to be substituted by class types only and when another member of the class template is available. The main idea is to “merge” the potentially empty type parameter with the other member using the EBCO. For example, instead of writing
template<typename CustomClass>
class Optimizable {
private:
CustomClass info; // might be empty
void* storage;
…
};
a template implementer would use the following:
template<typename CustomClass>
class Optimizable {
private:
BaseMemberPair<CustomClass, void*> info_and_storage;
…
};
Even without seeing the implementation of the template BaseMemberPair, it is clear that its use makes the implementation of Optimizable more verbose. However, various template library implementers have reported that the performance gains (for the clients of their libraries) do justify the added complexity. We explore this idiom further in our discussion of tuple storage in Section 25.1.1 on page 576.
The implementation of BaseMemberPair can be fairly compact:
inherit/basememberpair.hpp
#ifndef BASE_MEMBER_PAIR_HPP
#define BASE_MEMBER_PAIR_HPP
template<typename Base, typename Member>
class BaseMemberPair : private Base {
private:
Member mem;
public:
// constructor
BaseMemberPair (Base const & b, Member const & m)
: Base(b), mem(m) {
}
// access base class data via first()
Base const& base() const {
return static_cast<Base const&>(*this);
}
Base& base() {
return static_cast<Base&>(*this);
}
// access member data via second()
Member const& member() const {
return this->mem;
}
Member& member() {
return this->mem;
}
};
#endif // BASE_MEMBER_PAIR_HPP
An implementation needs to use the member functions base() and member() to access the encapsulated (and possibly storage-optimized) data members.
Another pattern is the Curiously Recurring Template Pattern (CRTP). This oddly named pattern refers to a general class of techniques that consists of passing a derived class as a template argument to one of its own base classes. In its simplest form, C++ code for such a pattern looks as follows:
template<typename Derived>
class CuriousBase {
…
};
class Curious : public CuriousBase<Curious> {
…
};
Our first outline of CRTP shows a nondependent base class: The class Curious is not a template and is therefore immune to some of the name visibility issues of dependent base classes. However, this is not an intrinsic characteristic of CRTP. Indeed, we could just as well have used the following alternative outline:
template<typename Derived>
class CuriousBase {
…
};
template<typename T>
class CuriousTemplate : public CuriousBase<CuriousTemplate<T>> {
…
};
By passing the derived class down to its base class via a template parameter, the base class can customize its own behavior to the derived class without requiring the use of virtual functions. This makes CRTP useful to factor out implementations that can only be member functions (e.g., constructor, destructors, and subscript operators) or are dependent on the derived class’s identity.
A simple application of CRTP consists of keeping track of how many objects of a certain class type were created. This is easily achieved by incrementing an integral static data member in every constructor and decrementing it in the destructor. However, having to provide such code in every class is tedious, and implementing this functionality via a single (non-CRTP) base class would confuse the object counts for different derived classes. Instead, we can write the following template:
inherit/objectcounter.hpp
#include <cstddef>
template<typename CountedType>
class ObjectCounter {
private:
inline static std::size_t count = 0; // number of existing objects
protected:
// default constructor
ObjectCounter() {
++count;
}
// copy constructor
ObjectCounter (ObjectCounter<CountedType> const&) {
++count;
}
// move constructor
ObjectCounter (ObjectCounter<CountedType> &&) {
++count;
}
// destructor
~ObjectCounter() {
--count;
}
public:
// return number of existing objects:
static std::size_t live() {
return count;
}
};
Note that we use inline to be able to define and initialize the count member inside the class structure. Before C++17, we had to define it outside the class template:
template<typename CountedType>
class ObjectCounter {
private:
static std::size_t count; // number of existing objects
…
};
// initialize counter with zero:
template<typename CountedType>
std::size_t ObjectCounter<CountedType>::count = 0;
If we want to count the number of live (i.e., not yet destroyed) objects for a certain class type, it suffices to derive the class from the ObjectCounter template. For example, we can define and use a counted string class along the following lines:
inherit/countertest.cpp
#include "objectcounter.hpp"
#include <iostream>
template<typename CharT>
class MyString : public ObjectCounter<MyString<CharT>> {
…
};
int main()
{
MyString<char> s1, s2;
MyString<wchar_t> ws;
std::cout << "num of MyString<char>: "
<< MyString<char>::live() << '\n';
std::cout << "num of MyString<wchar_t>: "
<< ws.live() << '\n';
}
In 1994, John J. Barton and Lee R. Nackman presented a template technique that they called restricted template expansion (see [BartonNackman]). The technique was motivated in part by the fact that—at the time—function template overloading was severely limited1 and namespaces were not available in most compilers.
To illustrate this, suppose we have a class template Array for which we want to define the equality operator ==. One possibility is to declare the operator as a member of the class template, but this is not good practice because the first argument (binding to the this pointer) is subject to conversion rules that differ from the second argument. Because operator == is meant to be symmetrical with respect to its arguments, it is preferable to declare it as a namespace scope function. An outline of a natural approach to its implementation may look like the following:
template<typename T>
class Array {
public:
…
};
template<typename T>
bool operator== (Array<T> const& a, Array<T> const& b)
{
…
}
However, if function templates cannot be overloaded, this presents a problem: No other operator == template can be declared in that scope, and yet it is likely that such a template would be needed for other class templates. Barton and Nackman resolved this problem by defining the operator in the class as a normal friend function:
template<typename T>
class Array {
static bool areEqual(Array<T> const& a, Array<T> const& b);
public:
…
friend bool operator== (Array<T> const& a, Array<T> const& b){
return areEqual(a, b);
}
};
Suppose this version of Array is instantiated for type float. The friend operator function is then declared as a result of that instantiation, but note that this function itself is not an instantiation of a function template. It is a normal nontemplate function that gets injected in the global scope as a side effect of the instantiation process. Because it is a nontemplate function, it could be overloaded with other declarations of operator == even before overloading of function templates was added to the language. Barton and Nackman called this restricted template expansion because it avoided the use of a template operator==(T, T) that applied to all types T (in other words, unrestricted expansion).
Because
operator== (Array<T> const&, Array<T> const&)
is defined inside a class definition, it is implicitly considered to be an inline function, and we therefore decided to delegate the implementation to a static member function areEqual, which doesn’t need to be inline.
Name lookup for friend function definitions has changed since 1994, so the Barton-Nackman trick is not as useful in standard C++. At the time of its invention, friend declarations would be visible in the enclosing scope of a class template when that template was instantiated via a process called friend name injection. Standard C++ instead finds friend function declarations via argument-dependent lookup (see Section 13.2.2 on page 220 for the specific details). This means that at least one of the arguments of the function call must already have the class containing the friend function as an associated class. The friend function would not be found if the arguments were of an unrelated class type that could be converted to the class containing the friend. For example:
inherit/wrapper.cpp
class S {
};
template<typename T>
class Wrapper {
private:
T object;
public:
Wrapper(T obj) : object(obj) { //implicit conversion from T to Wrapper<T>
}
friend void foo(Wrapper<T> const&) {
}
};
int main()
{
S s;
Wrapper<S> w(s);
foo(w); // OK: Wrapper<S> is a class associated withw
foo(s); // ERROR: Wrapper<S> is not associated with s
}
Here, the call foo(w) is valid because the function foo() is a friend declared in Wrapper<S> which is a class associated with the argument w.2 However, in the call foo(s), the friend declaration of function foo(Wrapper<S> const&) is not visible because the class Wrapper<S> in which it is defined is not associated with the argument s of type S. Hence, even though there is a valid implicit conversion from type S to type Wrapper<S> (through the constructor of Wrapper<S>), this conversion is never considered because the candidate function foo() is not found in the first place. At the time Barton and Nackman invented their trick, friend name injection would have made the friend foo() visible and the call foo(s) would succeed.
In modern C++, the only advantages to defining a friend function in a class template over simply defining an ordinary function template are syntactic: friend function definitions have access to the private and protected members of their enclosing class and don’t need to restate all of the template parameters of enclosing class templates. However, friend function definitions can be useful when combined with the Curiously Recurring Template Pattern (CRTP), as illustrated in the operator implementations described in the following section.
When implementing a class that provides overloaded operators, it is common to provide overloads for a number of different (but related) operators. For example, a class that implements the equality operator (==) will likely also implement the inequality operator (!=), and a class that implements the less-than operator (<) will likely implement the other relational operators as well (>, <=, >=). In many cases, the definition of only one of these operators is actually interesting, while the others can simply be defined in terms of that one operator. For example, the inequality operator for a class X is likely to be defined in terms of the equality operator:
bool operator!= (X const& x1, X const& x2) {
return !(x1 == x2);
}
Given the large number of types with similar definitions of !=, it is tempting to generalize this into a template:
template<typename T>
bool operator!= (T const& x1, T const& x2) {
return !(x1 == x2);
}
In fact, the C++ standard library contains similar such definitions as part of the <utility> header. However, these definitions (for !=, >, <=, and >=) were relegated to the namespace std::rel_ops during standardization, when it was determined that they caused problems when made available in namespace std. Indeed, having these definitions visible makes it appear that any type has an != operator (which may fail to instantiate), and that operator will always be an exact match for both of its arguments. While the first problem can be overcome through the use of SFINAE techniques (see Section 19.4 on page 416), such that this != definition will only be instantiated for types with a suitable == operator, the second problem remains: The general != definition above will be preferred over user-provided definitions that require, for example, a derived-to-base conversion, which may come as a surprise.
An alternative formulation of these operator templates based on CRTP allows classes to opt in to the general operator definitions, providing the benefits of increased code reuse without the side effects of an overly general operator:
inherit/equalitycomparable.cpp
template<typename Derived>
class EqualityComparable
{
public:
friend bool operator!= (Derived const& x1, Derived const& x2) {
return !(x1 == x2);
}
};
class X : public EqualityComparable<X>
{
public:
friend bool operator== (X const& x1, X const& x2) {
// implement logic for comparing two objects of type X
}
};
int main()
{
X x1, x2;
if (x1 != x2) { }
}
Here, we have combined CRTP with the Barton-Nackman trick. EqualityComparable<> uses CRTP to provide an operator!= for its derived class based on the derived class’s definition of operator==. It actually provides that definition via a friend function definition (the Barton-Nackman trick), which gives the two parameters to operator!= equal behavior for conversions.
CRTP can be useful when factoring behavior into a base class while retaining the identity of the eventual derived class. Along with the Barton-Nackman trick, CRTP can provide general definitions for a number of operators based on a few canonical operators. These properties have made CRTP with the Barton-Nackman trick a favorite technique for authors of C++ template libraries.
The use of CRTP and the Barton-Nackman trick to define some operators is a convenient shortcut. We can take this idea further, such that the CRTP base class defines most or all of the public interface of a class in terms of a much smaller (but easier to implement) interface exposed by the CRTP derived class. This pattern, called the facade pattern, is particularly useful when defining new types that need to meet the requirements of some existing interface—numeric types, iterators, containers, and so on.
To illustrate the facade pattern, we will implement a facade for iterators, which drastically simplifies the process of writing an iterator that conforms to the requirements of the standard library. The required interface for an iterator type (particularly a random access iterator) is quite large. The following skeleton for class template IteratorFacade demonstrates the requirements for an iterator interface:
inherit/iteratorfacadeskel.hpp
template<typename Derived, typename Value, typename Category,
typename Reference = Value&, typename Distance = std::ptrdiff_t>
class IteratorFacade
{
public:
using value_type = typename std::remove_const<Value>::type;
using reference = Reference;
using pointer = Value*;
using difference_type = Distance;
using iterator_category = Category;
// input iterator interface:
reference operator *() const { … }
pointer operator ->() const { … }
Derived& operator ++() { … }
Derived operator ++(int) { … }
friend bool operator== (IteratorFacade const& lhs,
IteratorFacade const& rhs) { … }
…
// bidirectional iterator interface:
Derived& operator --() { … }
Derived operator --(int) { … }
// random access iterator interface:
reference operator [](difference_type n) const { … }
Derived& operator +=(difference_type n) { … }
…
friend difference_type operator -(IteratorFacade const& lhs,
IteratorFacade const& rhs) { … }
friend bool operator <(IteratorFacade const& lhs,
IteratorFacade const& rhs) { … }
…
};
We’ve omitted some declarations for brevity, but even implementing every one of those listed for every new iterator is quite a chore. Fortunately, that interface can be distilled into a few core operations:
• For all iterators:
– dereference(): Access the value to which the iterator refers (typically used via operators * and ->).
– increment(): Move the iterator to refer to the next item in the sequence.
– equals(): Determine whether two iterators refer to the same item in a sequence.
• For bidirectional iterators:
– decrement(): Move the iterator to refer to the previous item in the list.
• For random-access iterators:
– advance(): Move the iterator n steps forward (or backward).
– measureDistance(): Determine the number of steps to get from one iterator to another in the sequence.
The role of the facade is to adapt a type that implements only those core operations to provide the full iterator interface. The implementation IteratorFacade mostly involves mapping the iterator syntax to the minimal interface. In the following examples, we use the member functions asDerived() to access the CRTP derived class:
Derived& asDerived() { return *static_cast<Derived*>(this); }
Derived const& asDerived() const {
return *static_cast<Derived const*>(this);
}
Given that definition, the implementation of much of the facade is straightforward.3 We only illustrate the definitions for some of the input iterator requirements; the others follow similarly.
reference operator*() const {
return asDerived().dereference();
}
Derived& operator++() {
asDerived().increment();
return asDerived();
}
Derived operator++(int) {
Derived result(asDerived());
asDerived().increment();
return result;
}
friend bool operator== (IteratorFacade const& lhs,
IteratorFacade const& rhs) {
return lhs.asDerived().equals(rhs.asDerived());
}
With our definition of IteratorFacade, we can now easily define an iterator into a simple linked-list class. For example, imagine that we define a node in the linked list as follows:
inherit/listnode.hpp
template<typename T>
class ListNode
{
public:
T value;
ListNode<T>* next = nullptr;
~ListNode() { delete next; }
};
Using IteratorFacade, an iterator into such a list can be defined in a straightforward manner:
inherit/listnodeiterator0.hpp
template<typename T>
class ListNodeIterator
: public IteratorFacade<ListNodeIterator<T>, T,
std::forward_iterator_tag>
{
ListNode<T>* current = nullptr;
public:
T& dereference() const {
return current->value;
}
void increment() {
current = current->next;
}
bool equals(ListNodeIterator const& other) const {
return current == other.current;
}
ListNodeIterator(ListNode<T>* current = nullptr) : current(current) { }
};
ListNodeIterator provides all of the correct operators and nested types needed to act as a forward iterator, and requires very little code to implement. As we will see later, defining more complicated iterators (e.g., random access iterators) requires only a small amount of extra work.
One downside to our implementation of ListNodeIterator is that we were required to expose, as a public interface, the operations dereference(), advance(), and equals(). To eliminate this requirement, we can rework IteratorFacade to perform all of its operations on the derived CRTP class through a separate access class, which we call IteratorFacadeAccess:
inherit/iteratorfacadeaccessskel.hpp
// ‘friend’ this class to allow IteratorFacade access to core iterator operations:
class IteratorFacadeAccess
{
// only IteratorFacade can use these definitions
template<typename Derived, typename Value, typename Category,
typename Reference, typename Distance>
friend class IteratorFacade;
// required of all iterators:
template<typename Reference, typename Iterator>
static Reference dereference(Iterator const& i) {
return i.dereference();
}
…
// required of bidirectional iterators:
template<typename Iterator>
static void decrement(Iterator& i) {
return i.decrement();
}
// required of random-access iterators:
template<typename Iterator, typename Distance>
static void advance(Iterator& i, Distance n) {
return i.advance(n);
}
…
};
This class provides static member functions for each of the core iterator operations, calling the corresponding (nonstatic) member function of the provided iterator. All of the static member functions are private, with the access only granted to IteratorFacade itself. Therefore, our ListNodeIterator can make IteratorFacadeAccess a friend and keep private the interface needed by the facade:
friend class IteratorFacadeAccess;
Our IteratorFacade makes it easy to build an iterator adapter that takes an existing iterator and exposes a new iterator that provides some transformed view of the underlying sequence. For example, we might have a container of Person values:
inherit/person.hpp
struct Person {
std::string firstName;
std::string lastName;
friend std::ostream& operator<<(std::ostream& strm, Person const& p) {
return strm << p.lastName << ", " << p.firstName;
}
};
However, rather than iterating over all of the Person values in the container, we only want to see the first names. In this section, we develop an iterator adapter called ProjectionIterator that allows us “project” the values of an underlying (base) iterator to some pointer-to-data member, for example, Person::firstName.
A ProjectionIterator is an iterator defined in terms of the base iterator (Iterator) and the type of value that will be exposed by the iterator (T):
inherit/projectioniteratorskel.hpp
template<typename Iterator, typename T>
class ProjectionIterator
: public IteratorFacade<
ProjectionIterator<Iterator, T>,
T,
typename std::iterator_traits<Iterator>::iterator_category,
T&,
typename std::iterator_traits<Iterator>::difference_type>
{
using Base = typename std::iterator_traits<Iterator>::value_type;
using Distance =
typename std::iterator_traits<Iterator>::difference_type;
Iterator iter;
T Base::* member;
friend class IteratorFacadeAccess
… //implement core iterator operations for IteratorFacade
public:
ProjectionIterator(Iterator iter, T Base::* member)
: iter(iter), member(member) { }
};
template<typename Iterator, typename Base, typename T>
auto project(Iterator iter, T Base::* member) {
return ProjectionIterator<Iterator, T>(iter, member);
}
Each projection iterator stores two values: iter, which is the iterator into the underlying sequence (of Base values), and member, a pointer-to-data member describing which member to project through. With that in mind, we consider the template arguments provided to the IteratorFacade base class. The first is the ProjectionIterator itself (to enable CRTP). The second (T) and fourth (T&) arguments are the value and reference types of our projection iterator, defining this as a sequence of T values.4 The third and fifth arguments merely pass through the category and difference types of the underlying iterator. Therefore, our projection iterator will be an input iterator when Iterator is an input iterator, a bidirectional iterator when Iterator is a bidirectional iterator, and so on. A project() function makes it easy to build projection iterators.
The only missing pieces are the implementations of the core requirements for IteratorFacade. The most interesting is dereference(), which dereferences the underlying iterator and then projects through the pointer-to-data member:
T& dereference() const {
return (*iter).*member;
}
The remaining operations are implemented in terms of the underlying iterator:
void increment() {
++iter;
}
bool equals(ProjectionIterator const& other) const {
return iter == other.iter;
}
void decrement() {
--iter;
}
For brevity, we’ve omitted the definitions for random access iterators, which follow analogously.
That’s it! With our projection iterator, we can print out the first names of a vector containing Person values:
inherit/projectioniterator.cpp
#include <vector>
#include <algorithm>
#include <iterator>
int main()
{
std::vector<Person> authors = { {"David", "Vandevoorde"},
{"Nicolai", "Josuttis"},
{"Douglas", "Gregor"} };
std::copy(project(authors.begin(), &Person::firstName),
project(authors.end(), &Person::firstName),
std::ostream_iterator<std::string>(std::cout, "\n"));
}
David
Nicolai
Douglas
The facade pattern is particularly useful for creating new types that conform to some specific interface. New types need only expose some small number of core operations (between three and six for our iterator facade) to the facade, and the facade takes care of providing a complete and correct public interface using a combination of CRTP and the Barton-Nackman trick.
Consider a simple Polygon class that consists of a sequence of points:
class Point
{
public:
double x, y;
Point() : x(0.0), y(0.0) { }
Point(double x, double y) : x(x), y(y) { }
};
class Polygon
{
private:
std::vector<Point> points;
public:
… //public operations
};
This Polygon class would be more useful if the user could extend the set of information associated with each Point to include application-specific data such as the color of each point, or perhaps associate a label with each point. One option to make this extension possible would be to parameterize Polygon based on the type of the point:
template<typename P>
class Polygon
{
private:
std::vector<P> points;
public:
… //public operations
};
Users could conceivably create their own Point-like data type that provided the same interface as Point but includes other application-specific data, using inheritance:
class LabeledPoint : public Point
{
public:
std::string label;
LabeledPoint() : Point(), label("") { }
LabeledPoint(double x, double y) : Point(x, y), label("") { }
};
This implementation has its shortcomings. For one, it requires that the type Point be exposed to the user so that the user can derive from it. Also, the author of LabeledPoint needs to be careful to provide exactly the same interface as Point (e.g., inheriting or providing all of the same constructors as Point), or LabeledPoint will not work with Polygon. This constraint becomes more problematic if Point changes from one version of the Polygon template to another: The addition of a new Point constructor could require each derived class to be updated.
Mixins provide an alternative way to customize the behavior of a type without inheriting from it. Mixins essentially invert the normal direction of inheritance, because the new classes are “mixed in” to the inheritance hierarchy as base classes of a class template rather than being created as a new derived class. This approach allows the introduction of new data members and other operations without requiring any duplication of the interface.
A class template that supports mixins will typically accept an arbitrary number of extra classes from which it will derive:
template<typename… Mixins>
class Point : public Mixins…
{
public:
double x, y;
Point() : Mixins()…, x(0.0), y(0.0) { }
Point(double x, double y) : Mixins()…, x(x), y(y) { }
};
Now, we can “mix in” a base class containing a label to produce a LabeledPoint:
class Label
{
public:
std::string label;
Label() : label("") { }
};
using LabeledPoint = Point<Label>;
or even mix in several base classes:
class Color
{
public:
unsigned char red = 0, green = 0, blue = 0;
};
using MyPoint = Point<Label, Color>;
With this mixin-based Point, it becomes easy to introduce additional information to Point without changing its interface, so Polygon becomes easier to use and evolve. Users need only apply the implicit conversion from the Point specialization to their mixin class (Label or Color, above) to access that data or interface. Moreover, the Point class can even be entirely hidden, with the mixins provided to the Polygon class template itself:
template<typename… Mixins>
class Polygon
{
private:
std::vector<Point<Mixins…>> points;
public:
… //public operations
};
Mixins are useful in cases where a template needs some small level of customization—such as decorating internally stored objects with user-specified data—without requiring the library to expose and document those internal data types and their interfaces.
Mixins can be made more powerful by combining them with the Curiously Recurring Template Pattern (CRTP) described in Section 21.2 on page 495. Here, each of the mixins is actually a class template that will be provided with the type of the derived class, allowing additional customization to that derived class. A CRTP-mixin version of Point would be written as follows:
template<template<typename>… Mixins>
class Point : public Mixins<Point>…
{
public:
double x, y;
Point() : Mixins<Point>()…, x(0.0), y(0.0) { }
Point(double x, double y) : Mixins<Point>()…, x(x), y(y) { }
};
This formulation requires some more work for each class that will be mixed in, so classes such as Label and Color will need to become class templates. However, the mixed-in classes can now tailor their behavior to the specific instance of the derived class they’ve been mixed into. For example, we can mix the previously discussed ObjectCounter template into Point to count the number of points created by Polygon and compose that mixin with other application-specific mixins as well.
Mixins also allow us to indirectly parameterize other attributes of the derived class, such as the virtuality of a member function. A simple example shows this rather surprising technique:
#include <iostream>
class NotVirtual {
};
class Virtual {
public:
virtual void foo() {
}
};
template<typename… Mixins>
class Base :
public Mixins… { public:
// the virtuality of foo() depends on its declaration
// (if any) in the base classes Mixins…
void foo() {
std::cout << "Base::foo()" << ’\n’;
}
};
template<typename… Mixins>
class Derived : public Base<Mixins…> {
public:
void foo() {
std::cout << "Derived::foo()" << ’\n’;
}
};
int main()
{
Base<NotVirtual>* p1 = new Derived<NotVirtual>;
p1->foo(); // calls Base::foo()
Base<Virtual>* p2 = new Derived<Virtual>;
p2->foo(); // calls Derived::foo()
}
This technique can provide a tool to design a class template that is usable both to instantiate concrete classes and to extend using inheritance. However, it is rarely sufficient just to sprinkle virtuality on some member functions to obtain a class that makes a good base class for more specialized functionality. This sort of development method requires more fundamental design decisions. It is therefore usually more practical to design two different tools (class or class template hierarchies) than to try to integrate them all into one template hierarchy.
Various template techniques sometimes cause a class template to end up with many different template type parameters. However, many of these parameters often have reasonable default values. A natural way to define such a class template may look as follows:
template<typename Policy1 = DefaultPolicy1,
typename Policy2 = DefaultPolicy2,
typename Policy3 = DefaultPolicy3,
typename Policy4 = DefaultPolicy4>
class BreadSlicer {
…
};
Presumably, such a template can often be used with the default template argument values using the syntax BreadSlicer<>. However, if a nondefault argument must be specified, all preceding arguments must be specified too (even though they may have the default value).
Clearly, it would be attractive to be able to use a construct akin to BreadSlicer<Policy3 = Custom> rather than BreadSlicer<DefaultPolicy1, DefaultPolicy2, Custom>, as is the case right now. In what follows we develop a technique to enable almost exactly that.5
Our technique consists of placing the default type values in a base class and overriding some of them through derivation. Instead of directly specifying the type arguments, we provide them through helper classes. For example, we could write BreadSlicer<Policy3_is<Custom>>. Because each template argument can describe any of the policies, the defaults cannot be different. In other words, at a high level, every template parameter is equivalent:
template<typename PolicySetter1 = DefaultPolicyArgs,
typename PolicySetter2 = DefaultPolicyArgs,
typename PolicySetter3 = DefaultPolicyArgs,
typename PolicySetter4 = DefaultPolicyArgs>
class BreadSlicer {
using Policies = PolicySelector<PolicySetter1, PolicySetter2,
PolicySetter3, PolicySetter4>;
// use Policies::P1, Policies::P2, … to refer to the various policies
…
};
The remaining challenge is to write the PolicySelector template. It has to merge the different template arguments into a single type that overrides default type alias members with whichever non-defaults were specified. This merging can be achieved using inheritance:
// PolicySelector<A,B,C,D> creates A,B,C,D as base classes
// Discriminator<> allows having even the same base class more than once
template<typename Base, int D>
class Discriminator : public Base {
};
template<typename Setter1, typename Setter2,
typename Setter3, typename Setter4>
class PolicySelector : public Discriminator<Setter1,1>,
public Discriminator<Setter2,2>,
public Discriminator<Setter3,3>,
public Discriminator<Setter4,4> {
};
Note the use of an intermediate Discriminator template. It is needed to allow the various Setter types to be identical. (You cannot have multiple direct base classes of the same type. Indirect base classes, on the other hand, can have types that are identical to those of other bases.)
As announced earlier, we’re collecting the defaults in a base class:
// name default policies as P1, P2, P3, P4
class DefaultPolicies {
public:
using P1 = DefaultPolicy1;
using P2 = DefaultPolicy2;
using P3 = DefaultPolicy3;
using P4 = DefaultPolicy4;
};
However, we must be careful to avoid ambiguities if we end up inheriting multiple times from this base class. Therefore, we ensure that the base class is inherited virtually:
// class to define a use of the default policy values
// avoids ambiguities if we derive from DefaultPolicies more than once
class DefaultPolicyArgs : virtual public DefaultPolicies {
};
Finally, we also need some templates to override the default policy values:
template<typename Policy>
class Policy1_is : virtual public DefaultPolicies {
public:
using P1 = Policy; // overriding type alias
};
template<typename Policy>
class Policy2_is : virtual public DefaultPolicies {
public:
using P2 = Policy; // overriding type alias
};
template<typename Policy>
class Policy3_is : virtual public DefaultPolicies {
public:
using P3 = Policy; // overriding type alias
};
template<typename Policy>
class Policy4_is : virtual public DefaultPolicies {
public:
using P4 = Policy; // overriding type alias
};
With all this in place, our desired objective is achieved. Now let’s look at what we have by example. Let’s instantiate a BreadSlicer<> as follows:
BreadSlicer<Policy3_is<CustomPolicy>> bc;
For this BreadSlicer<> the type Policies is defined as
PolicySelector<Policy3_is<CustomPolicy>,
DefaultPolicyArgs,
DefaultPolicyArgs,
DefaultPolicyArgs>
With the help of the Discriminator<> class templates, this results in a hierarchy in which all template arguments are base classes (see Figure 21.4). The important point is that these base classes
Figure 21.4. Resulting type hierarchy of BreadSlicer<>::Policies
all have the same virtual base class DefaultPolicies, which defines the default types for P1, P2, P3, and P4. However, P3 is redefined in one of the derived classes—namely, in Policy3_is<>. According to the domination rule, this definition hides the definition of the base class. Thus, this is not an ambiguity.6
Inside the template BreadSlicer you can refer to the four policies by using qualified names such as Policies::P3. For example:
template<…>
class BreadSlicer {
…
public:
void print () {
Policies::P3::doPrint();
}
…
};
In inherit/namedtmpl.cpp you can find the entire example.
We developed the technique for four template type parameters, but it obviously scales to any reasonable number of such parameters. Note that we never actually instantiate objects of the helper class that contain virtual bases. Hence, the fact that they are virtual bases is not a performance or memory consumption issue.
Bill Gibbons was the main sponsor behind the introduction of the EBCO into the C++ programming language. Nathan Myers made it popular and proposed a template similar to our BaseMemberPair to take better advantage of it. The Boost library contains a considerably more sophisticated template, called compressed_pair, that resolves some of the problems we reported for the MyClass template in this chapter. boost::compressed_pair can also be used instead of our BaseMemberPair.
CRTP has been in use since at least 1991. However, James Coplien was first to describe them formally as a class of patterns (see [CoplienCRTP]). Since then, many applications of CRTP have been published. The phrase parameterized inheritance is sometimes wrongly equated with CRTP. As we have shown, CRTP does not require the derivation to be parameterized at all, and many forms of parameterized inheritance do not conform to CRTP. CRTP is also sometimes confused with the Barton-Nackman trick (see Section 21.2.1 on page 497) because Barton and Nackman frequently used CRTP in combination with friend name injection (and the latter is an important component of the Barton-Nackman trick). Our use of CRTP with the Barton-Nackman trick to provide operator implementations follows the same basic approach as the Boost.Operators library ([BoostOperators]), which provides an extensive set of operator definitions. Similarly, our treatment of iterator facades follows that of the Boost.Iterator library ([BoostIterator]) which provides a rich, standard-library compliant iterator interface for a derived type that provides a few core iterator operations (equality, dereference, movement), and also addresses tricky issues involving proxy iterators (which we did not address for the sake of brevity). Our ObjectCounter example is almost identical to a technique developed by Scott Meyers in [MeyersCounting].
The notion of mixins has been around in Object-Oriented programming since at least 1986 ([Moon-Flavors]) as a way to introduce small pieces of functionality into an OO class. The use of templates for mixins in C++ became popular shortly after the first C++ standard was published, with two papers ([SmaragdakisBatoryMixins] and [EiseneckerBlinnCzarnecki]) describing the approaches commonly used today for mixins. Since then, it’s become a popular technique in C++ library design.
Named template arguments are used to simplify certain class templates in the Boost library. Boost uses metaprogramming to create a type with properties similar to our PolicySelector (but without using virtual inheritance). The simpler alternative presented here was developed by one of us (Vandevoorde).
1 It may be worthwhile to read Section 16.2 on page 326 to understand how function template overloading works in modern C++.
2 Note that S is also a class associated with w because it is a template argument for the type of w. The specific rules for ADL are discussed in Section 13.2.1 on page 219.
3 To simplify the presentation, we ignore the presence of proxy iterators, whose dereference operation does not return a true reference. A complete implementation of an iterator facade, such as the one in [BoostIterator], would adjust the result types of operator -> and operator[] to account for proxies.
4 Again, we assume that the underlying iterator returns a reference, rather than a proxy, to simplify the presentation.
5 Note that a similar language extension for function call arguments was proposed (and rejected) earlier in the C++ standardization process (see Section 17.4 on page 358 for details).
6 You can find the domination rule in Section 10.2/6 in the first C++ standard (see [C++98]) and a discussion about it in Section 10.1.1 of [EllisStroustrupARM].