C++11 tuple implementation details (Part 1)

In his "Variadic Templates are Funadic" talk at GoingNative 2012 Andrei Alexandrescu outlines a "recursive" implementation of std::tuple. He also notes that most implementations arrange tuple members in memory in the "wrong" order, that is, std::tuple<int, double, std::string> will have a memory layout where the std::string comes first and the int comes last. The straightforward recursive implementation he presents also has this property.

I checked out the implementation of std::tuple in libc++, and their implementation has the "sane" memory layout, and it's also non-recursive, which — according to Howard Hinnant, the primary author of libc++'s tuple implementation — has other benefits, like faster compile times, too.

In this post I'll try to explain the implementation details of a flat (non-recursive) tuple. The implementation presented here is based on the libc++ version — in fact, it's mostly copy-waste, I just simplified some of the hairy bits and omitted some parts, like the allocator related constructors, exception specifications, tie and tuple_cat. I'll return to them in a follow-up post. Some parts (like our internal TupleSize and TupleElement) are a bit more complicated than the ones in the standard library, because we can't just assume/dictate implementation details in the std namespace and we need compatibility with the standard tuple-like classes.

Tuple synopsis

First, let's see what our Tuple should look like:

template <typename... T>
class Tuple {
public:
    Tuple();

    explicit Tuple(const T&...);

    template <typename... U>
    explicit Tuple(U&&...);

    Tuple(const Tuple&);

    Tuple(Tuple&&);

    template <typename... U>
    Tuple(const Tuple<U...>&);

    template <typename... U>
    Tuple(Tuple<U...>&&);

    Tuple& operator=(const Tuple&);

    Tuple& operator=(Tuple&&);

    template <typename... U>
    Tuple& operator=(const Tuple<U...>&);

    template <typename... U>
    Tuple& operator=(Tuple<U...>&&);

    void swap(Tuple&);
};
  
template <typename... T> typename tuple_size<Tuple<T...>>;

template <size_t I, typename... T> typename tuple_element<I, Tuple<T...>>;

// element access:

template <size_t I, typename... T>
typename tuple_element<I, Tuple<T...>>::type&
get(Tuple<T...>&);

template <size_t I, typename... T>
typename tuple_element<I, Tuple<T...>>::type const&
get(const Tuple<T...>&);

template <size_t I, typename... T>
typename tuple_element<I, Tuple<T...>>::type&&
get(Tuple<T...>&&);

// relational operators:

template<typename... T, typename... U>
bool operator==(const Tuple<T...>&, const Tuple<U...>&);

template<typename... T, typename... U>
bool operator<(const Tuple<T...>&, const Tuple<U...>&);

template<typename... T, typename... U>
bool operator!=(const Tuple<T...>&, const Tuple<U...>&);

template<typename... T, typename... U>
bool operator>(const Tuple<T...>&, const Tuple<U...>&);

template<typename... T, typename... U>
bool operator<=(const Tuple<T...>&, const Tuple<U...>&);

template<typename... T, typename... U>
bool operator>=(const Tuple<T...>&, const Tuple<U...>&);

template <typename... Types>
void swap(Tuple<Types...>& x, Tuple<Types...>& y);

Notes on namespaces

I'm planning to use this Tuple implementation in a project (a simple OpenGL game on android), thus the Tuple class is in namespace migl2, the namespace used in this project. All implementation details are in namespace migl2::detail, and some template specializations are in (or lifted into) namespace std. I'm using namespace std inside namespace migl2::detail, so std::forward, std::enable_if and others will be unqualified there. The overall layout is something like this:

namespace migl2 {
using std::size_t;

// forward declaration of our Tuple template
template <typename... Ts_>
class Tuple;

namespace detail {
using namespace std;
using std::swap; // needed for primitive types, as ADL won't kick in for them

/*** Tuple implementation details come here ***/

} // end namespace detail

/*** user-visible Tuple and related functions come here ***/

} // end namespace migl2

namespace std {

/*** specializations of tuple_size, tuple_element and get for our Tuple come here ***/

} // end namespace std

A slightly odd-looking thing here is the using std::swap; line right after using namespace std. At first glance it'd seem superfluous, but it's in fact necessary. We'll use unqualified calls to swap() to enable Argument Dependent Lookup. Unqualified calls to swap would work for user defined types if they also provide their swap override, but it won't work for primitive types (as they're not in namespace std) or user-defined types that don't provide their specialized swap(), since the generic std::swap() is not picked up with ADL in this case, as we'll have our own swap() defined for TupleLeaf in the detail namespace, and without that "extra" using std::swap the compiler would try to use that for all types that don't provide their own overload.

The non-recursive approach

The basic idea behind the non-recursive tuple implementation is that tuple elements are stored in TupleLeaf base classes, but whereas the recursive implementation uses a deep class hierarchy, we'll use multiple-inheritance. 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);

TupleLeaf

Let's start with our basic building-block, the TupleLeaf template:

// TupleLeaf

template <size_t I_, typename ValueType_,
        bool IsEmpty_ = is_empty<ValueType_>::value
#if __has_feature(is_final)
            && !__is_final(ValueType_)
#endif
    >
class TupleLeaf;

template <size_t I, typename ValueType, bool IsEmpty>
inline void swap(TupleLeaf<I, ValueType, IsEmpty>& a,
                 TupleLeaf<I, ValueType, IsEmpty>& b) {
    swap(a.get(), b.get());
}

template <size_t I_, typename ValueType_, bool IsEmpty_>
class TupleLeaf {
    ValueType_ value_;
    
    TupleLeaf& operator=(const TupleLeaf&) = delete;
public:
    TupleLeaf()
            : value_() {
        static_assert(!is_reference<ValueType_>::value,
            "Attempt to default construct a reference element in a tuple");
    }

    TupleLeaf(const TupleLeaf& t)
            : value_(t.get()) {
        static_assert(!is_rvalue_reference<ValueType_>::value,
            "Can not copy a tuple with rvalue reference member");
    }

    template <typename T, typename = typename enable_if<
            is_constructible<ValueType_, T>::value>::type>
    explicit TupleLeaf(T&& t)
            : value_(forward<T>(t)) {
        static_assert(!is_reference<ValueType_>::value ||
                (is_lvalue_reference<ValueType_>::value &&
                 (is_lvalue_reference<T>::value ||
                  is_same<typename remove_reference<T>::type,
                    reference_wrapper<
                        typename remove_reference<ValueType_>::type
                    >
                 >::value)) ||
                (is_rvalue_reference<ValueType_>::value &&
                 !is_lvalue_reference<T>::value),
            "Attempted to construct a reference element in a tuple with an rvalue");
    }

    template <typename T>
    explicit TupleLeaf(const TupleLeaf<I_, T>& t) 
            : value_(t.get()) {
    }

    template <typename T>
    TupleLeaf& operator=(T&& t) {
        value_ = forward<T>(t);
        return *this;
    }

    int swap(TupleLeaf& t) {
        migl2::detail::swap(*this, t);
        return 0;
    }

    ValueType_& get() {
        return value_;
    }

    const ValueType_& get() const {
        return value_;
    }
};

Lines 3-9:

Here we declare our TupleLeaf template, and set the IsEmpty value to true when we can use Empty Base Class Optimization. A little bit of trickery is needed here: if the implementation supports final classes, then we must check if our ValueType_ is final or not. Since we can't subclass a final class, we cannot use EBCO in that case.

Lines 11-15:

Swap two TupleLeafs by swapping the contained elements. We'll use this from the swap member functions.

Lines 17-75:

The TupleLeaf implementation for the generic case (no Empty Base Class Optimization). We disable the normal copy-assignment (line 17), as we'll always use the forwarding copy-assignment (lines 53-57). The only interesting bit here is the return type of swap (lines 59-62). Normally, it should be void, but we'll later call this swap member from our TupleImpl::swap with template-pack expansion, and to do that we need a function with a return type. See the swallow function below.

Next, we specialize our TupleLeaf for the case when we can use the Empty Base Class Optimization, so as to not waste space for empty tuple members:

// TupleLeaf specialization in case we can use Empty Base Class Optimization:

template <size_t I_, typename ValueType_>
class TupleLeaf<I_, ValueType_, true>
        : private ValueType_ {

    TupleLeaf& operator=(const TupleLeaf&) = delete;
public:
    TupleLeaf() {
    }

    TupleLeaf(const TupleLeaf& t)
            : ValueType_(t.get()) {
        static_assert(!is_rvalue_reference<ValueType_>::value,
            "Can not copy a tuple with rvalue reference member");
    }

    template <typename T, typename = typename enable_if<
            is_constructible<ValueType_, T>::value>::type>
    explicit TupleLeaf(T&& t)
            : ValueType_(forward<T>(t)) {
    }

    template <typename T>
    explicit TupleLeaf(const TupleLeaf<I_, T>& t)
            : ValueType_(t.get()) {
    }

    template <typename T>
    TupleLeaf& operator=(T&& t) {
        ValueType_::operator=(forward<T>(t));
        return *this;
    }

    int swap(TupleLeaf& t) {
        migl2::detail::swap(*this, t);
        return 0;
    }

    ValueType_& get() {
        return static_cast<ValueType_&>(*this);
    }

    const ValueType_& get() const {
        return static_cast<const ValueType_&>(*this);
    }
};

Some glue: TupleIndexes, TupleSize and TupleElements

We'll need indexes and corresponding types for our TupleLeafs. To handle their coupling we'll create two helper classes for storing them and corresponding templates to create them when needed:

// TupleIndexes

template <size_t... Is_>
struct TupleIndexes {
};

template <size_t Start_, typename TupleIndexes_, size_t End_>
struct MakeTupleIndexesImpl;

template <size_t Start_, size_t... Indexes_, size_t End_>
struct MakeTupleIndexesImpl<Start_, TupleIndexes<Indexes_...>, End_> {
    typedef typename MakeTupleIndexesImpl<Start_ + 1,
            TupleIndexes<Indexes_..., Start_>, End_>::type type;
};

template <size_t End_, size_t... Indexes_>
struct MakeTupleIndexesImpl<End_, TupleIndexes<Indexes_...>, End_> {
    typedef TupleIndexes<Indexes_...> type;
};

template <size_t End_, size_t Start_ = 0>
struct MakeTupleIndexes {
    static_assert(Start_ <= End_, "MakeTupleIndexes: invalid parameters");
    typedef typename MakeTupleIndexesImpl<Start_, TupleIndexes<>, End_>::type type;
};

MakeTupleIndexes creates a type that encodes the indexes from Start_ to End_, for example: TupleTypes<0, 1, 2>. It could be a bit simpler, but we'll extend the standard tuple with a constructor that takes less parameters than the actual number of tuple elements (and default-constructs the rest), and for that we'll need to be able to create TupleIndexes starting from an arbitrary index instead of 0. The same applies to MakeTupleTypes below. Both templates use a helper template to build their values incrementally. The end result is a typedef for the complete indexes and types.

Note: Since the time of writing, c++14 introduced std::index_sequence, since the concept was found to be useful in many situations. The implementation of the sequence generation can also be optimized: instead of the above described linear recursion one can use a logarithmic implementation, or the sequence generation could even be a compiler intrinsic. The tuple implementation could be updated to use the new index_sequence here.

// TupleTypes

template <typename... Ts_>
struct TupleTypes {
};

// TupleSize

template <typename T_>
struct TupleSize
        : public tuple_size<T_> {
};

template <typename T_>
struct TupleSize<const T_>
        : public TupleSize<T_> {
};

template <typename T_>
struct TupleSize<volatile T_>
        : public TupleSize<T_> {
};

template <typename T_>
struct TupleSize<const volatile T_>
        : public TupleSize<T_> {
};

template <typename... Ts_>
struct TupleSize<TupleTypes<Ts_...>>
        : public integral_constant<size_t, sizeof...(Ts_)> {
};

// specialization for Tuple

template <typename... Ts_>
struct TupleSize<Tuple<Ts_...>>
        : public integral_constant<size_t, sizeof...(Ts_)> {
};

Here we declare our special type-holder, TupleTypes and then we can define TupleSize for that using the sizeof... operator. TupleSize for our own Tuple uses TupleTypes. For all other types, we fall back on the standard tuple_size template, thus our internal TupleSize will work for std::tuple, std::pair and std::array, too. The cv-qualified types are forwarded to the implementation for the unqualified TupleTypes.

Similarly our internal TupleElement is defined for TupleTypes and Tuple, but falls back on the standard tuple_element for other types:

// TupleElement

template <size_t I_, typename T_>
class TupleElement : public tuple_element<I_, T_> {
};

template <size_t I_>
class TupleElement<I_, TupleTypes<>> {
public:
    static_assert(I_ != I_, "tuple_element index out of range");
};

template <typename H_, typename... Ts_>
class TupleElement<0, TupleTypes<H_, Ts_...>> {
public:
    typedef H_ type;
};

template <size_t I_, typename H_, typename... Ts_>
class TupleElement<I_, TupleTypes<H_, Ts_...>> {
public:
    typedef typename TupleElement<I_ - 1, TupleTypes<Ts_...>>::type type;
};

// specialization for Tuple

template <size_t I_, typename... Ts_>
class TupleElement<I_, Tuple<Ts_...>> {
public:
    typedef typename TupleElement<I_, TupleTypes<Ts_...>>::type type;
};

template <size_t I_, typename... Ts_>
class TupleElement<I_, const Tuple<Ts_...>> {
public:
    typedef typename add_const<typename TupleElement<I_, TupleTypes<Ts_...>>::type>::type type;
};

template <size_t I_, typename... Ts_>
class TupleElement<I_, volatile Tuple<Ts_...>> {
public:
    typedef typename add_volatile<typename TupleElement<I_, TupleTypes<Ts_...>>::type>::type type;
};

template <size_t I_, typename... Ts_>
class TupleElement<I_, const volatile Tuple<Ts_...>> {
public:
    typedef typename add_cv<typename TupleElement<I_, TupleTypes<Ts_...>>::type>::type type;
};

TupleElement is a classic recursive template. We chomp off the types from the beginning of our list as we decrement the index (I_ in the main template at lines 19-23). The stop condition is when we reach I_ == 0 (lines 13-17). If the remaining TupleTypes is empty before we reach our stop condition, we signal an error with a static_assert (lines 7-11). The end result — if all goes well — is a typedef (TupleElement::type) corresponding to the I_th element in our TupleTypes. The specialization for our final Tuple uses TupleTypes adjusted for const and volatile qualifiers.

Note: TupleElement could be implemented by letting overload resolution find the correct type for us instead of the above presented linear recursion. See this other nice blog post about tuples for details.

Now we can return to our helper template that creates TupleTypes for us:

// MakeTupleTypes

template <typename TupleTypes_, typename Tuple_, size_t Start_, size_t End_>
struct MakeTupleTypesImpl;

template <typename... Types_, typename Tuple_, size_t Start_, size_t End_>
struct MakeTupleTypesImpl<TupleTypes<Types_...>, Tuple_, Start_, End_> {
    typedef typename remove_reference<Tuple_>::type TupleType;
    typedef typename MakeTupleTypesImpl<TupleTypes<Types_...,
            typename conditional<is_lvalue_reference<Tuple_>::value,
                // append ref if Tuple_ is ref
                typename TupleElement<Start_, TupleType>::type&,
                // append non-ref otherwise 
                typename TupleElement<Start_, TupleType>::type>::type>,
            Tuple_, Start_ + 1, End_>::type  type;
};

template <typename... Types_, typename Tuple_, size_t End_>
struct MakeTupleTypesImpl<TupleTypes<Types_...>, Tuple_, End_, End_> {
    typedef TupleTypes<Types_...> type;
};

template <typename Tuple_,
         size_t End_ = TupleSize<typename remove_reference<Tuple_>::type>::value,
         size_t Start_ = 0>
struct MakeTupleTypes {
    static_assert(Start_ <= End_, "MakeTupleTypes: invalid parameters");
    typedef typename MakeTupleTypesImpl<TupleTypes<>, Tuple_, Start_, End_>::type type;
};

MakeTupleTypes extracts the types from Tuple_ in the range [Start_ .. End_] and stores them in our TupleTypes type. The element-types are determined with the above defined TupleElement, and appended to a temporary list. As std::tuple_element (and consequently our TupleElement) doesn't work on reference types, we use a typedef for the reference-stripped type of Tuple_ (TupleType at line 8), but we convert the result type from TupleElement to a reference if the original Tuple_ was an lvalue_reference (types that were already reference-types in the original tuple are not touched by this transformation).

TupleImpl and swallow()

We're ready to assemble these pieces into our internal TupleImpl class that will be the basis of the final Tuple.

// TupleImpl

template <typename... Ts>
void swallow(Ts&&...) {
}

template <typename TupleIndexes_, typename... Ts_>
struct TupleImpl;

template <size_t... Indexes_, typename... Ts_>
struct TupleImpl<TupleIndexes<Indexes_...>, Ts_...>
        : public TupleLeaf<Indexes_, Ts_>... {
    template <size_t... FirstIndexes, typename... FirstTypes,
              size_t... LastIndexes, typename... LastTypes,
              typename... ValueTypes>
    explicit TupleImpl(
                TupleIndexes<FirstIndexes...>, TupleTypes<FirstTypes...>,
                TupleIndexes<LastIndexes...>, TupleTypes<LastTypes...>,
                ValueTypes&&... values)
            : TupleLeaf<FirstIndexes,
                    FirstTypes>(forward<ValueTypes>(values))...,
                    TupleLeaf<LastIndexes, LastTypes>()... {
    }

    template <typename OtherTuple>
    TupleImpl(OtherTuple&& t)
            : TupleLeaf<Indexes_, Ts_>(forward<
                    typename TupleElement<Indexes_,
                    typename MakeTupleTypes<OtherTuple>::type>::type
                    >(get<Indexes_>(t)))... {
    }

    template <typename OtherTuple>
    TupleImpl& operator=(OtherTuple&& t) {
        swallow(TupleLeaf<Indexes_, Ts_>::operator=(forward<
                    typename TupleElement<Indexes_,
                    typename MakeTupleTypes<OtherTuple>::type>::type
                    >(get<Indexes_>(t)))...);
        return *this;
    }

    TupleImpl& operator=(const TupleImpl& t) {
        swallow(TupleLeaf<Indexes_, Ts_>::operator=(static_cast<
                const TupleLeaf<Indexes_, Ts_>&>(t).get())...);
        return *this;
    }

    void swap(TupleImpl& t) {
        swallow(TupleLeaf<Indexes_, Ts_>::swap(
            static_cast<TupleLeaf<Indexes_, Ts_>&>(t))...);
    }
};

Lines 3-5:

The swallow() functions is just a little trick to allow us to use template-parameter-pack expansion at places where it wouldn't be possible otherwise: when we want to call foo() for each element of the template-parameter-pack, we call swallow() with the expansion like this:

template<typename... Ts>
void fooCaller(Ts... ts) {
    swallow(foo(ts)...);
}

The parameters of swallow() bind to anything except void, hence we'll need to make sure that our foo() does return something (is not void foo()). That's why we have the "strange" signature of our TupleLeaf::swap() function. Since the function itself doesn't do anything, the actuall call will be optimized away, and the only visible effect will be that foo() will be called for each element.

Lines 7-8:

The first template parameter of our TupleImpl template will be our TupleIndexes, and the rest are the actual types stored in the tuple. We'll immediately specialize this template declaration using actual indexes (as non-type template parameters) below.

Lines 10-12:

Here's our (only) specialization using actual indexes, and fixing the first type parameter to be TupleIndexes, and as we mentioned at the beginning, we're using multiple inheritance from TupleLeaf to build our class. The indexes and corresponding types are expanded in tandem, forming the base-classes.

Lines 13-23:

This is our "standard" constructor. As mentioned before, we'll allow construction of our final Tuple with less parameters than tuple elements. To allow this, this TupleImpl constructor splits the parameters in two, and expands them separately. The sum of the parameters of course must match the actual number of elements, but we'll take care of that in the final Tuple implementation.

Lines 25-31:

This is our "converting" constructor. We extract the elements from OtherTuple with get() expanded for each index our TupleImpl has, and forward them to the corresponding TupleLeafs. Since std::forward requires an explicit type specifier, we determine the correct type to use by building TupleTypes from OtherTuple and extracting the required type using TupleElement.

Lines 23-40:

This is our "converting" (or forwarding) assignment operator. It's pretty similar to our "converting" constructor above, we just use the swallow() function to call operator= of our TupleLeafs with corresponding elements from OtherTuple

Lines 42-46:

We need to define the "standard" assignment operator, too, because we explicitly disabled the standard operator= in our TupleLeaf (we only use the forwarding assignment operator), so the compiler cannot create the default assignment operator for us (as that would use TupleLeaf's default assignment operator, too).

Lines 48-51:

TupleImpl::swap() swaps each leaf piecewise using the swallow() trick.

Note: The swallow() implementation presented here processes the arguments in implementation-defined order. We could force left-to-right evaluation though by turning swallow into a struct with a variadic constructor and using brace-init like this: swallow{(foo(Args), 0)...}. Also note the use of the comma operator in this expansion: using this method to call swallow lets us use even void functions (no need for the trickery with the internal swap function above).

Some SFINAE helpers: TupleLike, TupleConvertible and TupleAssignable

The following templates will be used by our final Tuple class to disable some template instantiations (via SFINAE).

// TupleLike

template <typename T_>
struct TupleLike 
        : public false_type {
};

template <typename T_>
struct TupleLike<const T_>
        : public TupleLike<T_> {
};

template <typename T_>
struct TupleLike<volatile T_>
        : public TupleLike<T_> {
};

template <typename T_>
struct TupleLike<const volatile T_>
        : public TupleLike<T_> {
};

template <typename... Ts_>
struct TupleLike<Tuple<Ts_...>>
        : public true_type {
};

template <typename... Ts_>
struct TupleLike<TupleTypes<Ts_...>>
        : public true_type {
};

template <typename... Ts_>
struct TupleLike<std::tuple<Ts_...>>
        : public true_type {
};

template <typename First_, typename Second_>
struct TupleLike<std::pair<First_, Second_>>
        : public true_type {
};

template <typename T_, size_t N_>
struct TupleLike<std::array<T_, N_>>
        : public true_type {
};

TupleLike is a simple traits-template to check if the given type can be handled like a tuple, that is: tuple_size, tuple_element and get will work with it. The default implementation just inherits std::false_type, then we specialize it for our final Tuple, our internal TupleTypes and the standard tuple-like classes (std::tuple, std::pair and std::array).

// TupleConvertible

template <bool IsSameSize_, typename From_, typename To_>
struct TupleConvertibleImpl
        :  public false_type {
};

template <typename From0_, typename... FromRest_,
        typename To0_, typename... ToRest_>
struct TupleConvertibleImpl<true, TupleTypes<From0_, FromRest_...>,
            TupleTypes<To0_, ToRest_...>>
        : public integral_constant<bool,
            is_convertible<From0_, To0_>::value &&
            TupleConvertibleImpl<true, TupleTypes<FromRest_...>,
                TupleTypes<ToRest_...>>::value> {
};

template <>
struct TupleConvertibleImpl<true, TupleTypes<>, TupleTypes<>>
        : public true_type {
};

template <typename From_, typename To_,
         bool = TupleLike<typename remove_reference<From_>::type>::value,
         bool = TupleLike<typename remove_reference<To_>::type>::value>
struct TupleConvertible
        : public false_type {
};

template<typename From_, typename To_>
struct TupleConvertible<From_, To_, true, true>
        : public TupleConvertibleImpl<
            TupleSize<typename remove_reference<From_>::type>::value
                == TupleSize<typename remove_reference<To_>::type>::value,
            typename MakeTupleTypes<From_>::type,
            typename MakeTupleTypes<To_>::type> {
};

TupleConvertible is similar to std::is_convertible: it just checks that each tuple element of From_ is convertible to the corresponding element of To_. The default TupleConvertible template inherits std::false_type (lines 23-28). The two bool template parameters are defaulted to true if From_ and To_ are both TupleLike. We then specialize this template for the case when both are indeed tuple-like and defer the work to TupleConvertibleImpl (lines 30-37). We need this trick, because our TupleConvertibleImpl's first parameter is a bool indicating that From_ and To_ have the same number of elements. We check that with TupleSize, but it would blow up for non-tuple-like types, hence we can only use it when we're sure that both From_ and To_ are indeed tuple-like.

Once we get the size-match handled, TupleConvertibleImpl is pretty straightforward: we start with a default false_type (lines 3-6), then specialize for same-size tuples. This checks if the first elements are convertible then recursively checks the rest of the elements (lines 8-16).
The stop condition is when we reach empty TupleTypes<>, which are considered convertible (lines 18-21).

TupleAssignable is just like TupleConvertible, but we're using std::is_assignable in place of std::is_convertible:

// TupleAssignable

template <bool IsSameSize_, typename Target_, typename From_>
struct TupleAssignableImpl
        :  public false_type {
};

template <typename Target0_, typename... TargetRest_,
         typename From0_, typename... FromRest_>
struct TupleAssignableImpl<true, TupleTypes<Target0_, TargetRest_...>,
            TupleTypes<From0_, FromRest_...>>
        : public integral_constant<bool,
            is_assignable<Target0_, From0_>::value &&
            TupleAssignableImpl<true, TupleTypes<TargetRest_...>,
                TupleTypes<FromRest_...>>::value> {
};

template <>
struct TupleAssignableImpl<true, TupleTypes<>, TupleTypes<>>
        : public true_type {
};

template <typename Target_, typename From_,
         bool = TupleLike<typename remove_reference<Target_>::type>::value,
         bool = TupleLike<typename remove_reference<From_>::type>::value>
struct TupleAssignable
        : public false_type {
};

template<typename Target_, typename From_>
struct TupleAssignable<Target_, From_, true, true>
        : public TupleAssignableImpl<
            TupleSize<typename remove_reference<Target_>::type>::value
                == TupleSize<typename remove_reference<From_>::type>::value,
            typename MakeTupleTypes<Target_>::type,
            typename MakeTupleTypes<From_>::type> {
};

Helper templates for the relational operators: TupleEqual and TupleLess

The last detail (pun intended) we need are two helper templates to evaluate equals and less-than for tuples:

// TupleEqueal

template <size_t I_>
struct TupleEqual {
    template <typename Tuple1_, typename Tuple2_>
    bool operator()(const Tuple1_& t1, const Tuple2_& t2) {
        return TupleEqual<I_ - 1>()(t1, t2) &&
            get<I_ - 1>(t1) == get<I_ - 1>(t2);
    }
};

template<>
struct TupleEqual<0> {
    template <typename Tuple1_, typename Tuple2_>
    bool operator()(const Tuple1_&, const Tuple2_&) {
        return true;
    }
};

// TupleLess

template <size_t I_>
struct TupleLess {
    template <typename Tuple1_, typename Tuple2_>
    bool operator()(const Tuple1_& t1, const Tuple2_& t2) {
        return TupleLess<I_ - 1>()(t1, t2) ||
            (!TupleLess<I_ - 1>()(t2, t1) && get<I_ - 1>(t1) < get<I_ - 1>(t2));
    }
};

template<>
struct TupleLess<0> {
    template <typename Tuple1_, typename Tuple2_>
    bool operator()(const Tuple1_&, const Tuple2_&) {
        return false;
    }
};

These are the usual recursive templates parametrized on the number of tuple elements, that define an operator() to evaluate the relation for tuple elements up to the given index. The stop condition for both recursions is when I_ == 0, where TupleEqual return true and TupleLess returns false.

After the optimizer is done with the code, a call like

TupleEqual<2>()(tuple1, tuple2)

ends up as if we had hand-written

get<0>(tuple1) == get<0>(tuple2) && get<1>(tuple1) == get<1>(tuple2).

Tuple

Finally we can leave the detail namespace and put everything together in our final Tuple template:

// tuple_size

template <typename Tuple_>
class tuple_size : public detail::TupleSize<Tuple_> {
};

// tuple_element

template <size_t I_, typename Tuple_>
class tuple_element : public detail::TupleElement<I_, Tuple_> {
};

// Tuple

template <typename... Ts_>
class Tuple  {
    typedef detail::TupleImpl<typename detail::MakeTupleIndexes<sizeof...(Ts_)>::type, Ts_...> Impl;
    Impl impl_;

    template <size_t I, typename... Ts>
    friend
    typename tuple_element<I, Tuple<Ts...>>::type&
    get(Tuple<Ts...>& t);

    template <size_t I, typename... Ts>
    friend
    const typename tuple_element<I, Tuple<Ts...>>::type&
    get(const Tuple<Ts...>& t);

    template <size_t I, typename... Ts>
    friend
    typename tuple_element<I, Tuple<Ts...>>::type&&
    get(Tuple<Ts...>&& t);

public:
    explicit Tuple(const Ts_&... t)
            : impl_(typename detail::MakeTupleIndexes<sizeof...(Ts_)>::type(),
                   typename detail::MakeTupleTypes<Tuple, sizeof...(Ts_)>::type(),
                   typename detail::MakeTupleIndexes<0>::type(),
                   typename detail::MakeTupleTypes<Tuple, 0>::type(),
                   t...) {
    }

    template <typename... Us, typename std::enable_if<
                    sizeof...(Us) <= sizeof...(Ts_) &&
                    detail::TupleConvertible<
                        typename detail::MakeTupleTypes<Tuple<Us...>>::type,
                        typename detail::MakeTupleTypes<Tuple,
                            sizeof...(Us) < sizeof...(Ts_)
                                ? sizeof...(Us)
                                : sizeof...(Ts_)>::type>::value,
                    bool>::type = false>
    explicit Tuple(Us&&... u)
            : impl_(typename detail::MakeTupleIndexes<sizeof...(Us)>::type(),
                   typename detail::MakeTupleTypes<Tuple, sizeof...(Us)>::type(),
                   typename detail::MakeTupleIndexes<sizeof...(Ts_), sizeof...(Us)>::type(),
                   typename detail::MakeTupleTypes<Tuple, sizeof...(Ts_), sizeof...(Us)>::type(),
                   std::forward<Us>(u)...) {
    }
                    
    
    template <typename OtherTuple, typename std::enable_if<
            detail::TupleConvertible<OtherTuple, Tuple>::value,
            bool>::type = false>
    Tuple(OtherTuple&& t)
            : impl_(std::forward<OtherTuple>(t)) {
    }

    template <typename OtherTuple, typename std::enable_if<
            detail::TupleAssignable<Tuple, OtherTuple>::value,
            bool>::type = false>
    Tuple& operator=(OtherTuple&& t) {
        impl_.operator=(std::forward<OtherTuple>(t));
        return *this;
    }

    void swap(Tuple& t) {
        impl_.swap(t.impl_);
    }
};

// Empty Tuple

template <>
class Tuple<> {
public:
    Tuple() {
    }

    template <typename OtherTuple, typename std::enable_if<
            detail::TupleConvertible<OtherTuple, Tuple>::value,
            bool>::type = false>
    Tuple(OtherTuple&&) {
    }

    template <typename OtherTuple, typename std::enable_if<
            detail::TupleAssignable<Tuple, OtherTuple>::value,
            bool>::type = false>
    Tuple& operator=(OtherTuple&&) {
        return *this;
    }

    void swap(Tuple&) {
    }
};

// get

template <size_t I, typename... Ts>
inline
typename tuple_element<I, Tuple<Ts...>>::type&
get(Tuple<Ts...>& t) {
    typedef typename tuple_element<I, Tuple<Ts...>>::type Type;
    return static_cast<detail::TupleLeaf<I, Type>&>(t.impl_).get();
}

template <size_t I, typename... Ts>
inline
const typename tuple_element<I, Tuple<Ts...>>::type&
get(const Tuple<Ts...>& t) {
    typedef typename tuple_element<I, Tuple<Ts...>>::type Type;
    return static_cast<const detail::TupleLeaf<I, Type>&>(t.impl_).get();
}

template <size_t I, typename... Ts>
inline
typename tuple_element<I, Tuple<Ts...>>::type&&
get(Tuple<Ts...>&& t) {
    typedef typename tuple_element<I, Tuple<Ts...>>::type Type;
    return static_cast<Type&&>(static_cast<detail::TupleLeaf<I, Type>&&>(t.impl_).get());
}

// swap 

template <typename... Ts>
inline
void swap(Tuple<Ts...>& a, Tuple<Ts...>& b) {
    a.swap(b);
}

// relational operators

template <typename... T1s_, typename... T2s_>
inline bool operator==(const Tuple<T1s_...>& t1, const Tuple<T2s_...>& t2) {
    return detail::TupleEqual<sizeof...(T1s_)>()(t1, t2);
}

template <typename... T1s_, typename... T2s_>
inline bool operator!=(const Tuple<T1s_...>& t1, const Tuple<T2s_...>& t2) {
    return !(t1 == t2);
}

template <typename... T1s_, typename... T2s_>
inline bool operator<(const Tuple<T1s_...>& t1, const Tuple<T2s_...>& t2) {
    return detail::TupleLess<sizeof...(T1s_)>()(t1, t2);
}

template <typename... T1s_, typename... T2s_>
inline bool operator>(const Tuple<T1s_...>& t1, const Tuple<T2s_...>& t2) {
    return t2 < t1;
}

template <typename... T1s_, typename... T2s_>
inline bool operator<=(const Tuple<T1s_...>& t1, const Tuple<T2s_...>& t2) {
    return !(t2 < t1);
}

template <typename... T1s_, typename... T2s_>
inline bool operator>=(const Tuple<T1s_...>& t1, const Tuple<T2s_...>& t2) {
    return !(t1 < t2);
}

Lines 1-11:

The user-visible tuple_size and tuple_element templates just inherit from the corresponding "hidden" templates. Nothing fancy here.

Lines 13-18:

The generic Tuple template builds a detail::TupleImpl and holds that as its only data member.

Lines 20-33 and 107-131:

The get() functions are made friends so that they can access our private impl_ member. The three versions return reference, const-reference or rvalue-reference types depending on the type of the input parameter. We get the desired element by converting our impl_ member to the correct TupleLeaf type via a simple static_cast.

Lines 36-42:

This is the simplest of our constructors: it takes its parameters as const references, matching both the number and exact type of our tuple members. We pass these along to our TupleImpl's constructor, and since we fill out all parameters in the first set, the second set of parameters is empty (empty indexes and types).

Lines 44-59:

This constructor is responsible for constructing a Tuple from values convertible to our tuple-elements. We allow less parameters than the number of elements we hold, the rest of the elements will be default constructed. As a special case, if the number of supplied parameters is 0, then all of our tuple-elements will be default constructed, so this constructor acts as our default constructor, too. This constructor is enabled only if the supplied types are convertible to the corresponding types of our Tuple. This is checked via the above defined TupleConvertible template after creating suitable TupleTypes from the supplied parameter pack.

Lines 62-67:

Our last constructor takes a single tuple-like argument, and forwards it to the corresponding TupleImpl constructor, thus this constructor is both our copy and move constructor, depending on context. This constructor is enabled only if OtherTuple is convertible to our Tuple. This implicitly checks that OtherTuple is in fact tuple-like. Without this tuple-like check there would be an ambiguity (or other compile error) if we tried to instantiate our Tuple with a single (non-tuple) parameter.

Lines 69-75:

The forwarding move/copy assignment operator is analogous to the copy/move constructor above, the only difference is that instead of checking for TupleConvertible, we check for TupleAssignable to enable this operator.

Lines 77-79, 103-104 and 133-139:

The swap() member function just calls TupleImpl::swap() (the implementation for empty tuples is of course a no-op). We also define a standard swap() override, so that it could be picked up by ADL when needed.

Lines 82-105:

The empty Tuple<> doesn't need to hold any data at all, so we specialize our template for that case to avoid unnecessary memory waste. The constructors are of course simpler than in the general case. We also won't need get functions, and our swap is a no-op.

Lines 141-171:

The two basic relational operators (equals and less-than) are implemented via the corresponding helper templates, the rest are just built using these two, as usual.

Finishing touches: integration with the std namespace

In the last section we make our Tuple drop-in compatible with std::tuple by specializing the std::tuple_size and std::tuple_element templates for it, and providing overloads for std::get by lifting the migl2::get functions into the std namespace:

namespace std {

// tuple_size

template <typename... Ts_>
class tuple_size<migl2::Tuple<Ts_...>> 
        : public migl2::tuple_size<migl2::Tuple<Ts_...>> {
};

template <typename... Ts_>
class tuple_size<const migl2::Tuple<Ts_...>> 
        : public migl2::tuple_size<const migl2::Tuple<Ts_...>> {
};

template <typename... Ts_>
class tuple_size<volatile migl2::Tuple<Ts_...>> 
        : public migl2::tuple_size<volatile migl2::Tuple<Ts_...>> {
};

template <typename... Ts_>
class tuple_size<const volatile migl2::Tuple<Ts_...>> 
        : public migl2::tuple_size<const volatile migl2::Tuple<Ts_...>> {
};

// tuple_element

template <size_t I_, typename... Ts_>
class tuple_element<I_, migl2::Tuple<Ts_...>> 
        : public migl2::tuple_element<I_, migl2::Tuple<Ts_...>> {
};

template <size_t I_, typename... Ts_>
class tuple_element<I_, const migl2::Tuple<Ts_...>> 
        : public migl2::tuple_element<I_, const migl2::Tuple<Ts_...>> {
};

template <size_t I_, typename... Ts_>
class tuple_element<I_, volatile migl2::Tuple<Ts_...>> 
        : public migl2::tuple_element<I_, volatile migl2::Tuple<Ts_...>> {
};

template <size_t I_, typename... Ts_>
class tuple_element<I_, const volatile migl2::Tuple<Ts_...>> 
        : public migl2::tuple_element<I_, const volatile migl2::Tuple<Ts_...>> {
};

using migl2::get;

} // namespace std

Disclaimer

I'm returning to C++ after 9 years of Java development, so take everything presented here with a grain of salt, and please point out any mistakes in the comments section below, so that I can fix them and not confuse others. As mentioned in the preamble, this code is based on the tuple implementation in libc++, which was created by Howard Hinnant, so hereby I thank him (and all other developers of libc++) for the inspiration.

The complete source for the above Tuple implementation can be found on bitbucket.