How is std::tuple implemented?

user_325519 0
Viewed 23352

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

tuples std c++11 c++
6 Answers

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

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.

user_40213080

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.

user_109535650
Related