Tuple implementation via variadic templates

I took a look at the std tuple header file (which I believe is authored/maintained by Stephan T. Lavavej of the VC++ team – original code by P.J. Plauger) and it would be an understatement to say that my head was spinning for a while just going through the code. To understand better how it was implemented, I simplified it down and extracted out the minimal code required to instantiate a tuple and to access its values (and be able to both read and write). It helped me understand how variadic templates are typically used with recursive expansion to significantly reduce lines of code when designing template classes.

// tuple 
template<class... _Types> class tuple;

// empty tuple
template<> class tuple<> {};

// recursive tuple definition
template<class _This,
  class... _Rest>
  class tuple<_This, _Rest...>
  : private tuple<_Rest...>
{ 
public:
  _This _Myfirst;
};

The recursive specialization uses inheritance so that we’ll end up with members for every argument type specified for the tuple. To access a tuple value, a tuple_element class is used as a sort of accessor class.

// tuple_element
template<size_t _Index, class _Tuple> struct tuple_element;

// select first element
template<class _This, class... _Rest>
struct tuple_element<0, tuple<_This, _Rest...>>
{
  typedef _This& type;
  typedef tuple<_This, _Rest...> _Ttype;
};

// recursive tuple_element definition
template <size_t _Index, class _This, class... _Rest>
struct tuple_element<_Index, tuple<_This, _Rest...>>
  : public tuple_element<_Index - 1, tuple<_Rest...> >
{ 
};

Again, recursive inheritance is used, and the 0th case is specialized as well. Notice the two typedefs, one of them is a reference to the type of the value, and the other represents the tuple with the same arguments as the tuple_element. So, given an _Index value, we can retrieve the type of the tuple and the type of the tuple value for that recursion level. This is used in the get method.

// get reference to _Index element of tuple
template<size_t _Index, class... _Types> inline
  typename tuple_element<_Index, tuple<_Types...>>::type
  get(tuple<_Types...>& _Tuple)
{
  typedef typename tuple_element<_Index, tuple<_Types...>>::_Ttype _Ttype;
  return (((_Ttype&) _Tuple)._Myfirst);
}

Notice the return type, it uses the type typedef defined above. Similarly, the tuple is cast to the _TType typedef defined above and then we access the _Myfirst member (which represents the value). Now you can write code as follows.

tuple<int, char> t1;
get<0>(t1) = 959;
get<1>(t1) = 'A';

auto v1 = get<0>(t1);
auto v2 = get<1>(t1);

Now, this goes without saying, but I’ll say it just to be sure – but this is just for demonstration. Do not use this in production code, instead use std::tuple which does all this and lots more (there’s a reason it’s 800 lines long).

Advertisements

10 thoughts on “Tuple implementation via variadic templates

  1. Given that you’re not implementing the C++ Standard Library 😉 it’s not a good idea to use leading underscores: http://stackoverflow.com/questions/228783/what-are-the-rules-about-using-an-underscore-in-a-c-identifier

    Even if this is purely for illustrative purposes, it’s a good habit to avoid illegal constructs in general.

    BTW, I’ve found the following to be quite informative on the subject matter:
    http://mitchnull.blogspot.com/2012/06/c11-tuple-implementation-details-part-1.html

  2. Thanks – and I accept that. I was merely re-using the existing code, but it was still a mistake. 🙂

    And thank you for that link, looks like an interesting read to me.

  3. PJP wrote all of VC’s , with one exception. Ordinarily I just fix bugs, but I rewrote tuple_cat() from scratch to be non-runtime-recursive.

    Note that STL maintainers, in addition to having the right and responsibility to use _Ugly names, often have to do unusual things in the name of extreme genericity or other concerns. So, I want to emphasize: you should not unthinkingly imitate the STL’s implementation.

  4. You should have demonstrated the non recursive implementation as well. It gives (slightly) better results (notably layouts the members in the order they’re given). There’s a talk available online done at the last boost con er… C++ Now.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s