Very basic tuple implementation

Question

I've been messing with metaprogramming and variadic templates in C++, and I came up with this very primitive implementation of a tuple:

constexpr bool GreaterThanZero(int N)
{
    return N > 0;
}

template <int, typename...>
struct Helper;

template <int N, typename Head, typename... Tail>
struct Helper<N, Head, Tail...>
{
    typedef typename Helper<N-1, Tail...>::type type;
};

template <typename Head, typename... Tail>
struct Helper<0, Head, Tail...>
{
    typedef Head& type;
};

template <int, typename...>
class TupleImpl;

template <>
class TupleImpl<-1>
{

};

template <typename Head>
class TupleImpl<0, Head>
{
protected:
    Head head;

public:
    template <int Depth>
    Head& get()
    {
        static_assert(Depth == 0, "Requested member deeper than Tuple");
        return head;
    }

    template <int Depth>
    const Head& get() const
    {
        static_assert(Depth == 0, "Requested member deeper than Tuple");
        return head;
    }
};

template <int N, typename Head, typename... Tail>
class TupleImpl<N, Head, Tail...>
{
protected:
    Head head;
    TupleImpl<N-1, Tail...> tail;



public:
    template <int M>
    typename std::enable_if<M == 0, Head&>::type get()
    {
        return head;
    }

    template <int M>
    typename std::enable_if<GreaterThanZero(M), typename Helper<M, Head, Tail...>::type>::type get()
    {
        return tail.get<M-1>();
    }

    template <int M>
    typename std::enable_if<M == 0, const Head&>::type get() const
    {
        return head;
    }

    template <int M>
    typename std::enable_if<GreaterThanZero(M), typename Helper<M, Head, Tail...>::type>::type get() const
    {
        return tail.get<M-1>();
    }
};

template <typename... Elements>
class Tuple : public TupleImpl<sizeof...(Elements)-1, Elements...>
{
public:
    static constexpr std::size_t size()
    {
        return sizeof...(Elements);
    }
};

int main()
{
    using namespace std;

    Tuple<int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int, int> test;
    Tuple<> test2;

    test.get<0>() = 1;
    test.get<1>() = 2;

    cout << test.size() << endl;
    cout << test.get<0>() << endl;
    cout << test.get<1>() << endl;
}

Being template metaprogramming, of course it looks terrible. Are there any ways I can clean it up? I've been picking up the nitty-gritty details of how templates work by messing around with stuff like this, but I'm sure I'm missing something that would simplify this.

Answer 1

Below is how I would clean this up, or maybe partially re-write [live example]:

// helpers
template <typename T>
struct id { using type = T; };

template <typename T>
using type_of = typename T::type;

template <size_t... N>
struct sizes : id <sizes <N...> > { };

// choose N-th element in list <T...>
template <size_t N, typename... T>
struct Choose;

template <size_t N, typename H, typename... T>
struct Choose <N, H, T...> : Choose <N-1, T...> { };

template <typename H, typename... T>
struct Choose <0, H, T...> : id <H> { };

template <size_t N, typename... T>
using choose = type_of <Choose <N, T...> >;

// given L>=0, generate sequence <0, ..., L-1>
template <size_t L, size_t I = 0, typename S = sizes <> >
struct Range;

template <size_t L, size_t I, size_t... N>
struct Range <L, I, sizes <N...> > : Range <L, I+1, sizes <N..., I> > { };

template <size_t L, size_t... N>
struct Range <L, L, sizes <N...> > : sizes <N...> { };

template <size_t L>
using range = type_of <Range <L> >;

// single tuple element
template <size_t N, typename T>
class TupleElem
{
    T elem;
public:
    T&       get()       { return elem; }
    const T& get() const { return elem; }
};

// tuple implementation
template <typename N, typename... T>
class TupleImpl;

template <size_t... N, typename... T>
class TupleImpl <sizes <N...>, T...> : TupleElem <N, T>...
{
    template <size_t M> using pick = choose <M, T...>;
    template <size_t M> using elem = TupleElem <M, pick <M> >;

public:
    template <size_t M>
    pick <M>& get() { return elem <M>::get(); }

    template <size_t M>
    const pick <M>& get() const { return elem <M>::get(); }
};

template <typename... T>
struct Tuple : TupleImpl <range <sizeof...(T)>, T...>
{
    static constexpr std::size_t size() { return sizeof...(T); }
};

Comments:

• With a bit more infrastructure (helper structs that are typically reused here and there) at the beginning, the main tuple implementation becomes just 20 lines.

• Instead of a recursive implementation, I have switched to multiple (variadic) inheritance of single tuple elements TupleElem, each with its own id N (so that each element is of unique type) and its own function get(). Hence Tuple's function get() just redirects to the appropriate base class.

• Now a specialization of TupleElem for empty types can bring easily the desired empty base optimization without affecting the main tuple implementation.

• No specialization is needed for empty tuple. This definition includes empty tuple as a special case.

• No static assertions needed, an out-of-range index will give an error anyway (but you can add for better messages of course).

Now, there are so many things missing. I would start from support for rvalue references and, of course, constructors. If you want to get an idea, you can have a look at my own tuple implementation (of which this one here is a miniature) including tuple views, expression templates for lazy evaluation, loops, algorithms, integration with all C++ operators, and much more.

Template metaprogramming does not have to look terrible!

Answer 2

In C++14, it's possible to implement a tuple in a very concise way. However, you lose some functionality of std::tuple (constexprness and some perfect forwarding) because of some limitations of lambdas. The basic idea is to use a lambda capture as a fast compiler-generated struct. Here's a naive implementation just to give you the idea, but you should look at Hana to see the actual implementation:

#include <cstddef>
#include <utility>


template <typename ...Xs>
auto make_tuple(Xs&& ...xs) {
    // No perfect forwarding in the capture: maybe C++17?
    return [=](auto&& f) mutable -> decltype(auto) {
        return std::forward<decltype(f)>(f)(&xs...);
    };
}

template <std::size_t n, typename = std::make_index_sequence<n>>
struct get_impl;

template <std::size_t n, std::size_t ...ignore>
struct get_impl<n, std::index_sequence<ignore...>> {
    template <typename Nth>
    constexpr decltype(auto) operator()(decltype(ignore, (void const*)0)..., Nth nth, ...) const
    { return nth; }
};

template <std::size_t N, typename Tuple>
decltype(auto) get(Tuple& tuple) {
    return *tuple(get_impl<N>{});
}

You can then use it like:

#include <cassert>

int main() {
    auto xs = make_tuple('0', 1, 2.2);
    assert(get<0>(xs) == '0');
    assert(get<1>(xs) == 1);
    assert(get<2>(xs) == 2.2);

    get<2>(xs) = 2.2222222;
    assert(get<2>(xs) == 2.2222222);
}

Here's the live example. Of course, it's not exactly clear how one would then have a std::tuple<...> type using this technique, but it can be done (see slide 33 of this).

The largest advantages of this technique are:

1. Clarity. Once you get it, it's very simple and terse.
2. Opens new avenues for implementing many algorithms on tuples. For example, implementing std::tuple_cat is rather easy with this representation, while it's very hard with the usual std::tuple implementation.
3. Compile-time performance: I've done several benchmarks, and this implementation technique really improves on the usual std::tuple implementation in terms of compilation time.

Answer 3

This currently probably won't compile:

const Tuple<int, int> t{};
t.get<1>();

Your recursive const version of get returns a non-const reference.