Throughout this book we often use homogeneous containers and array-like types to illustrate the power of templates. Such homogeneous structures extend the concept of a C/C++ array and are pervasive in most applications. C++ (and C) also has a nonhomogeneous containment facility: the class (or struct). This chapter explores tuples, which aggregate data in a manner similar to classes and structs. For example, a tuple containing an int, a double, and a std::string is similar to a struct with int, double, and std::string members, except that the elements of the tuple are referenced positionally (as 0, 1, 2) rather than through names. The positional interface and the ability to easily construct a tuple from a typelist make tuples more suitable than structs for use with template metaprogramming techniques.
An alternative view on tuples is as a manifestation of a typelist in the executable program. For example, while a typelist Typelist<int, double, std::string> describes the sequence of types containing int, double, and std::string that can be manipulated at compile time, a Tuple<int, double, std::string> describes storage for an int, a double, and a std::string that can be manipulated at run time. For example, the following program creates an instance of such a tuple:
template<typename… Types>
class Tuple {
… // implementation discussed below
};
Tuple<int, double, std::string> t(17, 3.14, "Hello, World!");
It is common to use template metaprogramming with typelists to generate tuples that can be used to store data. For example, even though we’ve arbitrarily selected int, double, and std::string as the element types in the example above, we could have created the set of types stored by the tuple with a metaprogram.
In the remainder of this chapter, we will explore the implementation and manipulation of the Tuple class template, which is a simplified version of the class template std::tuple.
Tuples contain storage for each of the types in the template argument list. That storage can be accessed through a function template get, used as get<I>(t) for a tuple t. For example, get<0>(t) on the t in the previous example would return a reference to the int 17, while get<1>(t) returns a reference to the double 3.14.
The recursive formulation of tuple storage is based on the idea that a tuple containing N > 0 elements can be stored as both a single element (the first element, or header of the list) and a tuple containing N − 1 elements (the tail), with a separate special case for a zero-element tuple. Thus, a three-element tuple Tuple<int, double, std::string> can be stored as an int and a Tuple<double, std::string>. That two-element tuple can then be stored as a double and a Tuple<std::string>, which itself can be stored as a std::string and a Tuple<>. In fact, this is the same kind of recursive decomposition used in the generic versions of typelist algorithms, and the actual implementation of recursive tuple storage unfolds similarly:
template<typename… Types>
class Tuple;
// recursive case:
template<typename Head, typename… Tail>
class Tuple<Head, Tail…>
{
private:
Head head;
Tuple<Tail…> tail;
public:
// constructors:
Tuple() {
}
Tuple(Head const& head, Tuple<Tail…> const& tail)
: head(head), tail(tail) {
}
…
Head& getHead() { return head; }
Head const& getHead() const { return head; }
Tuple<Tail…>& getTail() { return tail; }
Tuple<Tail…> const& getTail() const { return tail; }
};
// basis case:
template<>
class Tuple<> {
// no storage required
};
In the recursive case, each Tuple instance contains a data member head that stores the first element in the list, along with a data member tail that stores the remaining elements in the list. The basis case is simply the empty tuple, which has no associated storage.
The get function template walks this recursive structure to extract the requested element:1
tuples/tupleget.hpp
// recursive case:
template<unsigned N>
struct TupleGet {
template<typename Head, typename… Tail>
static auto apply(Tuple<Head, Tail…> const& t) {
return TupleGet<N-1>::apply(t.getTail());
}
};
// basis case:
template<>
struct TupleGet<0> {
template<typename Head, typename… Tail>
static Head const& apply(Tuple<Head, Tail…> const& t) {
return t.getHead();
}
};
template<unsigned N, typename… Types>
auto get(Tuple<Types…> const& t) {
return TupleGet<N>::apply(t);
}
Note that the function template get is simply a thin wrapper over a call to a static member function of TupleGet. This technique is effectively a workaround for the lack of partial specialization of function templates (discussed in Section 17.3 on page 356), which we use to specialize on the value of N. In the recursive case (N > 0), the static member function apply() extracts the tail of the current tuple and decrements N to keep looking for the requested element later in the tuple. The basis case (N = 0) returns the head of the current tuple, completing the implementation.
578 Chapter 25: Tuples
Besides the constructors defined so far:
Tuple() {
}
Tuple(Head const& head, Tuple<Tail…> const& tail)
: head(head), tail(tail) {
}
for a tuple to be useful, we need to be able to construct it both from a set of independent values (one for each element) and from another tuple. Copy-constructing from a set of independent values passes the first of those values to initialize the head element (via its base class), then passes the remaining values to the base class representing the tail:
Tuple(Head const& head, Tail const&… tail)
: head(head), tail(tail…) {
}
This enables our initial Tuple example:
Tuple<int, double, std::string> t(17, 3.14, "Hello, World!");
However, this isn’t the most general interface: Users may wish to move-construct to initialize some (but perhaps not all) of the elements or to have an element constructed from a value of a different type. Therefore, we should use perfect forwarding (Section 15.6.3 on page 280) to initialize the tuple:
template<typename VHead, typename… VTail>
Tuple(VHead&& vhead, VTail&&… vtail)
: head(std::forward<VHead>(vhead)),
tail(std::forward<VTail>(vtail)…) {
}
Next, we implement support for constructing a tuple from another tuple:
template<typename VHead, typename… VTail>
Tuple(Tuple<VHead, VTail…> const& other)
: head(other.getHead()), tail(other.getTail()) { }
However, the introduction of this constructor does not suffice to allow tuple conversions: Given the tuple t above, an attempt to create another tuple with compatible types will fail:
// ERROR: no conversion from Tuple<int, double, string> to long
Tuple<long int, long double, std::string> t2(t);
The problem here is that the constructor template meant to initialize from a set of independent values is a better match than the constructor template that accepts a tuple. To address this problem, we have to use std::enable_if<> (see Section 6.3 on page 98 and Section 20.3 on page 469) to disable both member function templates when the tail does not have the expected length:
template<typename VHead, typename… VTail,
typename = std::enable_if_t<sizeof…(VTail)==sizeof…(Tail)>>
Tuple(VHead&& vhead, VTail&&… vtail)
: head(std::forward<VHead>(vhead)),
tail(std::forward<VTail>(vtail)…) { }
template<typename VHead, typename… VTail,
typename = std::enable_if_t<sizeof…(VTail)==sizeof…(Tail)>>
Tuple(Tuple<VHead, VTail…> const& other)
: head(other.getHead()), tail(other.getTail()) { }
You can find all constructor declarations in tuples/tuple.hpp.
A makeTuple() function template uses deduction to determine the element types of the Tuple it returns, making it far easier to create a tuple from a given set of elements:
tuples/maketuple.hpp
template<typename… Types>
auto makeTuple(Types&&… elems)
{
return Tuple<std::decay_t<Types>…>(std::forward<Types>(elems)…);
}
Again, we use perfect forwarding combined with the std::decay<> trait to convert string literals and other raw arrays into pointers and remove const and references. For example:
makeTuple(17, 3.14, "Hello, World!")
initializes a
Tuple<int, double, char const*>
Tuples are structural types that contain other values. To compare two tuples, it suffices to compare their elements. Therefore, we can write a definition of operator== to compare two definitions element-wise:
tuples/tupleeq.hpp
// basis case:
bool operator==(Tuple<> const&, Tuple<> const&)
{
// empty tuples are always equivalent
return true;
}
// recursive case:
template<typename Head1, typename… Tail1,
typename Head2, typename… Tail2,
typename = std::enable_if_t<sizeof…(Tail1)==sizeof…(Tail2)>>
bool operator==(Tuple<Head1, Tail1…> const& lhs,
Tuple<Head2, Tail2…> const& rhs)
{
return lhs.getHead() == rhs.getHead() &&
lhs.getTail() == rhs.getTail();
}
Like many algorithms on typelists and tuples, the element-wise comparison visits the head element and then recurses to visit the tail, eventually hitting the basis case. The !=, <, >, <=, and >= operators follow analogously.
Throughout this chapter, we will be creating new tuple types, so it is useful to be able to see those tuples in an executing program. The following operator<< prints any tuple whose element types can be printed:
tuples/tupleio.hpp
#include <iostream>
void printTuple(std::ostream& strm, Tuple<> const&, bool isFirst = true)
{
strm << ( isFirst ? ’(’ : ’)’ );
}
template<typename Head, typename… Tail>
void printTuple(std::ostream& strm, Tuple<Head, Tail…> const& t,
bool isFirst = true)
{
strm << ( isFirst ? "(" : ", " );
strm << t.getHead();
printTuple(strm, t.getTail(), false);
}
template<typename… Types>
std::ostream& operator<<(std::ostream& strm, Tuple<Types…> const& t)
{
printTuple(strm, t);
return strm;
}
Now, it is easy to create and display tuples. For example:
std::cout << makeTuple(1, 2.5, std::string("hello")) << ’\n’;
prints
(1, 2.5, hello)
A tuples is a container that provides the ability to access and modify each of its elements (through get) as well as to create new tuples (directly or with makeTuple()) and to break a tuple into its head and tail (getHead() and getTail()). These fundamental building blocks are sufficient to build a suite of tuple algorithms, such as adding or removing elements from a tuple, reordering the elements in a tuple, or selecting some subset of the elements in the tuple.
Tuple algorithms are particularly interesting because they require both compile-time and run-time computation. Like the typelist algorithms of Chapter 24, applying an algorithm to a tuple may result in a tuple with a completely different type, which requires compile-time computation. For example, reversing a Tuple<int, double, string> produces a Tuple<string, double, int>. However, like an algorithm for a homogeneous container (e.g., std::reverse() on a std::vector), tuple algorithms actually require code to execute at run time, and we need to be mindful of the efficiency of the generated code.
If we ignore the actual run-time component of our Tuple template, we see that it has precisely the same structure as the Typelist template developed in Chapter 24: It accepts any number of template type parameters. In fact, with a few partial specializations, we can turn Tuple into a full-featured typelist:
tuples/tupletypelist.hpp
// determine whether the tuple is empty:
template<>
struct IsEmpty<Tuple<>> {
static constexpr bool value = true;
};
// extract front element:
template<typename Head, typename… Tail>
class FrontT<Tuple<Head, Tail…>> {
public:
using Type = Head;
};
// remove front element:
template<typename Head, typename… Tail>
class PopFrontT<Tuple<Head, Tail…>> {
public:
using Type = Tuple<Tail…>;
};
// add element to the front:
template<typename… Types, typename Element>
class PushFrontT<Tuple<Types…>, Element> {
public:
using Type = Tuple<Element, Types…>;
};
// add element to the back:
template<typename… Types, typename Element>
class PushBackT<Tuple<Types…>, Element> {
public:
using Type = Tuple<Types…, Element>;
};
Now, all of the typelist algorithms developed in Chapter 24 work equally well with Tuple and Typelist, so that we easily can deal with the type of tuples. For example:
Tuple<int, double, std::string> t1(17, 3.14, "Hello, World!");
using
T2 = PopFront<PushBack<decltype(t1), bool>>;
T2 t2(get<1>(t1), get<2>(t1), true);
std::cout << t2;
which prints:
(3.14, Hello, World!, 1)
As we will see shortly, typelist algorithms applied to tuple types are often used to help determine the result type of a tuple algorithm.
For the values of tuples, the ability to add an element to the beginning or end of a tuple is important for building more advanced algorithms. As with typelists, insertion at the front of a tuple is far easier than insertion at the back, so we start with pushFront:
tuples/pushfront.hpp
template<typename… Types, typename V>
PushFront<Tuple<Types…>, V>
pushFront(Tuple<Types…> const& tuple, V const& value)
{
return PushFront<Tuple<Types…>, V>(value, tuple);
}
Adding a new element (called value) onto the front of an existing tuple requires us to form a new tuple with value as its head and the existing tuple as its tail. The resulting tuple type is Tuple<V, Types…>. However, we have opted to use the typelist algorithm PushFront to demonstrate the tight coupling between the compile-time and run-time aspects of tuple algorithms: The compile-time PushFront computes the type that we need to construct to produce the appropriate run-time value.
Adding a new element to the end of an existing tuple is more complicated, because it requires a recursive walk of the tuple, building up the modified tuple as we go. Note how the structure of the pushBack() implementation follows the recursive formulation of the typelist PushBack() from Section 24.2.3 on page 555:
tuples/pushback.hpp
// basis case
template<typename V>
Tuple<V> pushBack(Tuple<> const&, V const& value)
{
return Tuple<V>(value);
}
// recursive case
template<typename Head, typename… Tail, typename V>
Tuple<Head, Tail…, V>
pushBack(Tuple<Head, Tail…> const& tuple, V const& value)
{
return Tuple<Head, Tail…, V>(tuple.getHead(),
pushBack(tuple.getTail(), value));
The basis case, as expected, appends a value to a zero-length tuple by producing a tuple containing just that value. In the recursive case, we form a new tuple from the current element at the beginning of the list (tuple.getHead()) and the result of adding the new element to the tail of the list (the recursive pushBack call). While we have opted to express the constructed type as Tuple<Head, Tail…, V>, we note that this is equivalent to using the compile-time PushBack<Tuple<Head, Tail…>, V>.
Also, popFront() is easy to implement:
tuples/popfront.hpp
template<typename… Types>
PopFront<Tuple<Types…>>
popFront(Tuple<Types…> const& tuple)
{
return tuple.getTail();
}
Now we can program the example from Section 25.3.1 on page 582 as follows:
Tuple<int, double, std::string> t1(17, 3.14, "Hello, World!");
auto t2 = popFront(pushBack(t1, true));
std::cout << std::boolalpha << t2 << ’\n’;
which prints
(3.14, Hello, World!, true)
The elements of a tuple can be reversed with another recursive tuple algorithm whose structure follows that of the typelist reverse of Section 24.2.4 on page 557:
tuples/reverse.hpp
// basis case
Tuple<> reverse(Tuple<> const& t)
{
return t;
}
// recursive case
template<typename Head, typename… Tail>
Reverse<Tuple<Head, Tail…>> reverse(Tuple<Head, Tail…> const& t)
{
return pushBack(reverse(t.getTail()), t.getHead());
}
The basis case is trivial, while the recursive case reverses the tail of the list and appends the current head to the reversed list. This means, for example, that
reverse(makeTuple(1, 2.5, std::string("hello")))
will produce a Tuple<string, double, int> with the values string("hello"), 2.5, and 1, respectively.
As with typelists, that way we can now easily provide popBack() by calling popFront() for the temporarily reversed list using PopBack from Section 24.2.4 on page 558:
tuples/popback.hpp
template<typename… Types>
PopBack<Tuple<Types…>>
popBack(Tuple<Types…> const& tuple)
{
return reverse(popFront(reverse(tuple)));
}
The recursive formulation of tuple reversal in the previous section is correct, but it is unnecessarily inefficient at run time. To see the problem, we introduce a simple class that counts the number of times it is copied:2
tuples/copycounter.hpp
template<int N>
struct CopyCounter
{
inline static unsigned numCopies = 0;
CopyCounter() {
}
CopyCounter(CopyCounter const&) {
++numCopies;
}
};
Then, we create and reverse a tuple of CopyCounter instances:
tuples/copycountertest.hpp
void copycountertest()
{
Tuple<CopyCounter<0>, CopyCounter<1>, CopyCounter<2>,
CopyCounter<3>, CopyCounter<4>> copies;
auto reversed = reverse(copies);
std::cout << "0: " << CopyCounter<0>::numCopies << " copies\n";
std::cout << "1: " << CopyCounter<1>::numCopies << " copies\n";
std::cout << "2: " << CopyCounter<2>::numCopies << " copies\n";
std::cout << "3: " << CopyCounter<3>::numCopies << " copies\n";
std::cout << "4: " << CopyCounter<4>::numCopies << " copies\n";
}
This program will output:
0: 5 copies
1: 8 copies
2: 9 copies
3: 8 copies
4: 5 copies
That’s a lot of copies! In the ideal implementation of tuple reverse, each element would only be copied a single time, from the source tuple directly to the correct position in the result tuple. We could achieve this goal with careful use of references, including using references for the types of the intermediate arguments, but doing so complicates our implementation considerably.
To eliminate extraneous copies in tuple reverse, consider how we might implement a one-off tuple reverse operation for a single tuple of known length (say, 5 elements, as in our example). We could simply use makeTuple() and get():
auto reversed = makeTuple(get<4>(copies), get<3>(copies),
get<2>(copies), get<1>(copies),
get<0>(copies));
This program produces the exact output that we want, with a single copy of each tuple element:
0: 1 copies
1: 1 copies
2: 1 copies
3: 1 copies
4: 1 copies
Index lists (also called index sequences; see Section 24.4 on page 570) generalize this notion by capturing the set of tuple indices—in this case 4, 3, 2, 1, 0—into a parameter pack, which allows the sequence of get calls to be produced via a pack expansion. This allows the separation of the index computation, which can be an arbitrarily complicated template metaprogram, from the actual application of that index list, where run-time efficiency is most important. The standard type std::integer_sequence (introduced in C++14) is often used to represent index lists.
To perform tuple reversal with index lists, we first need a representation of index lists. An index list is a typelist containing values meant to be used as indices into either a typelist or a heterogeneous data structure (see Section 24.4 on page 570). For our index list, we will use the Valuelist type developed in Section 24.3 on page 566. The index list corresponding to the tuple reversal example above would be
Valuelist<unsigned, 4, 3, 2, 1, 0>
How do we produce this index list? One approach would be to start by generating an index list counting upward from 0 to N − 1 (inclusive), where N is the length of a tuple, using a simple template metaprogram MakeIndexList:3
tuples/makeindexlist.hpp
// recursive case
template<unsigned N, typename Result = Valuelist<unsigned>>
struct MakeIndexListT
: MakeIndexListT<N-1, PushFront<Result, CTValue<unsigned, N-1>>>
{
};
// basis case
template<typename Result>
struct MakeIndexListT<0, Result>
{
using Type = Result;
};
template<unsigned N>
using MakeIndexList = typename MakeIndexListT<N>::Type;
We can then compose this operation with the typelist Reverse to produce the appropriate index list:
using MyIndexList = Reverse<MakeIndexList<5>>;
// equivalent to Valuelist<unsigned, 4, 3, 2, 1, 0>
To actually perform the reversal, the indices in the index list need to be captured into a nontype parameter pack. This is handled by splitting the implementation of the index-set tuple reverse() algorithm into two parts:
tuples/indexlistreverse.hpp
template<typename… Elements, unsigned… Indices>
auto reverseImpl(Tuple<Elements…> const& t,
Valuelist<unsigned, Indices…>)
{
return makeTuple(get<Indices>(t)…);
}
template<typename… Elements>
auto reverse(Tuple<Elements…> const& t)
{
return reverseImpl(t,
Reverse<MakeIndexList<sizeof…(Elements)>>());
}
In C++11, the return types have to be declared as
-> decltype(makeTuple(get<Indices>(t)…))
and
-> decltype(reverseImpl(t, Reverse<MakeIndexList<sizeof…(Elements)>>()))
The reverseImpl() function template captures the indices from its Valuelist parameter into a parameter pack Indices. It then returns the result of calling makeTuple() with arguments formed by calling get() on the tuple with the set of captured indices.
The reverse() algorithm itself merely forms the appropriate index set, as discussed earlier, and provides that to the reverseImpl algorithm. The indices are manipulated as a template metaprogram and therefore produce no run-time code. The only run-time code is in reverseImpl, which uses makeTuple() to construct the resulting tuple in one step and therefore copies the tuple elements only a single time.
The reverseImpl() function template used in the previous section to form the reversed tuple actually contains no code specific to the reverse() operation. Rather, it simply selects a particular set of indices from an existing tuple and uses them to form a new tuple. reverse() provides a reversed set of indices, but many algorithms can build on this core tuple select() algorithm:4
tuples/select.hpp
template<typename… Elements, unsigned… Indices>
auto select(Tuple<Elements…> const& t,
Valuelist<unsigned, Indices…>)
{
return makeTuple(get<Indices>(t)…);
}
One simple algorithm that builds on select() is a tuple “splat” operation, which takes a single element in a tuple and replicates it to create another tuple with some number of copies of that element. For example:
Tuple<int, double, std::string> t1(42, 7.7, "hello"};
auto a = splat<1, 4>(t);
std::cout << a << ’\n’;
would produce a Tuple<double, double, double, double> where each of the values is a copy of get<1>(t), so it will print
(7.7, 7.7, 7.7, 7.7)
Given a metaprogram to produce a “replicated” index set consisting of N copies of the value I, splat() is a direct application of select():5
tuples/splat.hpp
template<unsigned I, unsigned N, typename IndexList = Valuelist<unsigned>>
class ReplicatedIndexListT;
template<unsigned I, unsigned N, unsigned… Indices>
class ReplicatedIndexListT<I, N, Valuelist<unsigned, Indices…>>
: public ReplicatedIndexListT<I, N-1,
Valuelist<unsigned, Indices…, I>> {
};
template<unsigned I, unsigned… Indices>
class ReplicatedIndexListT<I, 0, Valuelist<unsigned, Indices…>> {
public:
using Type = Valuelist<unsigned, Indices…>;
};
template<unsigned I, unsigned N>
using ReplicatedIndexList = typename ReplicatedIndexListT<I, N>::Type;
template<unsigned I, unsigned N, typename… Elements>
auto splat(Tuple<Elements…> const& t)
{
return select(t, ReplicatedIndexList<I, N>());
}
Even complicated tuple algorithms can also be implemented in terms of a template metaprogram on the index list followed by an application of select(). For example, we can use the insertion sort developed in Section 24.2.7 on page 563 to sort a tuple based on the sizes of the element types. Given such a sort() function, which accepts a template metafunction comparing tuple element types as the comparison operation, we could sort tuple elements by size with code like the following:
#include <complex>
template<typename T, typename U>
class SmallerThanT
{
public:
static constexpr bool value = sizeof(T) < sizeof(U);
};
void testTupleSort()
{
auto T1 = makeTuple(17LL, std::complex<double>(42,77), ’c’, 42, 7.7);
std::cout << t1 << ’\n’;
auto T2 = sort<SmallerThanT>(t1); // t2 is Tuple<int, long, std::string>
std::cout << "sorted by size: " << t2 << ’\n’;
}
The output might, for example, be as follows:6
(17, (42,77), c, 42, 7.7)
sorted by size: (c, 42, 7.7, 17, (42,77))
The actual sort() implementation involves the use of InsertionSort with a tuple select():7
tuples/tuplesort.hpp
// metafunction wrapper that compares the elements in a tuple:
template<typename List, template<typename T, typename U> class F>
class MetafunOfNthElementT {
public:
template<typename T, typename U> class Apply;
template<unsigned N, unsigned M>
class Apply<CTValue<unsigned, M>, CTValue<unsigned, N>>
: public F<NthElement<List, M>, NthElement<List, N>> { };
};
// sort a tuple based on comparing the element types:
template<template<typename T, typename U> class Compare,
typename… Elements>
auto sort(Tuple<Elements…> const& t)
{
return select(t,
InsertionSort<MakeIndexList<sizeof…(Elements)>,
MetafunOfNthElementT<
Tuple<Elements…>,
Compare>::template Apply>());
}
Look carefully at the use of InsertionSort: The actual typelist to be sorted is a list of indices into the typelist, constructed with MakeIndexList<>. Therefore, the result of the insertion sort is a set of indices into the tuple, which is then provided to select(). However, because the InsertionSort is operating on indices, it expects its comparison operation to compare two indices. The principle is easier to understand when considering a sort of the indices of a std::vector, as in the following (non-metaprogramming) example:
tuples/indexsort.cpp
#include <vector>
#include <algorithm>
#include <string>
int main()
{
std::vector<std::string> strings = {"banana", "apple", "cherry"};
std::vector<unsigned> indices = { 0, 1, 2 };
std::sort(indices.begin(), indices.end(),
[&strings](unsigned i, unsigned j) {
return strings[i] < strings[j];
});
}
Here, indices contains indices into the vector strings. The sort() operation sorts the actual indices, so the lambda provided as the comparison operation accepts two unsigned values (rather than string values). However, the body of the lambda uses those unsigned values as indices into the strings vector, so the ordering is actually according to the contents of strings. At the end of the sort, indices provides indices into strings, sorted based on the values in strings.
Our use of InsertionSort for the tuple sort() employs the same approach. The adapter template MetafunOfNthElementT provides a template metafunction (its nested Apply) that accepts two indices (CTValue specializations) and uses NthElement to extract the corresponding elements from its Typelist argument. In a sense, the member template Apply has “captured” the typelist provided to its enclosing template (MetafunOfNthElementT) in the same way that the lambda captured the strings vector from its enclosing scope. Apply then forwards the extracted element types to the underlying metafunction F, completing the adaptation.
Note that all of the computation for the sort is performed at compile time, and the resulting tuple is formed directly, with no extraneous copying of values at run time.
Tuples are useful for storing a set of related values together into a single value, regardless of what types or how many of those related values there are. At some point, it may be necessary to unpack such a tuple, for example, to pass its elements as separate arguments to a function. As a simple example, we may want to take a tuple and pass its elements to the variadic print() operation described in Section 12.4 on page 200:
Tuple<std::string, char const*, int, char> t("Pi", "is roughly",
3, ’\n’);
print(t…); //ERROR: cannot expand a tuple; it isn’t a parameter pack
As noted in the example, the “obvious” attempt to unpack a tuple will not succeed, because it is not a parameter pack. We can achieve the same means using an index list. The following function template apply() accepts a function and a tuple, then calls the function with the unpacked tuple elements:
tuples/apply.hpp
template<typename F, typename… Elements, unsigned… Indices>
auto applyImpl(F f, Tuple<Elements…> const& t,
Valuelist<unsigned, Indices…>)
->decltype(f(get<Indices>(t)…))
{
return f(get<Indices>(t)…);
}
template<typename F, typename… Elements,
unsigned N = sizeof…(Elements)>
auto apply(F f, Tuple<Elements…> const& t)
->decltype(applyImpl(f, t, MakeIndexList<N>()))
{
return applyImpl(f, t, MakeIndexList<N>());
}
The applyImpl() function template takes a given index list and uses it to expand the elements of a tuple into the argument list for its function object argument f. The user-facing apply() is responsible only for constructing the initial index list. Together, they allow us to expand a tuple into the arguments of print():
Tuple<std::string, char const*, int, char> t("Pi", "is roughly",
3, ’\n’);
apply(print, t); //OK: prints Pi is roughly 3
C++17 provides a similar function that works for any tuple-like type.
A tuple is a fundamental heterogeneous container with a large number of potential uses. As such, it is worthwhile to consider what can be done to optimize the use of tuples both at run time (storage, execution time) and at compile time (number of templates instantiations). This section discusses a few specific optimizations to our Tuple implementation.
Our formulation for Tuple storage uses more storage than is strictly necessary. One problem is that the tail member will eventually be an empty tuple, because every nonempty tuple terminates with an empty tuple, and data members must always have at least one byte of storage.
To improve Tuple’s storage efficiency, we can apply the empty base class optimization (EBCO) discussed in Section 21.1 on page 489 by inheriting from the tail tuple rather than making it a member. For example:
tuples/tuplestorage1.hpp
// recursive case:
template<typename Head, typename… Tail>
class Tuple<Head, Tail…> : private Tuple<Tail…>
{
private:
Head head;
public:
Head& getHead() { return head; }
Head const& getHead() const { return head; }
Tuple<Tail…>& getTail() { return *this; }
Tuple<Tail…> const& getTail() const { return *this; }
};
This is the same approach we took with BaseMemberPair in Section 21.1.2 on page 494. Unfortunately, it has the practical side effect of reversing the order in which the tuple elements are initialized in constructors. Previously, because the head member preceded the tail member, the head would be initialized first. In this new formulation of Tuple storage, the tail is in a base class, so it will be initialized before the member head.8
This problem can be addressed by sinking the head member into its own base class that precedes the tail in the base class list. A direct implementation of this would introduce a TupleElt template that is used to wrap each element type so that Tuple can inherit from it:
template<typename... Types>
class Tuple;
template<typename T>
class TupleElt
{
T value;
public:
TupleElt() = default;
template<typename U>
TupleElt(U&& other) : value(std::forward<U>(other) { }
T& get() { return value; }
T const& get() const { return value; }
};
// recursive case:
template<typename Head, typename... Tail>
class Tuple<Head, Tail...>
: private TupleElt<Head>, private Tuple<Tail...>
{
public:
Head& getHead() {
// potentially ambiguous
return static_cast<TupleElt<Head> *>(this)->get();
}
Head const& getHead() const {
// potentially ambiguous
return static_cast<TupleElt<Head> const*>(this)->get();
}
Tuple<Tail...>& getTail() { return *this; }
Tuple<Tail...> const& getTail() const { return *this; }
};
// basis case:
template<>
class Tuple<> {
// no storage required
};
While this approach has solved the initialization-ordering problem, it has introduced a new (worse) problem: We can no longer extract elements from a tuple that has two elements of the same type, such as Tuple<int, int>, because the derived-to-base conversion from a tuple to TupleElt of that type (e.g., TupleElt<int>) will be ambiguous.
To break the ambiguity, we need to ensure that each TupleElt base class is unique within a given Tuple. One approach is to encode the “height” of this value within its tuple, that is, the length of the tail tuple. The last element in the tuple will be stored with height 0, the next-to-last-element will be stored with height 1, and so on:9
tuples/tupleelt1.hpp
template<unsigned Height, typename T>
class TupleElt {
T value;
public:
TupleElt() = default;
template<typename U>
TupleElt(U&& other) : value(std::forward<U>(other)) { }
T& get() { return value; }
T const& get() const { return value; }
};
With this solution, we can produce a Tuple that applies the EBCO while maintaining initialization order and support for multiple elements of the same type:
tuples/tuplestorage3.hpp
template<typename... Types>
class Tuple;
// recursive case:
template<typename Head, typename... Tail>
class Tuple<Head, Tail...>
: private TupleElt<sizeof...(Tail), Head>, private Tuple<Tail...>
{
using HeadElt = TupleElt<sizeof...(Tail), Head>;
public:
Head& getHead() {
return static_cast<HeadElt *>(this)->get();
}
Head const& getHead() const {
return static_cast<HeadElt const*>(this)->get();
}
Tuple<Tail...>& getTail() { return *this; }
Tuple<Tail...> const& getTail() const { return *this; }
};
// basis case:
template<>
class Tuple<> {
// no storage required
};
With this implementation, the following program:
tuples/compressedtuple1.cpp
#include <algorithm>
#include "tupleelt1.hpp"
#include "tuplestorage3.hpp"
#include <iostream>
struct A {
A() {
std::cout << "A()" << ’\n’;
}
};
struct B {
B() {
std::cout << "B()" << ’\n’;
}
};
int main()
{
Tuple<A, char, A, char, B> t1;
std::cout << sizeof(t1) << " bytes" << ’\n’;
}
prints
A()
A()
B()
5 bytes
The EBCO has eliminated one byte (for the empty tuple, Tuple<>). However, note that both A and B are empty classes, which hints at one more opportunity for applying the EBCO in Tuple. TupleElt can be extended slightly to inherit from the element type when it is safe to do so, without requiring changes to Tuple:
tuples/tupleelt2.hpp
#include <type_traits>
template<unsigned Height, typename T,
bool = std::is_class<T>::value && !std::is_final<T>::value>
class TupleElt;
template<unsigned Height, typename T>
class TupleElt<Height, T, false>
{
T value;
public:
TupleElt() = default;
template<typename U>
TupleElt(U&& other) : value(std::forward<U>(other)) { }
T& get() { return value; }
T const& get() const { return value; }
};
template<unsigned Height, typename T>
class TupleElt<Height, T, true> : private T
{
public:
TupleElt() = default;
template<typename U>
TupleElt(U&& other) : T(std::forward<U>(other)) { }
T& get() { return *this; }
T const& get() const { return *this; }
};
When TupleElt is provided with a non-final class, it inherits from the class privately to allow the EBCO to apply to the stored value, too. With this change, the previous program now prints
A()
A()
B()
2 bytes
The get() operation is extremely common when working with tuples, but it’s recursive implementation requires a linear number of template instantiations that can affect compile time. Fortunately, the EBCO optimizations introduced in the previous section have enabled a more efficient implementation of get that we will describe here.
The key insight is that template argument deduction (Chapter 15) deduces template arguments for a base class when matching a parameter (of the base class type) to an argument (of the derived class type). Thus, if we can compute the height H of the element we wish to extract, we can rely on the conversion from the Tuple specialization to TupleElt<H, T> (where T is deduced) to extract that element without manually walking through all of the indices:
tuples/constantget.hpp
template<unsigned H, typename T>
T& getHeight(TupleElt<H,T>& te)
{
return te.get();
}
template<typename... Types>
class Tuple;
template<unsigned I, typename... Elements>
auto get(Tuple<Elements...>& t)
-> decltype(getHeight<sizeof...(Elements)-I-1>(t))
{
return getHeight<sizeof...(Elements)-I-1>(t);
}
Because get<I>(t) receives the index I of the desired element (which counts from the beginning of the tuple) while the tuple’s actual storage is in terms of height H (which counts from the end of the tuple), we compute H from I. Template argument deduction for the call to getHeight() performs the actual search: The height H is fixed because it is explicitly provided in the call, so only one TupleElt base class will match, from which the type T will be deduced. Note that getHeight() must be declared a friend of Tuple to allow the conversion to the private base class. For example:
// inside the recursive case for class template Tuple:
template<unsigned I, typename… Elements>
friend auto get(Tuple<Elements…>& t)
-> decltype(getHeight<sizeof…(Elements)-I-1>(t));
Note that this implementation requires only a constant number of template instantiations, because we have offloaded the hard work of matching up the index to the compiler’s template argument deduction engine.
In principle, it is also possible to define an operator[] to access the elements of a tuple, similarly to the way std::vector defines operator[].10 However, unlike std::vector, a tuple’s elements can each have a different type, so a tuple’s operator[] must be a template where the result type differs depending on the index of the element. That, in turn, requires each index to have a different type, so the index’s type can be used to determine the element type.
The class template CTValue, introduced in Section 24.3 on page 566, allows us to encode the numeric index within a type. We can use this to define a subscript operator as a member of Tuple:
template<typename T, T Index>
auto& operator[](CTValue<T, Index>) {
return get<Index>(*this);
}
Here, we use the value of the passed index within the type of the CTValue argument to make a corresponding get<>() call.
Now we can use this class as follows:
auto t = makeTuple(0, ’1’, 2.2f, std::string{"hello"});
auto a = t[CTValue<unsigned, 2>{}];
auto b = t[CTValue<unsigned, 3>{}];
a and b will be initialized by the type and value of the third and fourth values in the Tuple t.
To make the usage of constant indices more convenient, we can implement the literal operator with constexpr to compute the numeric compile-time literals directly from ordinary literals with the suffix _c:
tuples/literals.hpp
#include "ctvalue.hpp"
#include <cassert>
#include <cstddef>
// convert single char to corresponding int value at compile time:
constexpr int toInt(char c) {
// hexadecimal letters:
if (c >= ’A’ && c <= ’F’) {
return static_cast<int>(c) - static_cast<int>(’A’) + 10;
}
if (c >= ’a’ && c <= ’f’) {
return static_cast<int>(c) - static_cast<int>(’a’) + 10;
}
// other (disable ’.’ for floating-point literals):
assert(c >= ’0’ && c <= ’9’);
return static_cast<int>(c) - static_cast<int>(’0’);
}
// parse array of chars to corresponding int value at compile time:
template<std::size_t N>
constexpr int parseInt(char const (&arr)[N]) {
int base = 10; // to handle base (default: decimal)
int offset = 0; // to skip prefixes like 0x
if (N > 2 && arr[0] == ’0’) {
switch (arr[1]) {
case ’x’: //prefix 0x or 0X, so hexadecimal
case ’X’:
base = 16;
offset = 2;
break;
case ’b’: //prefix 0b or 0B (since C++14), so binary
case ’B’:
base = 2;
offset = 2;
break;
default: //prefix 0, so octal
base = 8;
offset = 1;
break;
}
}
// iterate over all digits and compute resulting value:
int value = 0;
int multiplier = 1;
for (std::size_t i = 0; i < N - offset; ++i) {
if (arr[N-1-i] != ’\’’) { //ignore separating single quotes (e.g. in 1’000)
value += toInt(arr[N-1-i]) * multiplier;
multiplier *= base;
}
}
return value;
}
// literal operator: parse integral literals with suffix _c as sequence of chars:
template<char… cs>
constexpr auto operator"" _c() {
return CTValue<int, parseInt<sizeof…(cs)>({cs…})>{};
}
Here we take the advantage of the fact that, for numeric literals, we can use the literal operator to deduce each character of the literal as its own template parameter (see Section 15.5.1 on page 277 for details). We pass the characters to a constexpr helper function parseInt() that computes the value of the character sequence at compile time and yields it as CTValue. For example:
• 42_c yields CTValue<int,42>
• 0x815_c yields CTValue<int,2069>
• 0b1111’1111_c yields CTValue<int,255>11
Note that the parser does not handle floating-point literals. For them, the assertion results in a compile-time error because it is a run-time feature that can’t be used in compile-time contexts.
With this, we can use tuples as follows:
auto t = makeTuple(0, ’1’, 2.2f, std::string{"hello"});
auto c = t[2_c];
auto d = t[3_c];
This approach is used by Boost.Hana (see [BoostHana]), a metaprogramming library suited for computations on both types and values.
Tuple construction is one of those template applications that appears to have been independently attempted by many programmers. The Boost.Tuple Library [BoostTuple] became one of the most popular formulations of tuples in C++, and eventually grew into the C++11 std::tuple.
Prior to C++11, many tuple implementations were based on the idea of a recursive pair structure; the first edition of this book, [VandevoordeJosuttisTemplates1st], illustrated one such approach via its “recursive duos.” One interesting alternative was developed by Andrei Alexandrescu in [AlexandrescuDesign]. He cleanly separated the list of types from the list of fields in the tuple, using the concept of typelists (as discussed in Chapter 24) as a foundation for tuples.
C++11 brought variadic templates, where parameter packs could clearly capture the list of types for a tuple, eliminating the need for recursive pairs. Pack expansions and the notion of index lists [GregorJarviPowellVariadicTemplates] collapsed recursive template instantiations into simpler, more efficient template instantiations, making tuples more widely practical. Index lists have become so critical to the performance of tuple and type list algorithms, that compilers include an intrinsic alias template such as __make_integer_seq<S, T, N> that expands to S<T, 0, 1, …, N> without additional template instantiations, thereby accelerating applications of std::make_index_sequence and make_integer_sequence.
Tuple is the most widely used heterogeneous container, but it isn’t the only one. The Boost.Fusion Library [BoostFusion] provides other heterogeneous counterparts to common containers, such as heterogeneous list, deque, set, and map. More important, it provides a framework for writing algorithms for heterogeneous collections, using the same kinds of abstractions and terminology as the C++ standard library itself (e.g., iterators, sequences, and containers).
Boost.Hana [BoostHana] takes many of the ideas present in Boost.MPL [BoostMPL] and Boost.Fusion, both designed and implemented long before C++11 came to fruition, and reimagines them with the new C++11 (and C++14) language features. The result is an elegant library that provides powerful, composable components for heterogeneous computation.
1 A complete implementation of get() should also handle non-const and rvalue-reference tuples appropriately.
2 Before C++17, inline static members were not supported. So, we had to initialize numCopies outside the class structure in one translation unit.
3 C++14 provides a similar template make_index_sequence that yields a list of indices of type std::size_t, as well as a more general make_integer_sequence that allows the specific type to be selected.
4 In C++11, the return type has to be declared as -> decltype(makeTuple(get<Indices>(t)…)).
5 In C++11, the return type of splat() has to be declared as -> decltype(return-expression).
6 Note that the resulting order depends on the platform-specific size. For example, the size of a double might be less, the same, or greater than the size of a long long.
7 In C++11, the return type of sort() has to be declared as -> decltype(return-expression).
8 Another practical impact of this change is that the elements of the tuple will end up being stored in reverse order, because base classes are typically stored before members.
9 It would be more intuitive to simply use the index of the tuple element rather than its height. However, that information is not readily available in Tuple, because a given tuple may appear both as a standalone tuple and as the tail of another tuple. A given Tuple does know, however, how many elements are in its own tail.
10 Thanks to Louis Dionne for pointing out the features described in this section.
11 The prefix 0b for binary literals and the single quote character to separate digits are supported since C++14.