Transformation of compile time list of lists of types into a list of lists of indices

Question

I would like to transform a compile time list of lists of types into a list of lists of std::integral_constant indices. Appearently this requires some kind of 2d iota-like transformation.

Example source

template<typename... Ts> struct type_list{};
using L = type_list<
    type_list<>,
    type_list<>,
    type_list<>,
    type_list<>,
    type_list<int>,
    type_list<>,
    type_list<int>,
    type_list<int>,
    type_list<int>,
    type_list<int,double>,
    type_list<int,double>
>;

expected result

template<uint64_t V> using I = std::integral_constant<uint64_t, V>; // alias for better legibility
using R = type_list<
    type_list<>,
    type_list<>,
    type_list<>,
    type_list<>,
    type_list<I<0>>,
    type_list<>,
    type_list<I<1>>,
    type_list<I<2>>,
    type_list<I<3>>,
    type_list<I<4>, I<5>>,
    type_list<I<6>, I<7>>
>;

I think boost::mp11 fits this purpose perfectly, but I lack the experience to bring it all together. Please share your advice.

Answer 1

I think boost::mp11 fits this purpose perfectly, but I lack the experience to bring it all together. Please share your advice.

You are correct! Boost.Mp11 does fit this purpose perfectly.

This is basically a stateful fold. We have to keep track of how many values we've pushed so far, call that N. Then, for each new element of the list, L, that we're iterating on, we append a new list that is [N, N+1, ..., N+len(L)-1] and then do N += len(L) in the state.

For convenience, we can add a State:

template <class N, class L>
struct State {
    using value = N;
    using list = L;
};

An accumulating function that does what I described above:

template <class S, class L>
using F = State<
    // S::value + len(L)
    mp_plus<typename S::value, mp_size<L>>,
    mp_push_back<typename S::list,
        // iota just gives you [0, 1, ..., V-1]
        // so we need to add S::value to all of those
        mp_transform_q<
            mp_bind_front<mp_plus, typename S::value>,
            mp_iota<mp_size<L>>>>
    >;

And then lastly, we do the fold and pull out the list:

template <class L>
using types_to_ints = mp_fold<L, State<mp_size_t<0>, mp_list<>>, F>::list

Example demonstrating that it does the right thing.

Answer 2

Here's a solution using pure C++20.

First a little helper to prepend a type to a typelist:

template<class T, class List> struct prepend_type_list;

template<class T, class... Args>
struct prepend_type_list<T, type_list<Args...>> 
: std::type_identity<type_list<T, Args...>> {};

Our primary entry point is going to be this:

template <class List, std::size_t Idx = 0>
struct index;

We're going to index the list recursively, so need a base case for when List is empty:

template <std::size_t Idx>
struct index<type_list<>, Idx> : std::type_identity<type_list<>> {};

Now the recursive specialization. Since we have two levels of recursion (the outer list and the inner lists) we're going to write an index_inner helper which does the internal indexing, and gives us back the last index it used:

template <class Head, class... Tail, std::size_t Idx>
struct index<type_list<Head, Tail...>, Idx> {
    using inner = index_inner<Head, type_list<>, Idx>;
    using type = typename prepend_type_list<
                                typename inner::type, 
                                typename index<type_list<Tail...>, inner::index>::type
                          >::type;
};

Primary template for index_inner, which instead of building with tail recursion, is going to build up the list as it goes, so that it can keep track of the index (you could also do it tail-recursively and then reverse the list):

template <class List, class Build, std::size_t Idx>
struct index_inner;

When we're done, we're going to expose the max index and the built type list:

template <class Build, std::size_t Idx>
struct index_inner<type_list<>, Build, Idx> {
    using type = Build;
    static constexpr std::size_t index = Idx;
};

Finally, the recursive case:

template <class Head, class... Tail, class... Build, std::size_t Idx>
struct index_inner<type_list<Head, Tail...>, type_list<Build...>, Idx> 
: index_inner<type_list<Tail...>, type_list<Build..., I<Idx>>, Idx+1> {};

Then we can use index<L>::type to get R.

Live demo: https://godbolt.org/z/KT1dEMs5q

Answer 3

Here is another alternative

#include <ranges>
#include <algorithm>
#include <array>
#include <vector>
#include <numeric>

template <typename... Ts> 
constexpr auto type_list_to_vector(type_list<Ts...>) {
  return std::vector<int>(sizeof...(Ts));
}

template <auto arr> 
constexpr auto arr_to_type_list() {
  return []<std::size_t... Is>(std::index_sequence<Is...>) {
    return type_list<I<arr[Is]>...>{};
  }(std::make_index_sequence<arr.size()>{});
}

template <typename... Ts> 
constexpr auto transform(type_list<Ts...>) {
  auto v = [] {
    std::vector<std::vector<int>> v{type_list_to_vector(Ts{})...};
    std::ranges::iota(v | std::views::join, 0);
    return v;
  };
  return [&]<std::size_t... Xs>(std::index_sequence<Xs...>) {
    return type_list<decltype([&] {
      constexpr auto arr = [&] {
        std::array<int, v()[Xs].size()> arr{};
        std::ranges::copy(v()[Xs], arr.begin());
        return arr;
      }();
      return arr_to_type_list<arr>();
    }())...>{};
  }(std::index_sequence_for<Ts...>{});
}

The basic idea is to convert the following:

using L = type_list<
  type_list<>,
  type_list<>,
  type_list<int>,
  type_list<>,
  type_list<int>,
  type_list<int,double>
>;

into:

std::vector<std::vector<int>> v{{}, {}, {0}, {}, {0}, {0, 0}};

Then apply the algorithm:

ranges::iota(v | views::join, 0);

to get:

std::vector<std::vector<int>> v{{}, {}, {0}, {}, {1}, {2, 3}};

and finally convert the result back to

using L = type_list<
  type_list<>,
  type_list<>,
  type_list<I<0>>,
  type_list<>,
  type_list<I<1>>,
  type_list<I<2>,I<3>>
>;

Demo