Marc Wäckerlin
Für eine libertäre Gesellschaft

C++11 Variadic Templates: Fun with Tuple

April 12, 2016

Views: 3289

To learn the power of the new variadic template parameters, I decided to implement my own tuple class. I know, there is already a tuple Implementation in the C++11 standard library, but it is a cool example anyway, and it is a typical use for variadic templates. Of course, the challenge is to check if I can do it better.

What is a Tuple

A tuple is a fixed size container that contains elements of arbitrary type, where each element in a tuple can have a different type. The simplest form of a tuple is std::pair, a tupel of two elements. The tuple is a generalisation of the pair to contain any number of elements. If you instantiate a pair, you pass the types of the two elements. To store an integer and a string in one pair and write ot to console, you can write:

std::pair<int, string> testpair = {32, "Hello World"};
std::cout<<"first:  "<<teststruct.first<<"\n"
         <<"second: "<<teststruct.second<<"\n";

This is mostly equivalent to:

struct {
  int first;
  string second;
} teststruct = {32, "Hello World"};
std::cout<<"first:  "<<teststruct.first<<"\n"
         <<"second: "<<teststruct.second<<"\n";

A tuple is an extension of pair to contain more than only two values, therefore the access needs to be more generalized than only first and second.

Design Principles

The code is written 2016, so complies to the current standard in C++14, even though it mainly explains a feature of C++11. C++17 features are not yet used. The samples are compilable with GNU C++ Compiler 4.8.1 and higher, but should work with any standard compliant compiler.

One thing that I dislike in the standard tuple implementation is, that access to the tuple elements is done using a global template function std::get<0>(mytuple). According to the C++ philosophy, the object should not be passed as function parameter, but the function should be member of the tuple class, such as mytuple.get<0>(). So this shall be an improvement. If possible, I don’t want to pollute the global namespace with anything but the tuple class, so there should only be one global class declaration and no helper functions.

I’ll try to add an operator[](int), so that the elements can be accessed through mytuple[1] instead of mytuple.get<1>(). The disadvantage of such a subscript operator is, that the element is evaluated at runtime, while get<> as a template function is evaluated at compile time. So the get<> needs less runtime than a flexible operator. But the operator[] access has the advantage, that it is possible use variable indices to access the elements, while get<> must use constants. So both access methods make sense.

Another decision is, that I use the name Tuple to avoid conflict with class std::tuple. For simplicity and to keep the code short, I place using namespace std at the top. Even though it is ugly, it helps to keep the sample code shorter by writing cout and string instead of std::cout and std::string.

I found a blog Variadic templates in C++, but unfortunately not all samples are compilable, and it does not do exactly what I want. Also, I implement a nicer solution that does not need the std::enable_if construct. I build up my approach step by step and I explain every step. Feel free to comment or ask questions.

Basic Approach

First, we need a tuple class to store the values. This I do according to Variadic templates in C++. I create a new file tuple.cxx:

#include <stdexcept>
#include <string>
#include <iostream>
#include <sstream>

using namespace std;

// Place 1

template<typename... Values>
    struct Tuple
{
    // Place 2
};

template<typename Value, typename... MoreValues>
    struct Tuple<Value, MoreValues...>
  : Tuple<MoreValues...>
{
    typedef Tuple<Value, MoreValues...> OwnType;
    typedef Tuple<MoreValues...> ParentType;
    Tuple(Value v, MoreValues... more):
        ParentType(more...),
        value(v) {
    }
    // Place 3
    ParentType& parent() {
      return *dynamic_cast<ParentType*>(this);
    }
    Value value;
};

// Place 4

int main(int, char**) {
  Tuple<int, string, char> atuple(13, "Test", 't');
  // Place 5
  return 0;
}

Compile it using the GNU C++ Compiler with g++ -std=c++1y -o tuple tuple.cxx, it should compile, but if you execute it with ./tuple, nothing happens yet. The comments at Place 1, Place 2, Place 3, Place 4 and Place 5 mark where we will add more code later, so I do not have to include the full code on every step. To start, I use struct with everything public to concentrate on the important points. I’ll fix that in the last step.

There is first a variadic template structure named Tuple, that takes any number of arguments. This Argument list is named Values. The three dots ... indicate that this variable holds any number of arguments, including no argument at all, so this basic structure also allows to take no argument at all. This structure is empty, because it only serves as the top most base class to the next structure. It will be the end of a recursive inheritance chain.

The next structure is a template specialization of the above definition Tuple. That’s why it is declared as Tuple<Value, MoreValues...>: it is the specialisation that takes at least one template argument named Value, plus any number of more arguments in MoreValues, where MoreValues can be empty. This is the structure we work on. The music plays here.

Value just defines the first template type, so that we can handle the first type separately and, i.e. split it off to handle the variadic templates recursively. It is necessary to split off the first argument, not the last, since the variadic argument must be the last argument, it is some kind of an argument list that takes every argument that follows. Because we cannot work with lists of types, it is necessary to split off the first type to handle it.

This structure recursively inherits from the same structure, but without the first argument, named Tuple<MoreValues...>. This goes on recursively until there is no more argument left. Then it ends up by inheriting from the first empty structure above which does not inherit any more and so ends the recursion. To better understand this, I declared a type OwnType that contains the exact type of this structure, and a type ParentType that declares the type of the parent structure that this structure inherits from. Wherever possible, I use these declarations just for better readability.

In the constructor, the first argument, that corresponds to the type of the first template argument is split off and assigned to the member variable value. All the remaining arguments are passed to the parent in the variable more. The last base class is then called with an empty more, so there is no need to write a constructor in the base structure.

Function parent just returns the parent object, which is the actual object converted to the parent structure type ParentType. This way we can recursively get the parent objects. But the top base object has no more parent() function, so accessing it would result in a compile error. Whenever possible, we should catch errors at compile time. Here, this is possible by not defining parent() in the topmost base class.

Next we store the first value of type Value as member value. We can not access the other members stored in more here. The second member is stored as value in the next parent class, the third in the parent’s parent. This is due to the fact, we are using recursive inheritance.

That’s all we need by now. Now we have a flexible storage for any number of object of any type. Let’s instantiate it in the main function: Tuple<int, string, char> atuple(13, "Test", 't'); So we store an integer, a string and a character in one tuple.

The inheritance tree and the structure in memory now look like this:

Access the Values

If we compile and execute the code up to now, nothing happens. So we need to add some output. After // Place 5 add:

  cout<<"atuple = "
      <<atuple.value<<", "
      <<atuple.parent().value<<", "
      <<atuple.parent().parent().value<<"\n";

Recompile and run it, it outputs a line: atuple = 13, Test, t, as expected. Of course this way to access the values is ugly. And moreover, the members parent() and value shall be protected in the final implementation. You can remove the cout now, we don’t need it any more.

Failed: Subscript Operator

I would like to add a subscript operator, so that I can access the i-th element using atuple[i] and it returns the value of the i-th element. This would mean to implement a subscript operator after // Place 3 somehow like:

    boost::any operator[](unsigned i) {
      if (i==0) return value;
      return parent().operator[](--i);
    }

If you start with i>0, then it counts i down recursively and calls the same function on the parent i-times. Finally, when it reaches the base class we are looking for, that means i reached 0, it returns value. There is only one problem: What is boost::any? Unfortunately, the method can return any type, depending on the index, but the index is not known at compile time. So a possible approach is to use an any type. C++17 will probably have one, but now at the time of writing this blog, it is not yet finished. Also, it will be similar to boost::any which has no access to the type. To access the value, you must know the type. So it is very uncomfortable to use. The type of the i-th value can be calculated at compile time (as we will see later in the get<> function), but there is no way to dynamically return a type at runtime. Using boost::any as return type compiles, but is not very useful. If you want to try it, you have to add to the top:

#include <boost/any.hpp>

After // Place 2 add:

      boost::any operator[](unsigned i) {}

Then you can use it in main after // Place 5, e.g. add:

  cout<<"atuple[1] = "<<boost::any_cast<string>(atuple[1])<<"\n";

Here you see the problem: You must know the type and explicitly cast to it. This is not nice, so I drop the idea of writing a subscript operator. If you have a better idea, please leave a comment and let me know.

I suggest you remove what you added in this chapter.

Alternatively: Apply a Functor

Instead of a subscript operator we could add a method to pass a template functor to the tuple, so the correct template instantiation is evaluated for all elements of the tuple and the index can be passed at runtime. A functor is a class that overwrites the function operator. Here we need the function operator that takes an value type as parameter. Let’s write an apply function that takes a functor as template parameter and the index in the function argument. After // Place 3 add:

    template<template<typename> class Function>
        auto apply(int i) {
      if (i==0) return Function<Value>()(value);
      return parent().apply<Function>(--i);
    }

The template in a template class here means, that Function is a class that also takes a template parameter. The parameter that is passed is the type of the value the operator is applied to. So we can pass the structure Out or Stringify as defined below. The call Function<Value>()(value) is two steps in one, with the first parenthesis, a temporary functor object is created and with the second parenthesis containing the value, the functor operator is applied on that temporary object.

As above, if you start with i>0, then it counts i down recursively and calls the same function on the parent i-times. Finally, when it reaches the base class we are looking for, that means i reached 0, it applies the functor on the value.

Before you can test it, add the following lines after // Place 2:

    template<template<typename> class Function>
        auto apply(int)
    {
      throw out_of_range("index to Tuple::apply is out of range");
      return Function<int>()(0); // dummy
    }

Because parent().apply<Function>(--i); is applied recursively at runtime, and range overflows may occur at runtime, the topmost base class must also implement it. If the function is reached in the top most base class, this means that the index is out of range. All that has to be done here is to throw a runtime exception. The return is a dummy, the line is never reached. But returning the correct type is necessary for the compiler to resolve auto and to detect the return type at compile time.

Output One Value

Everything is ready for a functor, so let’s write a template functor that prints the value to the screen for any arbitrary type. After // Place 1 add:

template<typename T> struct Out {
    void operator()(const T& value) {
      cout<<value;
    }
};

Use this functor in the following way, e.g. to print a string, you could write (this is just a sample, don’t add it to tuple.cxx):

Out<string> outs; // create the functor struct to handle string
string text("Hello World");
outs(text); // apply a string means print a string
outs("this is a test"); // apply a text

This is all the required preparation. The function can now be applied as atuple.apply<Out>(i);. After // Place 5 add:

  for (unsigned i: {0, 1, 2}) {
    cout<<"atuple<Out>("<<i<<") -> ";
    atuple.apply<Out>(i);
    cout<<"\n";
  }

This funny for loop is also a new feature in C++, it iterates the unsigned int variable i over the array of values 0, 1 and 2. In C++11, you can specify a C-style array of integer in the form int anArray[] = {-4, 2, 0, 1};. A loop over any type of container can be specified as for (auto var: container). In this for loop, the type of the array is defined by the type of the element iterating variable i, so the array definition needs no type. The loop is equivalent to for (int i(0); i<3; ++i), but it looks nicer.

Convert to String

The above solution is not so nice, because the apply is on a seperate line, not in the stream. But we can write any kind of functor, e.g. one to convert any value to string. Precondition is, that there exists a stream output operator, then we can shift the value to a std::stringstream and this way convert it to a string:

After // Place 1 add:

template<typename T> class Stringify {
  public:
    string operator()(const T& value) {
      std::stringstream ss;
      ss<<value;
      return ss.str();
    }
};

Use it within a stream, after // Place 5 add:

  for (unsigned i: {0, 1, 2}) {
    cout<<"atuple<Stringify>("<<i<<") = "
        <<atuple.apply<Stringify>(i)
        <<"\n";
  }

The Get Method

I saved the best for the last part: The get method, that looks like atuple.get<0>(). This needs a bit more preparation: We need an additional structure to retrieve positional information. Fortunately this structure, I name it Info, can be placed inside the structure Tuple, it does not have to be in the global namespace, But there is a pitfall. This is why I add it first to the global namespace, to show you how that works, then we remove that code and add it inside of the Tuple structure. This way, I can point out the problem and its workaround.

In the Global Namespace

After // Place 1 add a new structure Info to get the type and the value at a specific position in the Tuple, evaluated at compile time:

template<unsigned POS, typename T> struct Info {
    typedef typename Info<POS-1, typename T::ParentType>::Type Type;
    static auto& get(typename T::OwnType& t) {
      return Info<POS-1, typename T::ParentType>::get(t);
    }
};
template<typename T> struct Info<0, T> {
    typedef typename T::ValueType Type;
    static auto& get(typename T::OwnType& t) {
      return t.value;
    }
};

The first is the generic recursive definition, the second is a template specialisation for the final value POS=0. Add a template member function to Tuple to get the value at a specific position, after // Place 3 add:

    typedef Value ValueType;
    template<int POS>
        typename Info<POS, OwnType>::Type& get() {
      return Info<POS, OwnType>::get(*this);
    }

That’s all, now use the new get method, after // Place 5 add:

  cout<<"atuple.get<0>() = "<<atuple.get<0>()<<"\n";
  cout<<"atuple.get<1>() = "<<atuple.get<1>()<<"\n";
  cout<<"atuple.get<2>() = "<<atuple.get<2>()<<"\n";

That’s all, that works, but Info is now in the global namespace and should be moved to the Tuple’s namespace. So, now you can leave the code you added after // Place 5, this will remain the same. But remove the lines you just appended after // Place 1 and after // Place 3.

In the Tuple’s Namespace, 1st Try

In theory, you can just move the structure Info inside of Tuple, after // Place 3 add:

    template<unsigned POS> struct Info {
        typedef typename ParentType::template Info<POS-1>::Type Type;
        static auto& get(OwnType& t) {
          return ParentType::template Info<POS-1>::get(t);
        }
    };
    template<int POS>
        typename Info<POS>::Type& get() {
      return Info<POS>::get(*this);
    }

Then adapt the template specialization by prepending Tuple after // Place 4 add:

template<typename Value, typename... MoreValues> template<>
    struct Tuple<Value, MoreValues...>::Info<0>
{
    typedef Value Type;
    static auto& get(OwnType& t) {
      return t.value;
    }
};

This results in strange error messages, as:

error: invalid explicit specialization before ‘>’ token
error: enclosing class templates are not explicitly specialized
error: template parameters not used in partial specialization:

It is explained on Stack Overflow: A full explicit specialization of an inner, nested class (or method) is not allowed. In the following chapter, I use the workaround of specifying an additional dummy parameter, so that the specialization is not complete.

If you added code after // Place 3 and after // Place 4, then remove it now and continue with the following chapter.

In the Tuple’s Namespace, 2nd Try

It is possible to move the structure Info inside of Tuple by adding a completely useless dummy parameter. This way, the second template is only partially and not fully specified. When the structure Info is used, it does not matter how the second parameter is specified, so just use 0. After // Place 3 add:

    template<unsigned POS, int dummy> struct Info {
        typedef typename ParentType::template Info<POS-1, 0>::Type Type;
        static auto& get(OwnType& t) {
          return ParentType::template Info<POS-1, 0>::get(t);
        }
    };
    template<int POS>
        typename Info<POS, 0>::Type& get() {
      return Info<POS, 0>::get(*this);
    }

Then adapt the template specialization by prepending Tuple. Please note the duplicate template<> declaration for a template class within a template class. After // Place 4 add:

template<typename Value, typename... MoreValues> template<int dummy>
    struct Tuple<Value, MoreValues...>::Info<0, dummy>
{
    typedef Value Type;
    static auto& get(OwnType& t) {
      return t.value;
    }
};

That’s it, this is a complete implementation. Now there is one last point to simplify.

If you added code after // Place 3 and after // Place 4, then remove it now and continue with the following chapter.

In the Tuple’s Namespace, Final Try

Due to the new C++11 feature of auto declaration, the Info structure can be simplified. The return type of the value can be detected by the compiler, so there is no need for finding the correct type at a specific position. It was a good excercise to implement it, but now let’s remove it. After // Place 3 add:

    template<unsigned POS, int dummy> struct Info {
        static auto& get(OwnType& t) {
          return ParentType::template Info<POS-1, 0>::get(t);
        }
    };
    template<int POS> auto& get() {
      return Info<POS, 0>::get(*this);
    }

After // Place 4 add:

template<typename Value, typename... MoreValues> template<int dummy>
    struct Tuple<Value, MoreValues...>::Info<0, dummy>
{
    static auto& get(OwnType& t) {
      return t.value;
    }
};

That’s the simple solution. Now I am quite satisfied with the final result.

tuple.cxx

#include <stdexcept>
#include <string>
#include <iostream>
#include <sstream>

using namespace std;

// Place 1
template<typename T> class Stringify {
  public:
    string operator()(const T& value) {
      std::stringstream ss;
      ss<<value;
      return ss.str();
    }
};

template<typename T> struct Out {
    void operator()(const T& value) {
      cout<<value;
    }
};
template<typename... Values>
    struct Tuple
{
    // Place 2
    template<template<typename> class Function>
        auto apply(int)
    {
      throw out_of_range("index to Tuple::apply is out of range");
      return Function<int>()(0); // dummy
    }
};

template<typename Value, typename... MoreValues>
    struct Tuple<Value, MoreValues...>
  : Tuple<MoreValues...>
{
    typedef Tuple<Value, MoreValues...> OwnType;
    typedef Tuple<MoreValues...> ParentType;
    Tuple(Value v, MoreValues... more):
        ParentType(more...),
        value(v) {
    }
    // Place 3
    template<unsigned POS, int dummy> struct Info {
        static auto& get(OwnType& t) {
          return ParentType::template Info<POS-1, 0>::get(t);
        }
    };
    template<int POS> auto& get() {
      return Info<POS, 0>::get(*this);
    }
    template<template<typename> class Function>
        auto apply(int i) {
      if (i==0) return Function<Value>()(value);
      return parent().apply<Function>(--i);
    }
    ParentType& parent() {
      return *dynamic_cast<ParentType*>(this);
    }
    Value value;
};

// Place 4
template<typename Value, typename... MoreValues> template<int dummy>
    struct Tuple<Value, MoreValues...>::Info<0, dummy>
{
    static auto& get(OwnType& t) {
      return t.value;
    }
};

int main(int, char**) {
  Tuple<int, string, char> atuple(13, "Test", 't');
  // Place 5
  cout<<"atuple.get<0>() = "<<atuple.get<0>()<<"\n";
  cout<<"atuple.get<1>() = "<<atuple.get<1>()<<"\n";
  cout<<"atuple.get<2>() = "<<atuple.get<2>()<<"\n";
  for (unsigned i: {0, 1, 2}) {
    cout<<"atuple<Out>("<<i<<") -> ";
    atuple.apply<Out>(i);
    cout<<"\n";
  }
  for (unsigned i: {0, 1, 2}) {
    cout<<"atuple<Stringify>("<<i<<") = "
        <<atuple.apply<Stringify>(i)
        <<"\n";
  }
  cout<<"atuple = "
      <<atuple.value<<", "
      <<atuple.parent().value<<", "
      <<atuple.parent().parent().value<<"\n";
  return 0;
}

Last Cleanup

#include <stdexcept>
#include <string>
#include <iostream>
#include <sstream>

using namespace std;

template<typename T> class Out {
  public:
    void operator()(const T& value) {
      cout<<value;
    }
};

template<typename T> class Stringify {
  public:
    string operator()(const T& value) {
      std::stringstream ss;
      ss<<value;
      return ss.str();
    }
};
template<typename... Values>
    class Tuple
{
  public:
    template<template<typename> class Function>
        auto apply(int)
    {
      throw out_of_range("index to Tuple::apply is out of range");
      return Function<int>()(0); // dummy
    }
};

template<typename Value, typename... MoreValues>
    class Tuple<Value, MoreValues...>
  : public Tuple<MoreValues...>
{
  public:
    Tuple(Value v, MoreValues... more):
        ParentType(more...),
        value(v) {
    }
    template<int POS> auto& get() {
      return Info<POS, 0>::get(*this);
    }
    template<template<typename> class Function>
        auto apply(int i) {
      if (i==0) return Function<Value>()(value);
      return parent().apply<Function>(--i);
    }
  protected:
    typedef Tuple<Value, MoreValues...> OwnType;
    typedef Tuple<MoreValues...> ParentType;
    template<unsigned POS, int dummy> class Info {
      public:
        static auto& get(OwnType& t) {
          return ParentType::template Info<POS-1, 0>::get(t);
        }
    };
    ParentType& parent() {
      return *dynamic_cast<ParentType*>(this);
    }
    Value value;
};

template<typename Value, typename... MoreValues> template<int dummy>
    class Tuple<Value, MoreValues...>::Info<0, dummy>
{
  public:
    static auto& get(OwnType& t) {
      return t.value;
    }
};

int main(int, char**) {
  Tuple<int, string, char> atuple(13, "Test", 't');
  cout<<"atuple.get<0>() = "<<atuple.get<0>()<<"\n";
  cout<<"atuple.get<1>() = "<<atuple.get<1>()<<"\n";
  cout<<"atuple.get<2>() = "<<atuple.get<2>()<<"\n";
  for (unsigned i: {0, 1, 2}) {
    cout<<"atuple<Out>("<<i<<") -> ";
    atuple.apply<Out>(i);
    cout<<"\n";
  }
  for (unsigned i: {0, 1, 2}) {
    cout<<"atuple<Stringify>("<<i<<") = "
        <<atuple.apply<Stringify>(i)
        <<"\n";
  }
  return 0;
}

Compile and Run

user@host:~/test$ g++ -std=c++1y -o tuple tuple.cxx
user@host:~/test$ ./tuple
user@host:~/test$ g++ --version
g++-4.8.real (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4
Copyright (C) 2013 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Output

atuple.get<0>() = 13
atuple.get<1>() = Test
atuple.get<2>() = t
atuple<Out>(0) -> 13
atuple<Out>(1) -> Test
atuple<Out>(2) -> t

Stream Operator

It would be nice to have a stream operator. Here we are:

template<typename... MoreValues>
    ostream& operator<<(ostream& o, Tuple<MoreValues...>& t);

template<typename Value, typename... MoreValues>
    ostream& operator<<(ostream& o, Tuple<Value, MoreValues...>& t) {
  o<<t.template get<0>();
  if (sizeof...(MoreValues)>0) {
    o<<", "<<dynamic_cast<Tuple<MoreValues...>&>(t);
  }
  return o;
}

Use it:

  cout<<"atuple = "<<atuple<<'\n';

2 Years Later

Two years later, 2018, the code does not compile anymore in g++ 7.3.0. It works again, when I remove the apply function, which wasn’t a good idea anyway:

#include <stdexcept>
#include <string>
#include <iostream>
#include <sstream>

template<typename... Values> class Tuple {
};

template<typename Value, typename... MoreValues>
    class Tuple<Value, MoreValues...>: public Tuple<MoreValues...> {
  public:
    Tuple(Value v, MoreValues... more):
        ParentType(more...),
        value(v) {
    }
    template<int POS> auto& get() {
      return Info<POS, 0>::get(*this);
    }
  protected:
    typedef Tuple<Value, MoreValues...> OwnType;
    typedef Tuple<MoreValues...> ParentType;
    template<unsigned POS, int dummy> class Info {
      public:
        static auto& get(OwnType& t) {
          return ParentType::template Info<POS-1, 0>::get(t);
        }
    };
    ParentType& parent() {
      return *dynamic_cast<ParentType*>(this);
    }
    Value value;
};

template<typename Value, typename... MoreValues> template<int dummy>
    class Tuple<Value, MoreValues...>::Info<0, dummy> {
  public:
    static auto& get(OwnType& t) {
      return t.value;
    }
};

int main(int, char**) {
  Tuple<int, std::string, char> atuple(13, "Test", 't');
  std::cout<<"atuple.get<0>() = "<<atuple.get<0>()<<"\n";
  std::cout<<"atuple.get<1>() = "<<atuple.get<1>()<<"\n";
  std::cout<<"atuple.get<2>() = "<<atuple.get<2>()<<"\n";
  return 0;
}

For another example, that uses containment instead if inheritance, please see my new blog post on the evolving C++ standard.

comments title