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

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)

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