How does std::get work?

Question 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";
}

Question 2

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