More on STL Tuples - Implementation using Variadic Templates

My previous post on STL tuples mentioned that they can be implemented using variadic templates. This post looks at the VC++ 2013 tuple implementation to see how this has been achieved. Doing so gives a great example of how powerful variadic templates can be.

(Note, in order to keep the code below clean I've cut out some details, e.g. template parameters with defaults that are used. These extras have no affect on what I'm explaining and clutter up the code snippets. If you want to see these details go look in <tuple>.)

Simple class definition for a tuple in VC++ 2013

Firstly, there is the following class definition for tuple:

template<>
class tuple<>
{
public:
  tuple()
  {
  }
  // more implementation

This is a template class with no template parameters, and a constructor that takes no parameters. You could invoke this constructor with:

tuple<> temp;

but I can't think of a reason to ever do that.

Variadic template class definition for the tuple

There is then another tuple definition that uses variadic templates:

template<class T, class... _Rest>
class tuple<T, _Rest...> : private tuple<_Rest...>
{ // recursive tuple definition
public:
  _Tuple_val<T> _Myfirst;
  tuple<_Rest...> _Get_rest();

To understand this you'll need to know that the ... notation can be read as "collection of". Also, if you're not familiar with the class keyword inside the template angle brackets, it's equivalent to typename in this context.

Now you can begin to parse the above code. This definition of tuple is templated for a parameter of type T and a collection of types referred to as _Rest. It privately inherits from a tuple that is templated for this collection of types. The comment "recursive tuple definition" is not mine, it's taken from the VC++ 2013 STL code. It explains that when using the above definition the compiler will recursively create new tuple definitions for a shrinking list of types until that list is empty, at which point it will use the original tuple definition, which is templated for zero types.

To explain with an example, consider you wish to use tuple<double, long, std::string>. The compiler will first create a class definition of tuple that is templated for type double and the collection of types long and std::string. This class will inherit from another class definition of tuple that is templated for type long  and the collection of types std::string. This class will inherit from a tuple class that is templated for type std::string and inherits from the original tuple class definition that is templated for zero types.

Construction and Implementation details

Look at the two members that I've picked out. _Tuple_val<T> is a helper class and it's used to store a value of type T. _Get_rest() is a member function that returns a reference to the base class. So, from the previous example, in the most derived class, which is templated for type double and the collection of types long and std::string, _Myfirst refers to the value of the double and _Get_rest() returns a reference to its base class i.e. the class that is templated for a long  and the collection of types std::string.

Now look at the constructor that is used when many types are passed in:

explicit tuple(T&& _This_arg, _Rest&&... _Rest_arg)
: _Myfirst(_This_arg), tuple<_Rest...>(_Rest_arg...)
{
}

As you can see, the constructor simply initializes the _Myfirst variable with the corresponding value _This_arg, and the rest of the arguments are passed to the base class, which is by definition a tuple templated for the types of those arguments.

Hopefully this example gives a good idea of the power of variadic templates. I'll follow up with another post on some more VC++ 2013 tuple implementation details including how they are compared.