How is std::tuple implemented?

Question

I'd like to know how are tuple implemented in standard library for C++0x. I tried to read description in libstdc++ manual and then read template listing, but it's really hard to understand how it works, especially when reading code.

Can someone explain me in few sentences the idea of tuple implementation? I want to know this, because I thinking about using tuples in my code and i want to understand how it works and what type of overhead does it brings (extends compile time only, perform many copy operations on memory, execute many other function in constructor, etc.).

Solution 1

One approach to implementing tuples is using multiple-inheritance. The tuple-elements are held by leaf-classes, and the tuple class itself inherits from multiple leafs. In pseudo-code:

template<typename T0, typename T1, ..., typename Tn>
class PseudoTuple : TupleLeaf<0, T0>, TupleLeaf<1, T1>, ..., TupleLeaf<n, Tn> {
   ...
};

Each leaf has an index, so that each base-class becomes unique even if the types they contain are identical, so we can access the nth element with a simple static_cast:

static_cast<TupleLeaf<0, T0>*>(this);
// ...
static_cast<TupleLeaf<n, Tn>*>(this);

I've written up a detailed explanation about this "flat" tuple implementation here: C++11 tuple implementation details (Part 1)

Solution 2

I thought I would add a non-pseudocode simple recursive implementation for reference

#include <iostream>

// Contains the actual value for one item in the tuple. The 
// template parameter `i` allows the
// `Get` function to find the value in O(1) time
template<std::size_t i, typename Item>
struct TupleLeaf {
    Item value;
};

// TupleImpl is a proxy for the final class that has an extra 
// template parameter `i`.
template<std::size_t i, typename... Items>
struct TupleImpl;

// Base case: empty tuple
template<std::size_t i>
struct TupleImpl<i>{};

// Recursive specialization
template<std::size_t i, typename HeadItem, typename... TailItems>
struct TupleImpl<i, HeadItem, TailItems...> :
    public TupleLeaf<i, HeadItem>, // This adds a `value` member of type HeadItem
    public TupleImpl<i + 1, TailItems...> // This recurses
    {};

// Obtain a reference to i-th item in a tuple
template<std::size_t i, typename HeadItem, typename... TailItems>
HeadItem& Get(TupleImpl<i, HeadItem, TailItems...>& tuple) {
    // Fully qualified name for the member, to find the right one 
    // (they are all called `value`).
    return tuple.TupleLeaf<i, HeadItem>::value;
}

// Templated alias to avoid having to specify `i = 0`
template<typename... Items>
using Tuple = TupleImpl<0, Items...>;

int main(int argc, char** argv) {
    Tuple<int, float, std::string> tuple;
    Get<0>(tuple) = 5;
    Get<1>(tuple) = 8.3;
    Get<2>(tuple) = "Foo";
    std::cout << Get<0>(tuple) << std::endl;
    std::cout << Get<1>(tuple) << std::endl;
    std::cout << Get<2>(tuple) << std::endl;
    return 0;
}

Solution 3

A tuple is typically implemented as a compile time linked-list.

The code is a bit obfuscated through template-syntax, but following elements are normally present:

1. a chain of classes with head and tail elements (cons-elements)
2. an empty tail instance to indicate the end of the list.
3. recursive code to walk the list to a certain index, implemented as recursive template-instantiations (instantiated at compile time).

There exist reasonable implementations in C++03 (e.g. boost).

Variadic templates allow an unlimited number of elements, as mentioned by Motti.

The cost is normally a compile time-one. Copy constructors might be called during initialization (max 1), and when copying the tuples themselves.

Solution 4

Implementing std::tuple is possible via variadic templates, that were introduced into the core language as part of C++11.

I know this is begging the question but it gives you a better search phrase to research.

Solution 5

An implementation using recursive data structures by composition rather than inheritance:

#include <iostream>

template <typename T, typename... Ts>
struct Tuple {
    Tuple(const T& t, const Ts&... ts)
        : value(t)
        , rest(ts...)
    {
    }

    constexpr int size() const { return 1 + rest.size(); }

    T value;
    Tuple<Ts...> rest;
};
template <typename T>
struct Tuple<T> {
    Tuple(const T& t)
        : value(t)
    {
    }

    constexpr int size() const { return 1; }

    T value;
};

template <size_t i, typename T, typename... Ts>
struct nthType : nthType<i-1, Ts...> {
    static_assert(i < sizeof...(Ts) + 1, "index out of bounds");
};

template <typename T, typename... Ts>
struct nthType<0, T, Ts...> { T value; };

template <size_t i>
struct getter {
    template <typename... Ts>
    static decltype(nthType<i, Ts...>::value)& get(Tuple<Ts...>& t) {
        return getter<i-1>::get(t.rest);
    }
};
template <>
struct getter<0> {
    template <typename T, typename... Ts>
    static T& get(Tuple<T, Ts...>& t) {
        return t.value;
    }
};

template <size_t i, typename... Ts>
decltype(nthType<i, Ts...>::value)& get(Tuple<Ts...>& t) {
    return getter<i>::get(t);
}


int main()
{
    Tuple<int,int,float> t(1,2,3.4);
    
    std::cout << get<0>(t) << "\n";
    std::cout << get<1>(t) << "\n";
    std::cout << get<2>(t) << "\n";
    // std::cout << get<3>(t) << "\n"; // error with useful information
    
    return 0;
}

I find this method vastly superior to the alternatives given how intuitive it is to use when doing recursive things like apply map etc., especially if you have ever used recursive data structures in functional programming. Of course, for indexed retrieval we need to do some weird template stuff, but in general use the recursive nature is very intuitive. If someone could explain why this setup is not more common, I would love to know.

View more solutions

Comments

[Jean-Bernard Jansen]

Yes thats a great explanation ! Unfortunately, that is not how the tuple is implemented into libstdc++, which one sticks to the recursive implementation. Cant wait for a more widely distributed libc++ !

[Kyle Strand]

Plus, the implementation is not trivial, as evidenced by the fact that OP mentioned trying and failing to understand it by reading the code of an example implementation.

[Kyle Strand]

It might be useful to briefly describe the non-recursive implementation, too.

[Daedalus]

This answer is being discussed on meta.

[Motti]

@KyleStrand the OP read the code in 2010 when variadic templates weren't yet commonly understood. I gave him the tools to understand variadic templates. I consider this to be an answer.

[mitchnull]

@KyleStrand erm, this is the non-recursive implementation (T : L1, L2, L3 vs T : L1 : L2 : L3 of the recursive implementation)

[Kyle Strand]

@mitchnull Sorry, I meant the recursive implementation.

[Violet Giraffe]

Could you also briefly mention the pros and cons of the recursive vs. non-recursive implementation?

[mitchnull]

just for the record: this is a recursive implementation, not a flat one as I described :)

[Andrea Allais]

Apologies, I misunderstood your answer. I edited mine to remove the claim that it implements your solution.

[Adam.Er8]

Wow @mitchnull, I learned so much by reading your blogpost, thanks!

[Questionable]

@AndreaAllais This is really cool. However, I'm curious how does the Get function work? Ignoring the using. If I initialize with TupleImpl<0, int, float, std::string> tuple; When I call Get<1>(tuple), wouldn't the call be equivalent to Get(TupleImpl<1, int, {float,std::string}>& tuple). Since TupleLeaf<1, int> doesn't exist, shouldn't this fail?

[Andrea Allais]

@Questionable When you call Get<1>(tuple), the argument gets upcasted from TupleImpl<0, int, float, std::string> to TupleImpl<1, float, std::string>. This upcast is the only possible because of the value of the leading integer template parameter. Notice that the upcast dropped the int template parameter. This is because the type template parameters are dropped one by one in the inheritance hierarchy as the leading integer template parameter increases. Thus Get<1>(tuple) ends up calling tuple.TupleLeaf<1, float>::value, which is valid.

[Christopher Mauer]

This is both slower to compile and more limited than variadic implementations. Template recursion depth restricts you from creating extremely large tuples with this method, and the benefits of variadic implementations over recursive ones for the compiler are well-known.

[Asad-ullah Khan]

Interesting, I would like to know more about this. Do you have a resource you could share? I cannot find anything on this specific subject. Also what do you mean by "variadic implementations over recursive ones"? Aren't both implementations recursive?

[Christopher Mauer]

Look at the accepted answer to see how the non-recursive implementation is setup. You can kind of infer what most of the steps are from there. Interestingly, the non-recursive implementation allows for aggregate initialization, which has a rather large number of uses.

[Asad-ullah Khan]

Ah I understand, I was confused because I thought variadic templates had to be used recursively (which is true) but that doesn't mean the resulting output is recursive, if that makes sense.

[Christopher Mauer]

I think so. There are a lot of ways to use variadic templates without recursion, but IMO, many of them are non-intuitive. The trick with std::make_index_sequence used to expand the tuple in the non-recursive version is quite useful.