A non-recursive tuple_element<index, Tuple> implementation

Question

This is basically a non-recursive std::tuple_element implementation.

Note

To make this non-recursive, you must replace std::make_index_sequence with a non-recursive implementation. I left it with std::make_index_sequence in order to reduce the amount of unrelated code.

How it works

deduct has a specialization of deduct_impl that is generated from the index sequence template argument it receives. It is used in order to deduce the type at index in a variadic type template or tuple. It uses the itp_base and itp types.

itp<std::size_t> and itp<std::size_t, T> is an index-type-pair used to expand the variadic indices template with a type variadic template in order to match the generated specialization.

deducer puts it all together by specializing deduct and deduct_impl by using std::conditional_t to generate the correct specialization.

Basically, for std::tuple<void, int, char>, in order to get the type at index 1, it creates itp_base<0>, itp<1, int>, itp_base<2> and passes it to deduct and deduct_impl.

Source code

#include <utility>
#include <tuple>
template <std::size_t index>
struct itp_base {};
template <std::size_t index, typename T>
struct itp : itp_base<index> {};
template <std::size_t index, typename IndexSequence>
struct deduct;
template <std::size_t index, std::size_t... indices>
struct deduct<index, std::index_sequence<indices...>>
{
 template <typename Tuple>
 struct deduct_impl;
 template <typename T, typename... R>
 struct deduct_impl<std::tuple<itp_base<indices>..., itp<index, T>, R...>>
 {
 using type = T;
 };
};
template <std::size_t index, typename... Types>
class deducer
{
private:
 static_assert( index < sizeof...( Types ), "deducer::index out of bounds" );
 template <typename IndexSequence>
 struct deducer_impl;
 template <std::size_t... indices>
 struct deducer_impl<std::index_sequence<indices...>>
 {
 using type = typename deduct<index, std::make_index_sequence<index>
 >::template deduct_impl
 <
 std::tuple
 <
 std::conditional_t
 <
 std::is_base_of<itp_base<indices>, itp<index, Types>>::value,
 itp<index, Types>,
 itp_base<indices>
 >...
 >
 >::type;
 };
public:
 using type = typename deducer_impl<
 std::make_index_sequence<sizeof...( Types )>>::type;
};

Convenience aliases

template <std::size_t index, typename Tuple>
struct tuple_element;
template <std::size_t index, typename... Types>
struct tuple_element<index, std::tuple<Types...>> : deducer<index, Types...> {};
template <std::size_t index, typename... Types>
using tuple_element_t = typename tuple_element<index, Types...>::type;

Test case

#include <iostream>
#include <string>
int main()
{
 using tuple_t = std::tuple<int, void, std::string>;
 static_assert( std::is_same<tuple_element_t<2, tuple_t>, std::string>::value, "!" );
}

Demo

http://coliru.stacked-crooked.com/a/16805356d2578d6d

Answer 1

Your approach on finding the nth element relies on being able to construct a tuple with the first n-1 types being some predictable thing that you can match against. But the types you chose for std::tuple<void, int, char> were, for index 1, std::tuple<itp_base<0>, itp<1, int>, itp_base<2>>.

But we don't actually need to introduce this itp thing to do this, we can simply turn it into std::tuple<void, int, void>. That way, deduct_impl's specialization instead of taking a std::tuple<itp_base<indices>..., itp<index, T>, R...>, we can simplify to:

template <std::size_t>
using make_void = void;
template <typename T, typename... R>
struct deduct_impl<std::tuple<make_void<indices>..., T, R...>>
{
 using type = T;
};

And on the other side, we pass in:

std::tuple<std::conditional_t<(indices == index), Types, void>...>

Same idea, just more direct.

For that matter, we don't even need the tuple! std::tuple is an expensive type to construct at compile-time, so it's best to avoid it entirely. Just pass in the types as a pack (though the following doesn't compile on gcc - though even there you don't need tuple, just use a light wrapper like template <class...> struct typelist;)

template <typename... Ts>
struct deduct_impl;
template <std::size_t>
using make_void = void;
template <typename T, typename... R>
struct deduct_impl<make_void<indices>..., T, R...>
{
 using type = T;
};

and:

using type = typename deduct<index, std::make_index_sequence<index>
>::template deduct_impl
<
 std::conditional_t<(indices == index), Types, void>...
>::type;

A different approach

Another non-recursive way to do this would be through an inheritance tree. We basically take std::tuple<void, int, char> and turn it into a type that inherits from indexed<0, void>, indexed<1, int>, and indexed<2, char>:

template <std::size_t I, typename T>
struct indexed {
 using type = T;
};
template <typename Is, typename ...Ts>
struct indexer;
template <std::size_t ...Is, typename ...Ts>
struct indexer<std::index_sequence<Is...>, Ts...>
: indexed<Is, Ts>...
{};

Then, given a function template constrained on an index, we can pull out the correct type:

template <std::size_t I, typename ...Ts>
struct at_index {
private:
 template <typename T>
 static indexed<I, T> select(indexed<I, T>);
 using impl = indexer<std::index_sequence_for<Ts...>, Ts...>;
public:
 using type = typename decltype(select(impl{}))::type;
};

I don't know which solution is better, but this one is certainly shorter.

• user2296177: The conditional_t condition can be simplified to indices == index as you point out. However, VC++ v140 generates an error saying that index is not in static storage. That was a workaround. I appreciate your review. If you're interested, this link was shared by dyp in the SO question I asked about this code: ldionne.com/2015/11/29/efficient-parameter-pack-indexing