How does std::get() work with std::tuple?

Question

After trying to make a std::get<N>(std::tuple) method myself, I'm not so sure how it's implemented by compilers. I know std::tuple has a constructor like this:

tuple(Args&&... args);

But what exactly is args... assigned to? I think this is useful in order to know how std::get() works, because the arguments need to be placed somewhere in order to access them.

Dangle

Have you looked at boost::get and boost::tuple? How about the header file your std::get is implemented in? It isn't easy to read, but usually these are implemented as in C++. (the standard does not require that the standard library is implemented in C++) – Mini

Answer 1

Here is a crude toy implementation of a tuple-like class.

First, some metaprogramming boilerplate, to represent a sequence of integers:

template<int...> struct seq {};
template<int max, int... s> struct make_seq:make_seq< max-1, max-1, s... > {};
template<int... s> struct make_seq<0, s...> {
  typedef seq<s...> type;
};
template<int max> using MakeSeq = typename make_seq<max>::type;

Next, the tagged class that actually stores the data:

template<int x, typename Arg>
struct foo_storage {
  Arg data;
};

This tagging technique is a common pattern whenever we want to associate data with some tag at compile time (in this case, an integer). The tag (an int here) isn't used anywhere in the storage usually, it is just used to tag the storage.

foo_helper unpacks a sequence and a set of arguments into a bunch of foo_storage, and inherits from them in a linear fashion. This is a pretty common pattern -- if you are doing this a lot, you end up creating metaprogramming tools that do this for you:

template<typename Seq, typename... Args>
struct foo_helper {};
template<int s0, int... s, typename A0, typename... Args>
struct foo_helper<seq<s0, s...>, A0, Args...>:
  foo_storage<s0, A0>,
  foo_helper<seq<s...>, Args...>
{};

My crude tuple type, foo, creates a package of a sequence of indexes and the args, and passes it to the helper above. The helper then creates a bunch of tagged data holding parent classes:

template<typename... Args>
struct foo: foo_helper< MakeSeq<sizeof...(Args)>, Args... > {};

I removed everything from the body of foo, because it isn't needed to implement get.

get is pretty simple: we take the storage type (not the tuple type), and the explicit template argument N disambiguates which of the foo_storage<n, T> we are going to access. Now that we have the storage type, we simply return the data field:

template<int N, typename T>
T& get( foo_storage<N, T>& f )
 { return f.data; }
template<int N, typename T>
T const& get( foo_storage<N, T> const& f )
 { return f.data; }

We are using the overloading mechanisms of the C++ langauge to do the heavy lifting. When you call a function with a class instance, that instance as each of the parent classes are gone over to see if any of them can be made to match. With the N fixed, there is only one parent class that is a valid argument, so parent class (and hence T) is deduced automatically.

And finally, some basic test code:

#include <iostream>

int main() {
  foo<int, double> f;
  get<0>( f ) = 7;
  get<1>( f ) = 3.14;
  std::cout << get<0>(f) << "," << get<1>(f) << "\n";
}

Mini

This can be massively improved. See for example this toy implementation I wrote some time ago. It relies on derived-to-base conversion, and forcing the right one by specifying part of the base-type (namely, the index). – Nilsson

@Nilsson fixed, removing the int(*)[N] hack. – Mini

Answer 2

I had this same question and researched into it. Though libraries are free to implement a tuple template however they choose, the GNU ISO C++ library uses a recursive inheritance technique.

Basically, you start with the definition of a length 1 tuple say...

( elem1 )

Then a length 2 tuple is defined as...

( elem1, ( elem2 ) )

a length 3 as...

( elem1, ( elem2, ( elem3 ) ) )

and so on.

Every longer length tuple is defined as a new template class derived from a base template class category that is one unit shorter.

In the implementation, the template classes have a leading index tag. The index tag basically tells the compiler how many pairs of parenthesis surround it. The full tuple has index 0 and contains all the higher index tuples that make up the inner nests.

In the implementation there are two specializations.

Nested tuple elements that are to the left of some other element are all derived from both a head and a tail. The head contains that data at that index, and the tail is the nest containing all the elements to its right. In summary, every nested class inherits everything to its right in the list.

The far right nested element, OTOH, is the degenerate case that requires its own specialization. Unlike the others, it has only a head class parent, rather than both a head and a tail parent class.

I made a diagram of the inheritance structure. Within each nest, only the head parent class contains data directly. Every other class simply inherits it ( because it inherits the head class ).

Technique Overview

List Format: 

    { 
        { Type_0, Value_0 }, 
        { Type_1, Value_1 }, 
        { Type_2, Value_2 }, 
        ... 
        { Type_N, Value_N } 
    }

Nested Inheritance Format: 

    NestedTuple < 0, Types < Type_0, Type_1, Type_2, ... Type_N > >
    < - HeadClass < 0, Type_0 > { Value_0 }
    < - NestedTuple < 1, Types < Type_1, Type_2, ... Type_N > >
        < - HeadClass < 1, Type_1 > { Value_1 }
        < - NestedTuples < 2, Types < Type_2, ... Type_N > >
            < - HeadClass < 2, Type_2 > { Value_2 }
            < - ...
                < - HeadClass < [N-1], Type_[N-1] > { Value_[N-1] }
                < - NestedTuple < N, Types < Type_N > >
                    < - HeadClass < N, Type_N > { Value_N }

Inheritance Structure Notation:

    Child
    < - Parant
    < - Parent

NestedTuple Structure Notation: 

    Class < Index Tag, Types < Type Tags ... > >

HeadClass Structure Notation:

    Class < Index Tag, Type Tag > { Data Value }

Anyways, because the GNU ISO tuple header is not so easy to read, in an attempt to understand how it worked, I created my own toy class template called MyTuple. The code grew to be over 1000 lines, but a lot of it is comments. I also defined all the copy and move constructors which takes a lot of space. I also added some tools to print the contents and have some tests called from main().

Anyways, here it is.

MyTuple template toy

I made my version the old way without auto, because that's how it's done in the GNU library. Using "auto" makes things easier. It's a bit masochistic, but I wanted to understand how you can determine the proper return types without using "auto". It can be done using metafunctions (I actually used a combination of struct templates and alias templates that take an integer index parameter as if it was a function argument).

The only major difference between my implementation and the GNU library one is the GNU library functions are all static. This is might be more efficient in terms of compile time. I thought the use of static functions made the implementation harder to understand though. In my version I use non-static methods.

The library implementation also has a specialization for tuples of length 2, probably to make them more efficient.

Hernia

As an aside, a better implementation would use a balanced binary tree inheritance. This is better because the total symbol length shrinks; in your case, the total symbol length is O(n^2), while a balanced binary tree can manage O(n lg n). There is a larger constant factor as building the balanced binary tree of types takes some metaprogramming, but at even modest lengths (like 100) it pays off. OTOH, most use of tuple is for like 3 or 4 elements. – Mini

Answer 3

It is often useful to define classes or structures that have a variable number and type of data members which are defined at compile time. The canonical example is std::tuple, but sometimes is it is necessary to define your own custom structures. Here is an example that defines the structure using compounding (rather than inheritance as with std::tuple.

Start with the general (empty) definition, which also serves as the base-case for recrusion termination in the later specialisation:

template<typename ... T>
struct tuple {};

This already allows us to define an empty structure, tuple<> data, albeit that isn't very useful yet.

Next comes the recursive case specialisation:

template<typename T, typename ... Rest>
struct tuple<T, Rest ...>
{
    tuple(const T& first, const Rest& ... rest)
        : first(first)
        , rest(rest...)
    {}
    
    T first;                                
    tuple<Rest ... > rest;
};

This is now sufficient for us to create arbitrary data structures, like tuple<int, float, std::string> data(1, 2.1, "hello").

So what's going on? First, note that this is a specialisation whose requirement is that at least one variadic template parameter (namely T above) exists, whilst not caring about the specific makeup of the pack Rest. Knowing that T exists allows the definition of its data member, first. The rest of the data is recursively packaged as tuple<Rest ... > rest. The constructor initiates both of those members, including a recursive constructor call to the rest member.

You can visualise this as follows:

tuple <int, float>
   -> int first
   -> tuple <float> rest
         -> float first
         -> tuple <> rest
              -> (empty)

So on to the helper class. This time we will need an empty forward declaration and two specialisations. First the declaration:

template<size_t idx, typename T>
struct helper;

Now the base-case (when idx==0). In this case we just return the first member:

template<typename T, typename ... Rest>
struct helper<0, tuple<T, Rest ... >>
{
    static T get(tuple<T, Rest...>& data)
    {
        return data.first;
    }
};

In the recursive case, we decrement idx and invoke the helper for the rest member:

template<size_t idx, typename T, typename ... Rest>
struct helper<idx, tuple<T, Rest ... >>
{
    static auto get(tuple<T, Rest...>& data)
    {
        return helper<idx-1, tuple<Rest ...>>::get(data.rest);
    }
};

To work through an example, suppose we have tuple<int, float> data and we need data.get<1>(). This invokes helper<1, tuple<int, float>>::get(data) (the 2nd specialisation), which in turn invokes helper<0, tuple>::get(data.rest), which finally returns (by the 1st specialisation as now idx is 0) data.rest.first.

So that's it! Here is the whole functioning code, with some example use in the main function:

Full code

#include <type_traits>
#include <iostream>

using namespace std;

namespace my {
  template <typename ...Ts>
  struct tuple {};

  template <typename T, typename ...Ts>
  struct tuple <T, Ts...> {
    tuple(T first, Ts... rest) : 
    first(first), rest(rest...){}
    
    T first;

    tuple<Ts...> rest;
  };

  namespace detail {
    template <int N, typename ...Ts>
    struct helper;

    template <typename T, typename ...Ts>
    struct helper <0, tuple<T, Ts...>> {
      static auto get(tuple<T, Ts...> ds){
        return ds.first;
      }
    };

    template <int N, typename T, typename ...Ts>
    struct helper <N, tuple<T, Ts...>> {
      static auto get(tuple<T, Ts...> ds){
        return helper<N-1, tuple<Ts...>>::get(ds.rest);
      }
    };
  }

  template <int N, typename ...Ts>
  auto get(tuple<Ts...> ds){
    return detail::helper<N, decltype(ds)>::get(ds);
  }
}

int main(){
  my::tuple <int, bool, float> test = {5, false, 10.5};

  std::cout << my::get<0>(test) << endl;

  std::cout << my::get<1>(test) << endl;

  std::cout << my::get<2>(test) << endl;
}

Reference

Mulder