How is std::tuple implemented?
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)
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;
}
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:
- a chain of classes with head and tail elements (cons-elements)
- an empty tail instance to indicate the end of the list.
- 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.