STL From Scratch - Pairs and Tuples Part #2

If this is your first time reading the series, you should first read the introduction. Otherwise, enjoy!

In this post (part 2 of 2) we will be implementing tuple. This is a long one (very long, so strap yourself in), and so for the sake of readability I won't be covering all of the source code; only the most important parts will be discussed. Those are, in order of their appearance, new type helpers and traits, the internal representation of tuple, the basics for the constructors for tuple, and the free functions operating on tuples. As always, you can find the complete source code for this post in the GitHub repository.

The first order of business is to implement a number of new type helpers and type traits that we'll need for our tuple implementation. The following helper types appear in stl/bits/type_helpers.hpp under namespace bits.

/*
 * Variadic template testing for boolean conjuction for
 * many instances of a template predicate.
 */
template <bool...>
struct fold_and;

template <>
struct fold_and <> : std::integral_constant <bool, true> {};

template <bool b, bool ... bs>
struct fold_and <b, bs...>
    : std::integral_constant <bool, b && fold_and <bs...>::value> {};

template <template <class> class Predicate, class ... Args>
struct predicate_and : fold_and <Predicate <Args>::value...> {};

/* Helper type for selecting uses_allocator construction for tuple nodes */
template <bool b>
struct uses_allocator_tag : std::integral_constant <bool, b> {};

template <class T, class Allocator>
using make_uses_allocator_tag = uses_allocator_tag <
    std::uses_allocator <T, Allocator>::value
>

/* Selects the I'th type from a parameter pack. */
template <std::size_t, class ...>
struct select_type_helper;

template <class T, class ... Ts>
struct select_type_helper <0, T, Ts...>
{
    using type = T;
};

template <std::size_t I, class T, class ... Ts>
struct select_type_helper <I, T, Ts...> : select_type_helper <I - 1, Ts...>
{};

template <std::size_t I, class ... Ts>
struct select_type
{
    static_assert (
        I < sizeof... (Ts),
        "invalid index into template type parameter pack"
    );

    using type = typename select_type_helper <I, Ts...>::type;
};

/* Determines the index of a type in a parameter pack. */
template <std::size_t, class, class...>
struct type_index_helper;

template <std::size_t I, class T>
struct type_index_helper <I, T>
{
    static_assert (sizeof (T) == 0, "type not found in parameter pack");
};

template <std::size_t I, class T, class ... Ts>
struct type_index_helper <I, T, T, Ts...>
    : std::integral_constant <std::size_t, I>
{};

template <std::size_t I, class T, class U, class ... Ts>
struct type_index_helper <I, T, U, Ts...>
    : type_index_helper <I + 1, T, Ts...>
{};

template <class T, class ... Ts>
struct type_index : type_index_helper <0, T, Ts...> {};

/*
 * Counts the number of times that a type appears in a parameter pack.
 */
template <std::size_t, class, class...>
struct type_multiplicity_helper;

template <std::size_t M, class T>
struct type_multiplicity_helper <M, T>
    : std::integral_constant <std::size_t, M>
{};

template <std::size_t M, class T, class... Ts>
struct type_multiplicity_helper <M, T, T, Ts...>
    : std::integral_constant <
        std::size_t, type_multiplicity_helper <M + 1, T, Ts...>::value
    >
{};

template <std::size_t M, class T, class U, class... Ts>
struct type_multiplicity_helper <M, T, U, Ts...>
    : std::integral_constant <
        std::size_t, type_multiplicity_helper <M, T, Ts...>::value
    >
{};

template <class T, class ... Ts>
struct type_multiplicity : type_multiplicity_helper <0, T, Ts...> {};

Now, in stl/bits/type_traits.hpp we need to implement uses_allocator, tuple_element, and tuple_size. The first simply inherits from std::true_type, as mandaded by the standard. While we're at it, the second and third traits will also be implemented for pair. Notice that we have to handle const/volatile qualifications in tuple_element.

/* Forward declaration of uses_allocator. */
template <class T, class Allocator>
struct uses_allocator;

/*
 * Implementation of uses_allocator for tuples. As per the spec it always
 * inherits from std::true_type.
 */
template <class ... Ts, class Allocator>
struct uses_allocator <tuple <Ts...>, Allocator> : std::true_type {};

namespace bits
{
    template <std::size_t I, class Tup>
    struct tuple_element_helper;

    template <std::size_t I, class ... Ts>
    struct tuple_element_helper <I, tuple <Ts...>>
    {
        static_assert (
            I < sizeof... (Ts), "invalid index into tuple type list"
        );

    private:
        template <std::size_t Idx, class ... Us>
        struct select_type;

        template <class U, class ... Us>
        struct select_type <0, U, Us...>
        {
            using type = U;
        };

        template <std::size_t Idx, class U, class ... Us>
        struct select_type <Idx, U, Us...> : select_type <Idx - 1, Us...> {};

    public:
        using type = typename select_type <I, Ts...>::type;
    };

    template <std::size_t I, class T1, class T2>
    struct tuple_element_helper <I, pair <T1, T2>>
    {
        static_assert (I == 0 || I == 1, "invalid index into pair type list");
        using type = typename std::conditional <I == 0, T1, T2>::type;
    };
}   // namespace bits

/* Implementation of tuple_element and tuple_size for tuples and pairs. */
template <std::size_t, class>
class tuple_element;

template <std::size_t I, class ... Ts>
class tuple_element <I, tuple <Ts...>>
{
public:
    using type = typename bits::tuple_element_helper <
        I, tuple <Ts...>
    >::type;
};

template <std::size_t I, class T1, class T2>
class tuple_element <I, pair <T1, T2>>
{
public:
    using type = typename bits::tuple_element_helper <
        I, pair <T1, T2>
    >::type;
};

template <std::size_t I, class ... Ts>
class tuple_element <I, tuple <Ts...> const>
{
public:
    using type = typename std::add_const <
        typename bits::tuple_element_helper <
            I, tuple <Ts...>
        >::type
    >::type;
};

template <std::size_t I, class T1, class T2>
class tuple_element <I, pair <T1, T2> const>
{
public:
    using type = typename std::add_const <
        typename bits::tuple_element_helper <
            I, pair <T1, T2>
        >::type
    >::type;
};

template <std::size_t I, class ... Ts>
class tuple_element <I, tuple <Ts...> volatile>
{
public:
    using type = typename std::add_volatile <
        typename bits::tuple_element_helper <
            I, tuple <Ts...>
        >::type
    >::type;
};

template <std::size_t I, class T1, class T2>
class tuple_element <I, pair <T1, T2> volatile>
{
public:
    using type = typename std::add_volatile <
        typename bits::tuple_element_helper <
            I, pair <T1, T2>
        >::type
    >::type;
};

template <std::size_t I, class ... Ts>
class tuple_element <I, tuple <Ts...> const volatile>
{
public:
    using type = typename std::add_cv <
        typename bits::tuple_element_helper <
            I, tuple <Ts...>
        >::type
    >::type;
};

template <std::size_t I, class T1, class T2>
class tuple_element <I, pair <T1, T2> const volatile>
{
public:
    using type = typename std::add_cv <
        typename bits::tuple_element_helper <
            I, pair <T1, T2>
        >::type
    >::type;
};

template <class Tup>
class tuple_size;

template <class ... Ts>
class tuple_size <tuple <Ts...>>
    : public std::integral_constant <std::size_t, sizeof... (Ts)> {};

template <class T1, class T2>
class tuple_size <pair <T1, T2>>
    : public std::integral_constant <std::size_t, 2> {};

template <class Tup>
class tuple_size <Tup const>
    : public std::integral_constant <std::size_t, tuple_size <Tup>::value>
{};

template <class Tup>
class tuple_size <Tup volatile>
    : public std::integral_constant <std::size_t, tuple_size <Tup>::value>
{};

template <class Tup>
class tuple_size <Tup const volatile>
    : public std::integral_constant <std::size_t, tuple_size <Tup>::value>
{};

For our implementation of tuple as well as for the tie free- function there is a special object ignore under namespace stl that needs to appear in the stl/tuple.hpp header. This type needs to be assignable to from objects of any type as a no-op. Since this is a useful behavior, we'll also make it constructible from objects of any type (later on we'll use this behavior to implement expression-eaters). The definition of the type will appear in stl/bits/ignore_type.hpp under namespace bits.

/* 
 * As per the spec this is a type such that any value can be assigned to it
 * with no effect. There is a single const object `ignore` of this type that
 * is to be declared in the <tuple> header.
 */
class ignore_type
{
public:
    ignore_type (void) noexcept {}
    ~ignore_type (void) noexcept {}

    /*
     * Construction from any type; it performs nothing and does not modify
     * its argument in any way.
     */
    template <typename T>
    ignore_type (T &&) noexcept {}

    /* default all the special constructors */
    ignore_type (ignore_type &&) noexcept      = default;
    ignore_type (ignore_type const &) noexcept = default;

    /* 
     * The required assignment operator; it performs nothing and does not
     * modify its argument in any way.
     */
    template <typename T>
    ignore_type const & operator= (T &&) const noexcept
    {
        return *this;
    }
};

Now in stl/tuple.hpp we'll declare a single const qualified object named ignore.

/* Our const ignore_type object. */
bits::ignore_type const ignore;

That's it for the type helpers and type traits. Now we can move on to implementing tuple itself. A common way to implement tuple is with an inheritance hierarchy. That is, the type tuple <T1, ..., Tn> will be implemented as a hierarchy of wrappers around each Ti, in order: tuple <T1,...,Tn> inherits from node <Tn>, which inherits from node <Tn-1>, which inherits from ..., all the way up to node <T1> (or something similar to that). This is not how we'll be implementing tuple. Instead, we can get awaay with a single* multiple inheritance.

* When I say single, I mean the implementation (where all the magic happens) has a single multiple inheritance, which tuple itself will inherit from.

Our first type to implement will be the wrapper around the template arguments to tuple. This type will take a single template type argument and one index (which we will use to differentiate it from other type nodes). This wrapper type will handle the various forms of construction of its member object. We'll place the following code in stl/tuple.hpp under namespace detail.

/*
 * This is a wrapper around a single type that implements construction of
 * its member object with or without uses-allocator construction,
 * appropriately detected by the tuple_impl class.
 * 
 * type_node structs appear in the multiple inheritence list for the
 * tuple_impl class.
 */
template <std::size_t I, class T>
struct type_node
{
    using member_type = T;
    member_type member;

    /*
     * For an explanation of the constructors and why they are qualified the
     * way they are, look below at the constructors for tuple itself.
     */
    constexpr type_node (void)
        noexcept (
            std::is_nothrow_default_constructible <member_type>::value
        )
        : member ()
    {}

    ~type_node (void) noexcept (std::is_nothrow_destructible <T>::value)
        = default;

    explicit constexpr
    type_node (member_type const & m)
        : member (m)
    {}

    template <class U>
    explicit constexpr
    type_node (U && u)
        : member (stl::forward <U> (u))
    {}

    template <class U>
    constexpr type_node (type_node <I, U> const & node)
        : member (node.member)
    {}

    template <class U>
    constexpr type_node (type_node <I, U> && node)
        : member (stl::forward <U> (node.member))
    {}

    /* defaulted copy and move construction */
    constexpr type_node (type_node const &) = default;
    constexpr type_node (type_node &&) = default;

    /*
     * Constructors for uses-allocator construction. There are two of each
     * in order to faciliate ease of use in calling these constructors; one
     * taking a bits::uses_allocator_tag <true> arguent, and the other
     * taking a bits::uses_allocator_tag <false> argument, indicating,
     * respectively, that they member object is to be constructed with or
     * without the given allocator.
     *
     * Since the tuple class checks for constructibility of the member
     * objects with or without the allocator we need not perform any
     * checks here.
     */
    template <class Allocator>
    type_node (bits::uses_allocator_tag <true>, Allocator const & alloc)
        : member (alloc)
    {}

    template <class Allocator>
    type_node (bits::uses_allocator_tag <false>, Allocator const &)
        : member ()
    {}

    template <class Allocator>
    type_node (bits::uses_allocator_tag <true>,
               Allocator const & alloc,
               member_type const & m)
        : member (m, alloc)
    {}

    template <class Allocator>
    type_node (bits::uses_allocator_tag <false>,
               Allocator const &,
               member_type const & m)
        : member (m)
    {}

    template <class Allocator>
    type_node (bits::uses_allocator_tag <true>,
               Allocator const & alloc,
               type_node const & node)
        : member (node.member, alloc)
    {}

    template <class Allocator>
    type_node (bits::uses_allocator_tag <false>,
               Allocator const &,
               type_node const & node)
        : member (node.member)
    {}

    template <class Allocator>
    type_node (bits::uses_allocator_tag <true>,
               Allocator const & alloc,
               type_node && node)
        : member (stl::move (node.member), alloc)
    {}

    template <class Allocator>
    type_node (bits::uses_allocator_tag <false>,
               Allocator const &,
               type_node && node)
        : member (stl::move (node.member))
    {}

    template <class Allocator, class U>
    type_node (bits::uses_allocator_tag <true>,
               Allocator const & alloc,
               U && u)
        : member (stl::forward <U> (u), alloc)
    {}

    template <class Allocator, class U>
    type_node (bits::uses_allocator_tag <false>,
               Allocator const &,
               U && u)
        : member (stl::forward <U> (u))
    {}

    template <class Allocator, class U>
    type_node (bits::uses_allocator_tag <true>,
               Allocator const & alloc,
               type_node <I, U> const & node)
        : member (node.member, alloc)
    {}

    template <class Allocator, class U>
    type_node (bits::uses_allocator_tag <false>,
               Allocator const &,
               type_node <I, U> const & node)
        : member (node.member)
    {}

    template <class Allocator, class U>
    type_node (bits::uses_allocator_tag <true>,
               Allocator const & alloc,
               type_node <I, U> && node)
        : member (stl::forward <U> (node.member), alloc)
    {}

    template <class Allocator, class U>
    type_node (bits::uses_allocator_tag <false>,
               Allocator const &,
               type_node <I, U> && node)
        : member (stl::forward <U> (node.member))
    {}
};

Now we can write the tuple_impl class that will handle all of the template magic. From tuple this template will receive the list of template arguments Ts ... along with an index sequence into this list. This lets us to a number of cool things, as we'll see below. Again, this code is under namespace detail.

template <class, class ...>
class tuple_impl;

/*
 * This is our implementation of the inheritence for tuples. Instead of an
 * inheritence hierarchy we'll implement tuples with a single multiple
 * inheritence list. This is not only a fun application of multiple
 * inheritence, it is also a fun application of parameter pack expansion
 * (and in more ways than one). First, we can use it to construct a multiple
 * inheritence list for the type nodes. Second, we can use parameter pack
 * expansion to create delegating constructor lists to each type node.
 *
 * Since this takes an parameter packs std::size_t ... I and class ... Ts as
 * template arguments we are free to expand them inline for each constructor
 * with no extra work involved on our part.
 */
template <std::size_t ... I, class ... Ts>
class tuple_impl <stl::index_sequence <I...>, Ts...>
    : public type_node <I, Ts>...
{
    using size = std::integral_constant <std::size_t, sizeof... (Ts)>

    template <class ... Us>
    using rebind = tuple_impl <stl::index_sequence <I...>, Us...>
public:
    /*
     * The source for the constructor specifications can be found at
     * en.cppreference.com/w/cpp/tuple/tuple
     *
     * As always, we'll be using the C++14 signatures.
     */

    /*
     * The tuple of two elements is handled by enable_if's for the
     * appropriate construction and assignment by/from pairs. 
     */

    /*
     * Default constructor is requires that all Ts... are  themselves
     * default constructible.
     */
    constexpr tuple_impl (void) : type_node <I, Ts> ()... {}
    ~tuple_impl (void)
        noexcept (
            bits::predicate_and <std::is_nothrow_destructible, Ts...>::value
        )
        = default;

    /*
     * Copy construction of each node from values inhabiting the full list
     * of template types.
     */
    explicit constexpr tuple_impl (Ts const &... ts)
        : type_node <I, Ts> (ts)...
    {}

    /*
     * Converting construction of each member object from the values in
     * us..., passed to constructors as stl::forward <Ui> (ui) for each i.
     */
    template <class ... Us>
    explicit constexpr tuple_impl (Us && ... us)
        : type_node <I, Ts> (stl::forward <Us> (us))...
    {}

    /*
     * Converting construction of each member object from the member objects
     * in other, passed to constructors as if by stl::get <i> (other) for
     * each i.
     *
     * This constructor delegates to the converting constructor taking a
     * list of references to the const member objects of other.
     */
    template <class ... Us>
    constexpr tuple_impl (rebind <Us...> const & other)
        : tuple_impl (other.template type_node <I, Us>::member...)
    {}

    /*
     * Converting construction of each member object from the member objects
     * in other, passed to constructors as if by
     * stdl::forward <Ui> (stl::get <i> (other)) for each i.
     *
     * This constructor delegates to the converting constructor taking a
     * list of forwarding references to the member objects of other.
     */
    template <class ... Us>
    constexpr tuple_impl (rebind <Us...> && other)
        : tuple_impl (
            stl::forward <Us> (other.template type_node <I, Us>::member)...
        )
    {}

    /* Defaulted copy and move constructors. */
    tuple_impl (tuple_impl const &) = default;
    tuple_impl (tuple_impl &&)      = default;

    /*
     * Default construction by uses-allocator construction for each member
     * object, appropriately detected by the constructor for each inherited
     * node.
     */
    template <class Allocator>
    tuple_impl (std::allocator_arg_t, Allocator const & alloc)
        : type_node <I, Ts> (
            bits::make_uses_allocator_tag <Ts, Allocator> {}, alloc
        )...
    {}

    /*
     * Copy construction by uses-allocator construction for each member
     * object, appropriately detected by the constructor for each inherited
     * node.
     */
    template <class Allocator>
    tuple_impl (std::allocator_arg_t,
                Allocator const & alloc,
                Ts const & ... ts)
        : type_node <I, Ts> (
            bits::make_uses_allocator_tag <Ts, Allocator> {}, alloc, ts
        )...
    {}

    /*
     * Converting construction by uses-allocator construction for each
     * member object from the values in us..., passed to constructos by
     * stl::forward <Ui> (ui) for each i, appropriately detected by the
     * constructor for each inherited node.
     */
    template <class Allocator, class ... Us>
    tuple_impl (std::allocator_arg_t, Allocator const & alloc, Us && ... us)
        : type_node <I, Ts> (
            bits::make_uses_allocator_tag <Ts, Allocator> {},
            alloc,
            stl::forward <Us> (us)
        )...
    {}

    /*
     * Copy construction by uses-allocator construction for each member
     * object, passed to constructors as if by stl::get <i> (other) for each
     * i, appropriately detected by the constructor for each inherited node.
     *
     * This constructor delegates to the uses-allocator constructor taking
     * a list of references to the const member objects of other.
     */
    template <class Allocator>
    tuple_impl (std::allocator_arg_t,
                Allocator const & alloc,
                tuple_impl const & other)
        : tuple_impl (
            std::allocator_arg_t {},
            alloc,
            other.template type_node <I, Ts>::member...
        )
    {}

    /*
     * Move construction by uses-allocator construction for each member
     * object, passed to constructors as if by
     * stl::move (stl::get <i> (other)) for each i, appropriately detected
     * by the constructor for each inherited node.
     *
     * This constructor delegates to the uses-allocator constructor taking
     * a list of forwarding references to the member objects of other.
     */
    template <class Allocator>
    tuple_impl (std::allocator_arg_t,
                Allocator const & alloc,
                tuple_impl && other)
        : tuple_impl (
            std::allocator_arg_t {},
            alloc,
            stl::forward <Ts> (other.template type_node <I, Ts>::member)...
        )
    {}

    /*
     * Converting construction by uses-allocator construction of each member
     * object from the member objects in other, passed to constructors as if
     * by stl::get <i> (other) for each i.
     *
     * This constructor delegates to the converting uses-allocator
     * constructor taking a list of references to the const member objects
     * of other.
     */
    template <class Allocator, class ... Us>
    tuple_impl (std::allocator_arg_t,
                Allocator const & alloc,
                rebind <Us...> const & other)
        : tuple_impl (
            std::allocator_arg_t {},
            alloc,
            other.template type_node <I, Us>::member...
        )
    {}

    /*
     * Converting construction by uses-allocator construction of each member
     * object from the member objects in other, passed to constructors as if
     * by stdl::forward <Ui> (stl::get <i> (other)) for each i.
     *
     * This constructor delegates to the converting uses-allocator
     * constructor taking a list of forwarding references to the member
     * objects of other.
     */
    template <class Allocator, class ... Us>
    tuple_impl (std::allocator_arg_t,
                Allocator const & alloc,
                rebind <Us...> && other)
        : tuple_impl (
            std::allocator_arg_t {},
            alloc,
            stl::forward <Us> (other.template type_node <I, Us>::member)...
        )
    {}

    /*
     * Copy assignment operator of each member object by the corresponding
     * member object of other.
     */
    tuple_impl & operator= (tuple_impl const & other)
    {
        bits::ignore_type _expression_eater [] = {
            ((type_node <I, Ts>::member =
                other.template type_node <I, Ts>::member),
             I)...
        };

        (void) _expression_eater;
        return *this;
    }

    /*
     * Move assignment operator of each member object by the corresponding
     * member object of other, using move semantics.
     */
    tuple_impl & operator= (tuple_impl && other)
        noexcept (
            bits::predicate_and <
                std::is_nothrow_move_assignable, Ts...
            >::value
        )
    {
        bits::ignore_type _expression_eater [] = {
            ((type_node <I, Ts>::member =
                stl::move (other.template type_node <I, Ts>::member)),
             I)...
        };

        (void) _expression_eater;
        return *this;
    }

    /*
     * Converting copy assignment operator of each member object by the
     * corresponding member object of other.
     */
    template <class ... Us>
    tuple_impl & operator= (rebind <Us...> const & other)
    {
        bits::ignore_type _expression_eater [] = {
            ((type_node <I, Ts>::member =
                other.template type_node <I, Us>::member),
             I)...
        };

        (void) _expression_eater;
        return *this;
    }

    /*
     * Converting move assignment operator of each member object by the
     * corresponding member object of other, using move semantics.
     */
    template <class ... Us>
    tuple_impl & operator= (rebind <Us...> && other)
    {
        bits::ignore_type _expression_eater [] = {
            ((type_node <I, Ts>::member = stl::forward <Us> (
                other.template type_node <I, Us>::member
            )), I)...
        };

        (void) _expression_eater;
        return *this;
    }

    /*
     * Converting copy assignment operator of each member object by the
     * corresponding member objects of the pair p, from first to second.
     */
    template <class U1, class U2>
    tuple_impl & operator= (pair <U1, U2> const & p)
    {
        bits::ignore_type _expression_eater [] = {
            ((type_node <I, Ts>::member = stl::get <I> (p)), I)...
        };

        (void) _expression_eater;
        return *this;
    }

    /*
     * Converting move assignment operator of each member object by the
     * corresponding member objects of the pair p, from first to second,
     * using move semantics.
     */
    template <class U1, class U2>
    tuple_impl & operator= (pair <U1, U2> && p) noexcept
    {
        bits::ignore_type _expression_eater [] = {
            ((type_node <I, Ts>::member = stl::get <I> (stl::move (p))),
             I)...
        };

        (void) _expression_eater;
        return *this;
    }

    /*
     * Swaps each member object with the corresponding member object of
     * other.
     */
    void swap (tuple_impl & other)
        noexcept (
            bits::fold_and <
                noexcept (
                    swap (stl::declval <Ts &> (), stl::declval <Ts &> ())
                )...
            >::value
        )
    {
        using stl::swap;

        bits::ignore_type _expression_eater [] = {
            ((swap (type_node <I, Ts>::member,
                    other.template type_node <I, Ts>::member)), I)...
        };
        (void) _expression_eater;
    }

    /* 
     * Here are our implementations of operator== and operator<. As per the
     * spec we must short-circuit evaluation, which means we have to do a
     * bit of leg-work with helper templates.
     */
    template <std::size_t, class ...>
    struct compare;

    template <class ... Us>
    struct compare <size::value - 1, Us...>
    {
        static constexpr bool
            compare_eq (tuple_impl const lhs, rebind <Us...> const & rhs)
            noexcept
        {
            using t_type = typename bits::select_type <
                size::value - 1, Ts...
            >::type;
            using u_type = typename bits::select_type <
                size::value - 1, Us...
            >::type;

            return lhs.template type_node <size::value - 1, t_type>::member
                == rhs.template type_node <size::value - 1, u_type>::member;
        }

        static constexpr bool
            compare_lt (tuple_impl const lhs, rebind <Us...> const & rhs)
            noexcept
        {
            using t_type = typename bits::select_type <
                size::value - 1, Ts...
            >::type;
            using u_type = typename bits::select_type <
                size::value - 1, Us...
            >::type;

            return lhs.template type_node <size::value - 1, t_type>::member
                 < rhs.template type_node <size::value - 1, u_type>::member;
        }
    };

    template <std::size_t Idx, class ... Us>
    struct compare
    {
        static constexpr bool
            compare_eq (tuple_impl const lhs, rebind <Us...> const & rhs)
            noexcept
        {
            using t_type = typename bits::select_type <Idx, Ts...>::type;
            using u_type = typename bits::select_type <Idx, Us...>::type;

            return (lhs.template type_node <Idx, t_type>::member
                    == rhs.template type_node <Idx, u_type>::member)
                 ? compare <Idx + 1, Us...>::compare_eq (lhs, rhs)
                 : false;
        }

        static constexpr bool
            compare_lt (tuple_impl const lhs, rebind <Us...> const & rhs)
            noexcept
        {
            using t_type = typename bits::select_type <Idx, Ts...>::type;
            using u_type = typename bits::select_type <Idx, Us...>::type;

            return (lhs.template type_node <Idx, t_type>::member
                    < rhs.template type_node <Idx, u_type>::member)
                 ? true
                 : (rhs.template type_node <Idx, t_type>::member
                    < lhs.template type_node <Idx, u_type>::member)
                 ? false
                 : compare <Idx + 1, Us...>::compare_lt (lhs, rhs);
        }
    };

    template <class ... Us>
    constexpr bool operator== (rebind <Us...> const & rhs) const noexcept
    {
        return compare <0, Us...>::compare_eq (*this, rhs);
    }

    template <class ... Us>
    constexpr bool operator< (rebind <Us...> const & rhs) const noexcept
    {
        return compare <0, Us...>::compare_lt (*this, rhs);
    }
};

That's the gist of our tuple implementation. The actual tuple template has three specializations: an empty tuple, a tuple of two elements (which admits constructors and assignment operators taking pair objects as arguments), and the general case tuple. Since these are all similar to one another, and to the tuple_impl class I won't repeat the code here. You can, of course, see the full source in the GitHub repository.

One important thing about the tuple implementation that needs to be mentioned is that the tuple constructors perform all of the enable_if checks on their arguments ahead-of-time. Most often these are checking that a parameter pack Us && ... us is of the correct length, although there are a number of other checks that are made. You should check all this out in the source code if you're interested.

The only thing that I will implement here is the following. Three structs under namespace detail are implemented as friends of tuple to allow access into tuple's representation. They are: base_access <>, which performs object-slicing of tuples into tuple_impls; get_impl <>, which performs the work of the free-function get operations; and compare_impl, which object-slices tuples and forwards to the tuple_impl member comparison operators that perform the actual work of the lexicographic comparisons. Here's the code for these, again under namespace detail.

template <class ... Ts>
struct base_access <tuple <Ts...>>
{
    using base = typename tuple <Ts...>::base;

    /*
     * These are helper methods for object-slicing references to our tuple
     * into references to the tuple_impl.
     */
    static base & slice (tuple <Ts...> & t) noexcept
    {
        return static_cast <base &> (t);
    }

    static base const & slice (tuple <Ts...> const & t) noexcept
    {
        return static_cast <base const &> (t);
    }

    static base && slice (tuple <Ts...> && t) noexcept
    {
        return static_cast <base &&> (stl::move (t));
    }

    static base const && slice (tuple <Ts...> const && t) noexcept
    {
        return static_cast <base const &&> (stl::move (t));
    }
};

template <class ... Ts>
struct get_impl <tuple <Ts...>>
{
    template <std::size_t I>
    static constexpr typename stl::tuple_element <I, tuple <Ts...>>::type &
        do_get (tuple <Ts...> & t) noexcept
    {
        using tup  = tuple <Ts...>
        using type = typename stl::tuple_element <I, tup>::type;
        using node = typename tup::base::template type_node <I, type>

        return static_cast <node &> (t).member;
    }

    template <std::size_t I>
    static constexpr
    typename stl::tuple_element <I, tuple <Ts...>>::type const &
        do_get (tuple <Ts...> const & t) noexcept
    {
        using tup  = tuple <Ts...>
        using type = typename stl::tuple_element <I, tup>::type;
        using node = typename tup::base::template type_node <I, type>

        return static_cast <node const &> (t).member;
    }

    template <std::size_t I>
    static constexpr typename stl::tuple_element <I, tuple <Ts...>>::type &&
        do_get (tuple <Ts...> && t) noexcept
    {
        using tup  = tuple <Ts...>
        using type = typename stl::tuple_element <I, tup>::type;
        using node = typename tup::base::template type_node <I, type>

        return stl::forward <type &&> (static_cast <node &> (t).member);
    }

    template <std::size_t I>
    static constexpr
    typename stl::tuple_element <I, tuple <Ts...>>::type const &&
        do_get (tuple <Ts...> const && t) noexcept
    {
        using tup  = tuple <Ts...>
        using type = typename stl::tuple_element <I, tup>::type;
        using node = typename tup::base::template type_node <I, type>

        return stl::forward <type const &&> (
            static_cast <node const &> (t).member
        );
    }
};

struct compare_impl
{
    static constexpr bool do_eq (tuple <> const &,
                                 tuple <> const &) noexcept
    {
        return true;
    }

    static constexpr bool do_lt (tuple <> const &,
                                 tuple <> const &) noexcept
    {
        return false;
    }

    template <class ... Ts, class ... Us>
    static constexpr bool do_eq (tuple <Ts...> const & lhs,
                                 tuple <Us...> const & rhs) noexcept
    {
        using lhs_tuple = tuple <Ts...>
        using rhs_tuple = tuple <Ts...>

        return detail::base_access <lhs_tuple>::slice (lhs) ==
            detail::base_access <rhs_tuple>::slice (rhs);
    }

    template <class ... Ts, class ... Us>
    static constexpr bool do_lt (tuple <Ts...> const & lhs,
                                 tuple <Us...> const & rhs) noexcept
    {
        using lhs_tuple = tuple <Ts...>
        using rhs_tuple = tuple <Ts...>

        return detail::base_access <lhs_tuple>::slice (lhs) <
            detail::base_access <rhs_tuple>::slice (rhs);
    }
};

Now with these helper types we can implement the index and type based get free-functions, and the comparison operators on tuple. First, we'll implement get.

/*
 * While we're at it, we can also implement the C++17 rvalue reference to
 * const overload for index and type based get.
 */
template <std::size_t I, class ... Ts>
constexpr typename stl::tuple_element <I, tuple <Ts...>>::type &
    get (tuple <Ts...> & t) noexcept
{
    return detail::get_impl <tuple <Ts...>>::template do_get <I> (t);
}

template <std::size_t I, class ... Ts>
constexpr typename stl::tuple_element <I, tuple <Ts...>>::type const &
    get (tuple <Ts...> const & t) noexcept
{
    return detail::get_impl <tuple <Ts...>>::template do_get <I> (t);
}

template <std::size_t I, class ... Ts>
constexpr typename stl::tuple_element <I, tuple <Ts...>>::type &&
    get (tuple <Ts...> && t) noexcept
{
    return detail::get_impl <tuple <Ts...>>::template do_get <I> (
        stl::move (t)
    );
}

template <std::size_t I, class ... Ts>
constexpr typename stl::tuple_element <I, tuple <Ts...>>::type const &&
    get (tuple <Ts...> const && t) noexcept
{
    return detail::get_impl <tuple <Ts...>>::template do_get <I> (
        stl::move (t)
    );
}

/*
 * Type based get <>. This does not compile if the tuple has more than
 * one element of that type or if this is the empty tuple.
 *
 * We will be using the C++14 signatures.
 */
template <class S, class ... Ts>
constexpr S & get (tuple <Ts...> & t) noexcept
{
    static_assert (sizeof... (Ts) != 0, "cannot extract from empty tuple");

    using index        = bits::type_index <S, Ts...>
    using multiplicity = bits::type_multiplicity <S, Ts...>
    static_assert (
        multiplicity::value == 1, "cannot extract repeated element type"
    );

    return get <index::value> (t);
}

template <class S, class ... Ts>
constexpr S const & get (tuple <Ts...> const & t) noexcept
{
    static_assert (sizeof... (Ts) != 0, "cannot extract from empty tuple");

    using index        = bits::type_index <S, Ts...>
    using multiplicity = bits::type_multiplicity <S, Ts...>
    static_assert (
        multiplicity::value == 1, "cannot extract repeated element type"
    );

    return get <index::value> (t);
}

template <class S, class ... Ts>
constexpr S && get (tuple <Ts...> && t) noexcept
{
    static_assert (sizeof... (Ts) != 0, "cannot extract from empty tuple");

    using index        = bits::type_index <S, Ts...>
    using multiplicity = bits::type_multiplicity <S, Ts...>
    static_assert (
        multiplicity::value == 1, "cannot extract repeated element type"
    );

    return get <index::value> (stl::move (t));
}

template <class S, class ... Ts>
constexpr S const && get (tuple <Ts...> const && t) noexcept
{
    static_assert (sizeof... (Ts) != 0, "cannot extract from empty tuple");

    using index        = bits::type_index <S, Ts...>
    using multiplicity = bits::type_multiplicity <S, Ts...>
    static_assert (
        multiplicity::value == 1, "cannot extract repeated element type"
    );

    return get <index::value> (stl::move (t));
}

Now we'll implement the comparison operators. Just like with pair, we only need to implement the equality and less-than operators by hand, as the remainder can be written in terms of these.

template <class ... Ts, class ... Us>
constexpr bool operator== (tuple <Ts...> const & lhs,
                           tuple <Us...> const & rhs)
{
    return detail::compare_impl::do_eq (lhs, rhs);
}

template <class ... Ts, class ... Us>
constexpr bool operator!= (tuple <Ts...> const & lhs,
                           tuple <Us...> const & rhs)
{
    return !(lhs == rhs);
}

template <class ... Ts, class ... Us>
constexpr bool operator< (tuple <Ts...> const & lhs,
                          tuple <Us...> const & rhs)
{
    return detail::compare_impl::do_lt (lhs, rhs);
}

template <class ... Ts, class ... Us>
constexpr bool operator<= (tuple <Ts...> const & lhs,
                           tuple <Us...> const & rhs)
{
    return !(rhs < lhs);
}

template <class ... Ts, class ... Us>
constexpr bool operator> (tuple <Ts...> const & lhs,
                          tuple <Us...> const & rhs)
{
    return rhs < lhs;
}

template <class ... Ts, class ... Us>
constexpr bool operator>= (tuple <Ts...> const & lhs,
                           tuple <Us...> const & rhs)
{
    return !(lhs < rhs);
}

The last free-function that requires a helper type is tuple_cat. This function takes zero or more tuples of various types and concatentates their contents into a new tuple. Here's the helper types along with tuple_cat itself.

namespace detail
{
    template <class ... Tup>
    struct concat_type;

    template <>
    struct concat_type <>
    {
        using type = tuple <>
    };

    template <class Tup>
    struct concat_type <Tup>
    {
        using type = typename std::decay <Tup>::type;
    };

    template <class ... As, class ... Bs, class ... Tups>
    struct concat_type <tuple <As...>, tuple <Bs...>, Tups...>
    {
        using type = typename concat_type <
            tuple <As..., Bs...>, Tups...
        >::type;
    };

    template <std::size_t N>
    struct tuple_cat_helper;

    template <>
    struct tuple_cat_helper <0>
    {
        static constexpr tuple <> dispatch (void) noexcept
        {
            return tuple <> ();
        }
    };

    template <>
    struct tuple_cat_helper <1>
    {
        template <class Tuple>
        static constexpr typename std::decay <Tuple>::type
            dispatch (Tuple && t) noexcept
        {
            return typename std::decay <Tuple>::type (stl::forward <Tuple> (t));
        }
    };

    template <>
    struct tuple_cat_helper <2>
    {
        template <
            std::size_t ... I1, std::size_t ... I2, class Tuple1, class Tuple2
        >
        static constexpr typename concat_type <
            typename std::decay <Tuple1>::type,
            typename std::decay <Tuple2>::type
        >::type
            concat (stl::index_sequence <I1...>,
                    stl::index_sequence <I2...>,
                    Tuple1 && t1,
                    Tuple2 && t2) noexcept
        {
            using result = typename concat_type <
                typename std::decay <Tuple1>::type,
                typename std::decay <Tuple2>::type
            >::type;
            return result (
                stl::get <I1> (stl::forward <Tuple1> (t1))...,
                stl::get <I2> (stl::forward <Tuple2> (t2))...
            );
        }

        template <class Tuple1, class Tuple2>
        static constexpr typename concat_type <
            typename std::decay <Tuple1>::type,
            typename std::decay <Tuple2>::type
        >::type
            dispatch (Tuple1 && t1, Tuple2 && t2) noexcept
        {
            using size1 = stl::tuple_size <typename std::decay <Tuple1>::type>
            using size2 = stl::tuple_size <typename std::decay <Tuple2>::type>
            return concat (
                stl::make_index_sequence <size1::value> {},
                stl::make_index_sequence <size2::value> {},
                stl::forward <Tuple1> (t1),
                stl::forward <Tuple2> (t2)
            );
        }
    };

    /*
     * Because of the above specializations we know that N >= 3, which ensures
     * correctness of the concat implementation.
     */
    template <std::size_t N>
    struct tuple_cat_helper
    {
        template <
            std::size_t ... I1, std::size_t ... I2,
            class Tuple1, class Tuple2, class ... Tuples
        >
        static constexpr typename concat_type <
            typename std::decay <Tuple1>::type,
            typename std::decay <Tuple2>::type,
            typename std::decay <Tuples>::type...
        >::type
            concat (stl::index_sequence <I1...>,
                    stl::index_sequence <I2...>,
                    Tuple1 && t1, Tuple2 && t2,
                    Tuples && ... ts)
        {
            using partial = typename concat_type <
                typename std::decay <Tuple1>::type,
                typename std::decay <Tuple2>::type
            >::type;
            return tuple_cat_helper <2>::dispatch (
                partial (get <I1> (stl::forward <Tuple1> (t1))...,
                         get <I2> (stl::forward <Tuple2> (t2))...),
                tuple_cat_helper <N - 2>::dispatch (
                    stl::forward <Tuples> (ts)...
                )
            );
        }

        template <class Tuple1, class Tuple2, class ... Tuples>
        static constexpr typename concat_type <
            typename std::decay <Tuple1>::type,
            typename std::decay <Tuple2>::type,
            typename std::decay <Tuples>::type...
        >::type
            dispatch (Tuple1 && t1, Tuple2 && t2, Tuples && ... ts) noexcept
        {
            using size1 = stl::tuple_size <typename std::decay <Tuple1>::type>
            using size2 = stl::tuple_size <typename std::decay <Tuple2>::type>
            return concat (
                stl::make_index_sequence <size1::value> {},
                stl::make_index_sequence <size2::value> {},
                stl::forward <Tuple1> (t1),
                stl::forward <Tuple2> (t2),
                stl::forward <Tuples> (ts)...
            );
        }
    };
}

/*
 * Concatenates one or more tuples with member objects ordered by the
 * appearance in which their original tuples appeared as parameters.
 *
 * We use the C++14 signature.
 */
template <class ... Tuples>
constexpr typename detail::concat_type <
    typename std::decay <Tuples>::type...
>::type
    tuple_cat (Tuples && ... tuples)
{
    return detail::tuple_cat_helper <sizeof... (Tuples)>::dispatch (
        stl::forward <Tuples> (tuples)...
    );
}

The only remaining free-functions to implement are make_tuple, which creates a tuple from a parameter pack of arguments, tie, which creates a tuple of references to its arguments, forward_as_tuple, which creates a tuple of forwarding references to its arguments, and the specialization for swap, which will simply forward on to the member swap function of tuple. This is all fairly short, so here's the code in one block.

/*
 * Creates a tuple object from the passed parameters. If any of the deduced
 * types are reference wrappers the reference wrapper types are further
 * decayed to the underlying reference types.
 *
 * We will be using the C++14 signature.
 */
template <class ... Ts>
constexpr
tuple <
    typename bits::decay_reference_wrapper <
        typename std::decay <Ts>::type
    >::type...
> make_tuple (Ts && ... ts)
{
    using tuple_type = tuple <
        typename bits::decay_reference_wrapper <
            typename std::decay <Ts>::type
        >::type...
    >
    return tuple_type (stl::forward <Ts> (ts)...);
}

/*
 * Creates a tuple of lvalue references to its arguments (or references to
 * the stl::ignore object).
 *
 * We will be using the C++14 signature.
 */
template <class ... Ts>
constexpr tuple <Ts &...> tie (Ts & ... ts) noexcept
{
    return tuple <Ts &...> (ts...);
}

/*
 * Creates a tuple of references to its arguments suitable for forwarding
 * to a function call. rvalue references are preserved for the appropriate
 * arguments, and lvalue references are taken to all other arguments.
 *
 * We will be using the C++14 signature.
 */
template <class ... Ts>
constexpr tuple <Ts &&...> forward_as_tuple (Ts && ... ts) noexcept
{
    return tuple <Ts &&...> (stl::forward <Ts> (ts)...);
}

/*
 * This is our free-function swap specialization for tuples. It will simply
 * forward to the member swap function for tuple.
 */
template <class ... Types>
void swap (tuple <Types...> & lhs, tuple <Types...> & rhs)
    noexcept (noexcept (lhs.swap (rhs)))
{
    lhs.swap (rhs);
}

Okay, we're done with tuple! The last thing to do is finish up the piecewise constructor for pair. Remember that we had a private constructor that will unpack tuples as arguments for the first and second member object constructors, so we'll have two things to implement. One thing to note, we use a template-template in order to implement the constructor. The reason for this is that pair itself is a template, while the pair::pair (tuple <Args1...>, tuple <Args2...>) constructor is also a template (but separate from the first). Thus, to implement these out-of-line we use a template-template. If you haven't seen this construct before that's okay, it's pretty rare in the wild.

/*
 * Lasly, now that tuples have been implemented we can define the
 * piecewise constructor for pair.
 */
template <class T1, class T2>
    template <
        std::size_t ... I1, std::size_t ... I2,
        class ... Args1, class ... Args2
    >
pair <T1, T2>::pair (stl::index_sequence <I1...>,
                     stl::index_sequence <I2...>,
                     tuple <Args1...> first_args,
                     tuple <Args2...> second_args)
    : first  (stl::get <I1> (first_args)...)
    , second (stl::get <I2> (second_args)...)
{}

template <class T1, class T2>
    template <class ... Args1, class ... Args2>
pair <T1, T2>::pair (stl::piecewise_construct_t,
                    tuple <Args1...> first_args,
                    tuple <Args2...> second_args)
    : pair (
        stl::make_index_sequence <sizeof... (Args1)> {},
        stl::make_index_sequence <sizeof... (Args2)> {},
        first_args,
        second_args
    )
{}

That's all for the stl/tuple.hpp header. I hope you've enjoyed this (very, very long) blog post. Next time we'll be implementing reference_wrapper and function objects. See you then!