Variadic template data structures

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 DataStructure {};

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

Next comes the recursive case specialisation:

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

This is now sufficient for us to create arbitrary data structures, like DataStructure<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 DataStructure<Rest ... > rest. The constructor initiates both of those members, including a recursive constructor call to the rest member.

To understand this better, we can work through an example: suppose you have a declaration DataStructure<int, float> data. The declaration first matches against the specialisation, yielding a structure with int first and DataStructure<float> rest data members. The rest definition again matches this specialisation, creating its own float first and DataStructure<> rest members. Finally this last rest matches against the base-case defintion, producing an empty structure.

You can visualise this as follows:

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

Now we have the data structure, but its not terribly useful yet as we cannot easily access the individual data elements (for example to access the last member of DataStructure<int, float, std::string> data we would have to use data.rest.rest.first, which is not exactly user-friendly). So we add a get method to it (only needed in the specialisation as the base-case structure has no data to get):

template<typename T, typename ... Rest>
struct DataStructure<T, Rest ...>
{
    ...
    template<size_t idx>
    auto get()
    {
        return GetHelper<idx, DataStructure<T,Rest...>>::get(*this);
    }
    ...
};

As you can see this get member function is itself templated - this time on the index of the member that is needed (so usage can be things like data.get<1>(), similar to std::tuple). The actual work is done by a static function in a helper class, GetHelper. The reason we can’t define the required functionality directly in DataStructure‘s get is because (as we will shortly see) we would need to specialise on idx - but it isn’t possible to specialise a template member function without specialising the containing class template. Note also the use of a C++14-style auto here makes our lives significantly simpler as otherwise we would need quite a complicated expression for the return type.

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 GetHelper;

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

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

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

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

To work through an example, suppose we have DataStructure<int, float> data and we need data.get<1>(). This invokes GetHelper<1, DataStructure<int, float>>::get(data) (the 2nd specialisation), which in turn invokes GetHelper<0, DataStructure<float>>::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:

#include <iostream>

template<size_t idx, typename T>
struct GetHelper;

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

template<typename T, typename ... Rest>
struct DataStructure<T, Rest ...>
{
    DataStructure(const T& first, const Rest& ... rest)
        : first(first)
        , rest(rest...)
    {}
    
    T first;
    DataStructure<Rest ... > rest;
    
    template<size_t idx>
    auto get()
    {
        return GetHelper<idx, DataStructure<T,Rest...>>::get(*this);
    }
};

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

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

int main()
{
    DataStructure<int, float, std::string> data(1, 2.1, "Hello");
        
    std::cout << data.get<0>() << std::endl;
    std::cout << data.get<1>() << std::endl;
    std::cout << data.get<2>() << std::endl;
    
    return 0;
}