15
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Your implementation does not handle empty tuples :) \$\endgroup\$ – Morwenn Mar 17 '14 at 12:48
  • \$\begingroup\$ @Morwenn Ah good point :) what is acceptable behavior for that? Perhaps just an empty specialized class? I mean, there's nothing to get from it. \$\endgroup\$ – chbaker0 Mar 17 '14 at 19:55
  • \$\begingroup\$ I actually tried to find a use case for it, but the only I could find was for some variadic metafunctions using tuples where there was a specialization for an empty parameter pack. \$\endgroup\$ – Morwenn Mar 18 '14 at 8:42
  • 3
    \$\begingroup\$ First obvious point: GreaterThanZero might as well just use: return N > 0; as its body. \$\endgroup\$ – Jerry Coffin Mar 19 '14 at 6:31
  • \$\begingroup\$ @JerryCoffin Wow, I can't believe I did that. The code has been updated for both fixes. \$\endgroup\$ – chbaker0 Mar 20 '14 at 1:20
12
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Kudos for the non-recursive implementation :) \$\endgroup\$ – Morwenn Mar 20 '14 at 11:02
  • \$\begingroup\$ Agreed, that's cool. Not to mention, saves me from the unlikely case that the entire tuple won't be inlined with the recursive implementation. \$\endgroup\$ – chbaker0 Mar 20 '14 at 23:05
8
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Yes, I had noticed too that a const was missing, but one couldn't see that easily among all the template, enable_if and Helper stuff. \$\endgroup\$ – iavr Mar 20 '14 at 13:23
  • \$\begingroup\$ Good point, that's pretty important. \$\endgroup\$ – chbaker0 Mar 20 '14 at 23:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.