4
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – user2296177 Dec 2 '15 at 22:14

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.