type_list with utilities

Question

The post is follow up to my previous Typelist with extractor. The type_list and extraction feature code is identical to the accepted answer (from user2296177). The idea is to provide a type list with fundamental features that users could built something specialized upon that.

List of features, by order of appearance in the code:

• type_list itself.

• type_list_extract, extracts Nth type (0 indexed) from the provided type_list.

• type_list_concat, concatenates 2 type_lists, adding second to the end of the first.

• type_list_expand, expansion of the type_list into std::tuple, supporting extraction by supplied indexes.

• utility first_index_holder, which helps to extract first index from the index interval.

• utility reverse_index_interval, which reverses interval N ... M to M ... N, code has undefined behavior if the interval is not contiguous.

• type_list_reverse, reversion of the type_list.

The code also provides convenient xxx_t aliases for all operations, except for first_index_holder and reverse_index_interval.

My particular concerns are naming in all parts of the code and optimization (in terms of instantiations) and compile-time (not sure how I could measure this though) of type_list_reverse.

#include <cstddef>
#include <tuple>
#include <utility>
#include <cassert>

template <class ... Types>
class type_list {};

template <std::size_t idx, class... Types>
class extract
{
    static_assert(idx < sizeof...(Types), "index out of bounds");

    template <std::size_t i, std::size_t n, class... Rest>
    struct extract_impl;

    template <std::size_t i, std::size_t n, class T, class... Rest>
    struct extract_impl<i, n, T, Rest...>
    {
        using type = typename extract_impl<i + 1, n, Rest...>::type;
    };

    template <std::size_t n, class T, class... Rest>
    struct extract_impl<n, n, T, Rest...>
    {
        using type = T;
    };
public:
    using type = typename extract_impl<0, idx, Types...>::type;
};

template <std::size_t idx, class TypeList>
struct type_list_extract;

template <std::size_t idx, template <class...> class TypeList, class... Types>
struct type_list_extract<idx, TypeList<Types...>>
{
    using type = typename extract<idx, Types...>::type;
};

template <std::size_t idx, class TypeList>
using type_list_extract_t = typename type_list_extract<idx, TypeList>::type;

template <class FirstTypeList, class SecondTypeList>
struct type_list_concat;

template <template <class ...> class TypeList, class ... FirstTypesPack, class ... SecondTypesPack>
struct type_list_concat<TypeList<FirstTypesPack...>, TypeList<SecondTypesPack...> >
{
    using type = TypeList<FirstTypesPack..., SecondTypesPack...>;
};

template <class FirstTypeList, class SecondTypeList>
using type_list_concat_t = typename type_list_concat<FirstTypeList, SecondTypeList>::type;

template <class TypeList, size_t ... indexes>
struct type_list_expand
{
    using type = std::tuple<typename type_list_extract<indexes, TypeList>::type...>;
};

template < template <class...> class TypeList, class ... Types>
struct type_list_expand< TypeList<Types...>>
{
    using type = std::tuple<Types...>;
};

template <class TypeList, size_t ... indexes>
using type_list_expand_t = typename type_list_expand<TypeList, indexes...>::type;

template <std::size_t ... indexes>
struct first_index_holder;

template <std::size_t head, std::size_t ... remainder>
struct first_index_holder<head, remainder...>
{
    static const std::size_t value = head;
};

template <class IndexInterval>
class reverse_index_interval;

template <template <typename T, T ...> class IndexInterval, std::size_t ... indexes>
class reverse_index_interval < IndexInterval<std::size_t, indexes...>>
{
    static const std::size_t size = sizeof...(indexes)-1;
    static const std::size_t head = first_index_holder<indexes...>::value;
public:
    using type = IndexInterval<std::size_t, (size + head - indexes + head)... >;
};

template <class TypeList>
class type_list_reverse;

template <template <class ... > class TypeList, class ... Types>
class type_list_reverse<TypeList<Types...> >
{
    template <class integer_sequence, class TList>
    struct typelist_reverse_impl;

    template <template <typename T, T ...> class Sequence, std::size_t ... indexes, template<class ...> class TList, class ... Ts>
    struct typelist_reverse_impl<Sequence<std::size_t, indexes...>, TList<Ts...>>
    {
        using type = TList<type_list_extract_t<indexes, TList<Ts...>>...>;
    };
public:
    using type = typename typelist_reverse_impl<typename reverse_index_interval<std::make_index_sequence<sizeof...(Types)> >::type, TypeList<Types...>>::type;
};

template <class TypeList>
using type_list_reverse_t = typename type_list_reverse<TypeList>::type;

Example usage:

#include <utility>
#include <cassert>
#include "typelist.h"

//just to populate with some types
struct String;
struct Condition;
struct Opinion;

int main()
{
    using MyList = type_list<int, char, bool>;
    using First = type_list_extract_t<0, MyList>;
    static_assert(std::is_same<First, int>::value, "!");

    using SecondList = type_list<String, Condition, Opinion>;
    using Concat = type_list_concat_t<MyList, SecondList>;
    static_assert(std::is_same<type_list<int, char, bool, String, Condition, Opinion>, Concat>::value, "!");

    using Expansion = type_list_expand_t<MyList>;
    static_assert(std::is_same<std::tuple<int, char, bool>, Expansion>::value, "!");

    using PartialExpansion = type_list_expand_t<MyList, 0, 2>; //int, bool
    static_assert(std::is_same<std::tuple<int, bool>, PartialExpansion>::value, "!");

    constexpr std::size_t sz = first_index_holder<2, 3, 4>::value;
    static_assert(sz == 2, "!");

    using Seq = std::index_sequence<2, 3, 4>;
    using ReversedSeq = reverse_index_interval<Seq>::type;
    static_assert(std::is_same<ReversedSeq, std::index_sequence<4, 3, 2> >::value, "!");

    using Rev = type_list_reverse_t<MyList>;
    static_assert(std::is_same<type_list<bool, char, int>, Rev>::value, "!");
}

Note: The code doesn't compile in VC++14 (it argues that > is missing before alias named type which belongs to reverse_index_interval), but does compile on Ideone and c++ shell (GCC 4.9.2). I believe my code is standard conformant.

Answer 1

This is an old question, but it has no answers yet, so what the heck.

I'll just focus on your extract metafunction. Consider a usage such as

using T0 = extract<0, int, int, int>::type;
using T1 = extract<1, int, int, int>::type;
using T2 = extract<2, int, int, int>::type;
using T3 = extract<1, int, int>::type;
using T4 = extract<2, void, int, int>::type;

for example's sake.

template <std::size_t idx, class... Types>
class extract
{
    static_assert(idx < sizeof...(Types), "index out of bounds");

    template <std::size_t i, std::size_t n, class... Rest>
    struct extract_impl;

Why a nested type? As written, when I do extract<1, int, int, int>::type, you're going to instantiate extract<1, int, int, int>, and then extract<1, int, int, int>::extract_impl<0, 1, int, int, int>, and then extract<1, int, int, int>::extract_impl<1, 1, int, int>. None of these nested types can be reused for the computation of extract<2, int, int, int>::type. That's inefficiency.

---

    template <std::size_t i, std::size_t n, class T, class... Rest>
    struct extract_impl<i, n, T, Rest...>
    {
        using type = typename extract_impl<i + 1, n, Rest...>::type;
    };

I might prefer to write this as

    template <std::size_t i, std::size_t n, class T, class... Rest>
    struct extract_impl<i, n, T, Rest...> : extract_impl<i + 1, n, Rest...> {};

I don't know whether it's actually faster/cheaper to compile an inheritance relationship than a whole new class, but this feels simpler, because we're not proliferating type members all over the place. There's just the one type member that we need, way down at the base of the class hierarchy.

---

    template <std::size_t n, class T, class... Rest>
    struct extract_impl<n, n, T, Rest...>
    {
        using type = T;
    };
public:
    using type = typename extract_impl<0, idx, Types...>::type;
};

Again I would use inheritance here; which requires that you un-nest the nested types (which I already said were a bad idea for efficiency anyway).

The other thing I would do is rework all your counters to count down instead of up. That way, you can maybe reuse some of your types as the counters approach zero.

And, stylistically, I prefer all my template parameters to be CamelCase, so I'm going to rename your lowercase idx to capital K.

---

Putting it all together:

using T0 = extract<0, int, int, int>::type;
using T1 = extract<1, int, int, int>::type;
using T2 = extract<2, int, int, int>::type;
using T3 = extract<1, int, int>::type;
using T4 = extract<2, void, int, int>::type;

With your original code, this instantiates the following class types:

extract<0, int, int, int>::extract_impl<0, 0, int, int, int>
extract<1, int, int, int>::extract_impl<0, 1, int, int, int>
extract<1, int, int, int>::extract_impl<1, 1, int, int>
extract<2, int, int, int>::extract_impl<0, 2, int, int, int>
extract<2, int, int, int>::extract_impl<1, 2, int, int>
extract<2, int, int, int>::extract_impl<2, 2, int>
extract<1, int, int>::extract_impl<0, 1, int, int>
extract<1, int, int>::extract_impl<1, 1, int>
extract<2, void, int, int>::extract_impl<0, 2, void, int, int>
extract<2, void, int, int>::extract_impl<1, 2, int, int>
extract<2, void, int, int>::extract_impl<2, 2, int>

But if we write your code this way instead:

template<size_t K, class T, class... Ts> struct extract_impl : extract_impl<K-1, Ts...> {};
template<class T, class... Ts> struct extract_impl<0, T, Ts...> { using type = T; };

template<size_t K, class... Ts>
struct extract {
    static_assert(K < sizeof...(Ts), "index out of bounds");
    using type = typename extract_impl<K, Ts...>::type;
};

...well, number one, it's crazy shorter. In fact, we don't really need extract_impl at all! The only reason you might want to keep extract separate from extract_impl is that it gives you a decent place to hang the static_assert.

Anyway, with this version, our example needs only these instantiations:

extract_impl<0, int, int, int>
extract_impl<1, int, int, int>
extract_impl<0, int, int>
extract_impl<2, int, int, int>
extract_impl<1, int, int>
extract_impl<0, int>
extract_impl<2, void, int, int>

Seven instantiations, versus 11 instantiations in your case.

Hope this helps (belatedly)!

Answer 2

template <std::size_t i, std::size_t n, class T, class... Rest>
struct extract_impl<i, n, T, Rest...>
{
    using type = typename extract_impl<i + 1, n, Rest...>::type;
};

When I recently implemented something like this, I've come up with an idea that a simple recursive implementation does not fit particularly well due to its linearity. Take millionth element of a list, and you instantiate a million of templates at compile time (to retrieve a single type!) So I've finally done it logarithmically (dynamic programming on types, eh?). In brief it is something like:

template<::std::size_t i, class L> struct drop
    : drop<i / 2, typename drop<i - i / 2, L>::type> {};

template<::std::size_t i, class L> using drop_t =
    typename drop<i, L>::type;


// Base cases are drops of sizes 0 and 1
template<class L> struct drop<0, L>: box<L> {};

template<::std::size_t i> struct drop<i, nil>: box<nil> {};

template<> struct drop<0, nil>: box<nil> {};

template<class H, class... Ts> struct drop<1, list<H, Ts...>>
    : box<list<Ts...>> {};


// Head extractor, once we've dropped all the preceding elements
template<class L> struct car;

template<class L> using car_t = typename car<L>::type;

template<class H, class... Ts> struct car<list<H, Ts...>>: box<H> {};


// The element extractor itself
template<::std::size_t i, class L> using element =
    ::std::enable_if<i < size_v<L>, car_t<drop_t<i, L>>>;

template<::std::size_t i, class L> using element_t
    = type_t<element<i, L>>;

(type_t is a lazy member-type extractor defined in another file. box<T> is simply the inverse, a struct with internal typedef type = T. size_v is defined somewhere above, it is merely pack size for lists.)