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.).

Baras

Answer 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)

Perky

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++ ! – Munmro

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

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

@Perky Sorry, I meant the recursive implementation. – Affinity

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

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

Answer 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;
}

Tall

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

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

@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? – Sanctify

@Sanctify 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. – Tall

@AndreaAllais could you please shed some light on why the integer parameter is needed, e.g. vs. simply inheriting from TailItems? I think this may have to do with resolving the ambiguity from interiting from TupleLeaf multiple times? If so, if TupleLeaf is a member variable, would one still need the integer template parameter? – Hartzel

The integer index is required by the function Get to distinguish between the many TupleImpl::value inherited members that have the same name. I don't understand the alternative you are proposing. It's totally possible that a simpler implementation exists, this is the best I could do. – Tall

Answer 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.

Armstrong

Answer 4

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.

Pamphleteer

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. – Noah

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? – Pamphleteer

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. – Noah

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. – Pamphleteer

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. – Noah

Answer 5

tuple can be implemented with multiple inheritance like what mitchnull said.

A mininal working example:

#include <cstddef>
#include <utility>

template <std::size_t I, typename T>
struct tuple_unit
{
    template <typename U>
    tuple_unit(U&& u) : m_unit(std::forward<U>(u)) {}
    T m_unit;
};

template <typename, typename ...>
struct tuple_base;

template <std::size_t ...Is, typename ...Ts>
struct tuple_base<std::index_sequence<Is...>, Ts...> : tuple_unit<Is, Ts>...
{
    template <typename ...Us>
    tuple_base(Us... us) : tuple_unit<Is, Ts>(us)... {}
};

template <typename ...Ts>
class tuple : public tuple_base<std::make_index_sequence<sizeof...(Ts)>, Ts...>
{
public:
    tuple(const Ts& ...ts) : tuple_base<std::make_index_sequence<sizeof...(Ts)>, Ts...>(ts...) {}
};

template <typename ...Ts>
tuple(Ts...) -> tuple<Ts...>;

int main()
{
    tuple t{ 1, 2.0, 'c', "def" };   // The type of t is tuple<int, double, char, const char*>
}

Full implementation is here.

Visualize

Answer 6

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.

Tion

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. – Affinity

This answer is being discussed on meta. – Boltzmann

@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. – Tion