STL From Scratch - Pairs and Tuples Part #1

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

I have decided to split-up the posts on pairs and tuples so that we don't have one extremely long post. However, both data structures are closely related to one another and so their respective posts will be released more or less at the same time. The code for both is already available on the GitHub repository to check out.

In this post (part 1) we will be implementing pair. In part 2, to be released shortly after this, we will be implementing tuple.

There is one helper type that we need to define, piecewise_construct_t. This type will allow us to call the piecewise constructor that we'll see later on. The piecewise constructor of pair also requires that we forward declare tuple, so we will do that at the same time. Since piecewise_construct_t is simply a tag type, so all we need write is

template <class...>
class tuple;

struct piecewise_construct_t {};

Now we can implement pair. As before, all our code will be placed inside namespace stl unless otherwise stated. There's not much to it beyond the constructors (we'll discuss the free functions more later on), so here's the code.

/*
 * We'll be using the C++14 signatures for pair's constructors and member
 * functions.
 */
template <class T1, class T2>
class pair
{
public:
    /* first and second are public member objects of pair */
    T1 first;
    T2 second;

    using first_type  = T1;
    using second_type = T2;

    /* we can default this and let the compiler generate the constructor */
    constexpr pair (void) = default;

    constexpr pair (T1 const & t1, T2 const & t2)
        : first  (t1)
        , second (t2)
    {}

    /*
     * This constructor forwards its arguments to the constructors of first
     * and second, respectively. It participates in overload resolution
     * only if U1 is implicitly convertible to T1 and U2 is implicitly
     * convertible to T2, which is why we use the defaulted third parameter
     * enable_if expression.
     */
    template <
        class U1, class U2,
        typename = typename std::enable_if <
            std::is_convertible <U1, T1>::value &&
            std::is_convertible <U2, T2>::value
        >::type
    >
    constexpr pair (U1 && u1, U2 && u2)
        : first  (stl::forward <U1> (u1))
        , second (stl::forward <U2> (u2))
    {}

    /*
     * Constructs first from the first element of the argument, and second
     * from the second element of the argument. The constructions must be
     * well-formed for the types T1 and T2, or use of this constructor will
     * not compile.
     */
    template <class U1, class U2>
    constexpr pair (pair <U1, U2> const & p)
        : first  (p.first)
        , second (p.second)
    {}

    /*
     * Constructs first from the moved-from value of the first element of
     * the argument, and second from the moved-from value of the second
     * element of the argument. The constructions must be well-formed for
     * the types T1 and T2, otherwise use of this constructor will not
     * compile.
     */
    template <class U1, class U2>
    constexpr pair (pair <U1, U2> && p)
        : first  (stl::move (p.first))
        , second (stl::move (p.second))
    {}

private:
    /*
     * In order to implement the piecewise constructor we will first
     * need to implement tuple, so for now we leave this as a
     * declaration only, just as the below constructor.
     */
    template <
        std::size_t ... I1, std::size_t ... I2,
        class ... Args1, class ... Args2
    >
    pair (stl::index_sequence <I1...>,
          stl::index_sequence <I2...>,
          tuple <Args1...> first_args,
          tuple <Args2...> second_args);

public:
    /*
     * Constructs first and second from the forwarded elements of each
     * argument tuple, respectively. This constructor will be defined
     * in the tuple.hpp file. Since this must allow for non-copyable and
     * non-movable types we'll have to forward to the above private
     * constructor that can properly construct the member objects.
     */
    template <class ... Args1, class ... Args2>
    pair (piecewise_construct_t, tuple <Args1...>, tuple <Args2...>);

    /* we can default this and let the compiler generate the destructor */
    ~pair (void) = default;

    /*
     * As per the specification, the copy and move constructors of pair are
     * defaulted.
     */
    constexpr pair (pair const &) = default;
    constexpr pair (pair &&) = default;

    /*
     * We have four assignment operators to implement. The first two are
     * the standard copy and move assignment operators, while the second
     * two are templated versions of each (the entailed assignments must
     * be well formed for the types T1 and T2, otherwise use of those
     * assignment operators will not compile).
     */
    pair & operator= (pair const & other)
    {
        this->first  = other.first;
        this->second = other.second;
        return *this;
    }

    pair & operator= (pair && other)
        noexcept (std::is_nothrow_move_assignable <T1>::value &&
                  std::is_nothrow_move_assignable <T2>::value)
    {
        this->first  = stl::move (other.first);
        this->second = stl::move (other.second);
        return *this;
    }

    template <class U1, class U2>
    pair & operator= (pair <U1, U2> const & other)
    {
        this->first  = other.first;
        this->second = other.second;
        return *this;
    }

    template <class U1, class U2>
    pair & operator= (pair <U1, U2> && other)
    {
        this->first  = stl::forward <U1> (other.first);
        this->second = stl::forward <U2> (other.second);
        return *this;
    }

    /*
     * Our last member function to implement is swap. It swaps across the
     * first elements of this and other, and across the second elements of
     * this and other. The method will be noexcept if the swapping of each
     * of the first and second elements is noexcept.
     */
    void swap (pair & other)
        noexcept (
            noexcept (
                stl::swap (stl::declval <T1 &> (), stl::declval <T1 &> ())
            ) &&
            noexcept (
                stl::swap (stl::declval <T2 &> (), stl::declval <T2 &> ())
            )
        )
    {
        using stl::swap;
        swap (this->first, other.first);
        swap (this->second, other.second);
    }
};

That's it for pair (besides the piecewise constructor)! It's all relatively straightforward. All we have left is to implement the free functions operating on pair objects.

The first free functions we'll implement are the comparison operators.

/*
 * Comparison for pairs is lexicographic (meaning comparisons will happen
 * for the first elements, and then conditionally for the second elements).
 *
 * We will be using the C++14 signatures for these.
 */
template <class T1, class T2>
constexpr bool
    operator== (pair <T1, T2> const & lhs, pair <T1, T2> const & rhs)
{
    return lhs.first == rhs.first && lhs.second == rhs.second;
}

template <class T1, class T2>
constexpr bool
    operator!= (pair <T1, T2> const & lhs, pair <T1, T2> const & rhs)
{
    return lhs.first != rhs.first || lhs.second != rhs.second;
}

template <class T1, class T2>
constexpr bool
    operator< (pair <T1, T2> const & lhs, pair <T1, T2> const & rhs)
{
    return lhs.first < rhs.first ? true :
           rhs.first < lhs.first ? false :
           lhs.second < rhs.second ? true : false;
}

template <class T1, class T2>
constexpr bool
    operator<= (pair <T1, T2> const & lhs, pair <T1, T2> const & rhs)
{
    return !(rhs < lhs); 
}

template <class T1, class T2>
constexpr bool
    operator> (pair <T1, T2> const & lhs, pair <T1, T2> const & rhs)
{
    return rhs < lhs;
}

template <class T1, class T2>
constexpr bool
    operator>= (pair <T1, T2> const & lhs, pair <T1, T2> const & rhs)
{
    return !(lhs < rhs); 
}

Notice how we only needed to write equality and less-than operators by hand, as the remaining comparison operators can always be implemented on top of these two. We will use this as a common short-cut from now on whenever comparison operators are needed.

The next function to implement is make_pair, which takes two arguments (of possibly different types) and creates a new pair object.

/*
 * make_pair constructs a new pair with types deduced from its arguments
 * after applying std::decay to the template type parameters (unless the
 * decay produces a reference wrapper, in which case we convert to the
 * underlying reference). In the implementation below, note that when
 * forwarding to the constructor of pair we rely on stl::reference_wrapper
 * to implicitly convert to its underlying reference.
 *
 * This is the C++14 signature of make_pair.
 */
template <typename T1, typename T2>
constexpr pair <
    typename bits::decay_reference_wrapper <
        typename std::decay <T1>::type
    >::type,
    typename bits::decay_reference_wrapper <
        typename std::decay <T2>::type
    >::type
> make_pair (T1 && t1, T2 && t2)
{
    using t1_decay = typename bits::decay_reference_wrapper <
        typename std::decay <T1>::type
    >::type;
    using t2_decay = typename bits::decay_reference_wrapper <
        typename std::decay <T2>::type
    >::type;

    return pair <t1_decay, t2_decay> {
        stl::forward <t1_decay> (t1), stl::forward <t2_decay> (t2)
    };
}

Now we have the free function swap specialization for pairs. This will simply forward to the member swap function.

template <class T1, class T2>
void swap (pair <T1, T2> & p1, pair <T1, T2> & p2)
    noexcept (noexcept (p1.swap (p2)))
{
    p1.swap (p2);
}

Finally we have the index-based and type-based specializations for the free function get. In order to have the types match up correctly for get <0> () vs get <1> () applied to pairs we will make use of some helper types and functions in namespace detail. First, in the header stl/bits/type_helpers.hpp we will write an index_tag <N> type that will let us overload our helper methods in order to select the correct member object from pair.

template <std::size_t I>
struct index_tag : std::integral_constant <std::size_t, I> {};

With this type we can now implement index-based get in the stl/utility.hpp header. Notice that we'll also implement the C++17 overloads of get taking pair const && as an argument.

namespace detail
{
    template <class T1, class T2>
    constexpr T1 & get_helper (pair <T1, T2> & p, bits::index_tag <0>)
        noexcept
    {
        return p.first;
    }

    template <class T1, class T2>
    constexpr T2 & get_helper (pair <T1, T2> & p, bits::index_tag <1>)
        noexcept
    {
        return p.second;
    }

    template <class T1, class T2>
    constexpr T1 const &
        get_helper (pair <T1, T2> const & p, bits::index_tag <0>) noexcept
    {
        return p.first;
    }

    template <class T1, class T2>
    constexpr T2 const &
        get_helper (pair <T1, T2> const & p, bits::index_tag <1>) noexcept
    {
        return p.second;
    }

    template <class T1, class T2>
    constexpr T1 && get_helper (pair <T1, T2> && p, bits::index_tag <0>)
        noexcept
    {
        return stl::move (p.first);
    }

    template <class T1, class T2>
    constexpr T2 && get_helper (pair <T1, T2> && p, bits::index_tag <1>)
        noexcept
    {
        return stl::move (p.second);
    }

    template <class T1, class T2>
    constexpr T1 const && get_helper (pair <T1, T2> const && p, 
                                      bits::index_tag <0>)
        noexcept
    {
        return stl::move (p.first);
    }

    template <class T1, class T2>
    constexpr T2 const && get_helper (pair <T1, T2> const && p, 
                                      bits::index_tag <1>)
        noexcept
    {
        return stl::move (p.second);
    }
}   // namespace detail

    /*
     * For type based versions of get, the types T1 and T2 cannot be 
     * the same.
     */
    template <std::size_t I, class T1, class T2>
    constexpr typename tuple_element <I, pair <T1, T2>>::type &
        get (pair <T1, T2> & p) noexcept
    {
        return detail::get_helper (p, bits::index_tag <I> {});
    }

    template <std::size_t I, class T1, class T2>
    constexpr typename tuple_element <I, pair <T1, T2>>::type const &
        get (pair <T1, T2> const & p) noexcept
    {
        return detail::get_helper (p, bits::index_tag <I> {});
    }

    template <std::size_t I, class T1, class T2>
    constexpr typename tuple_element <I, pair <T1, T2>>::type &&
        get (pair <T1, T2> && p) noexcept
    {
        return detail::get_helper (stl::move (p), bits::index_tag <I> {});
    }

    template <std::size_t I, class T1, class T2>
    constexpr typename tuple_element <I, pair <T1, T2>>::type const &&
        get (pair <T1, T2> const && p) noexcept
    {
        return detail::get_helper (stl::move (p), bits::index_tag <I> {});
    }

Lastly, we have the type-based specializations for get. These are far easier to implement than the index-based specializations, as we can detect which member object of pair to access based on the order of the template type arguments to pair. Note that these functions will compile only if the template types are distinct.

template <class T, class U>
constexpr T & get (pair <T, U> & p) noexcept
{
    return p.first;
}

template <class T, class U>
constexpr T const & get (pair <T, U> const & p) noexcept
{
    return p.first;
}

template <class T, class U>
constexpr T && get (pair <T, U> && p) noexcept
{
    return stl::move (p.first);
}

template <class T, class U>
constexpr T const && get (pair <T, U> const && p) noexcept
{
    return stl::move (p.first);
}

template <class T, class U>
constexpr T & get (pair <U, T> & p) noexcept
{
    return p.second;
}

template <class T, class U>
constexpr T const & get (pair <U, T> const & p) noexcept
{
    return p.second;
}

template <class T, class U>
constexpr T && get (pair <U, T> && p) noexcept
{
    return stl::move (p.second);
}

template <class T, class U>
constexpr T const && get (pair <U, T> const && p) noexcept
{
    return stl::move (p.second);
}

And that's it! We have completely implemented pair (with the exception of the piecewise constructor, which will come in the next post).

The implementation of tuple is considerably longer than that for pair, but I will work to have the next post up as soon as possible. Again, the code is already available on [the GitHub repository][2], so feel free to check it out in the meantime.