How to create an array from two index sequence at compile time

Question

(Spoiler - this is a self-answered question) Let's pretend I have two index sequences, for example using i1 = std::index_sequence<1, 3, 5, 7>; and using i2 = std::index_sequence<2, 4, 6, 8>;

I want to make an array (at compile time) which would have 8 elements in it in sequence: 1, 2, 3, 4, 5, 6, 7, 8, so that following code would work (say, at global scope):

std::array<int, 8> arr = make_array(i1{}, i2{});

Note: if I just want one sequence, the solution is straightforward:

template<size_t... Ix>
constexpr auto make_arr(std::index_sequence<Ix...> )
    return std::array{Ix...};
}

But it is not that trivial if I need to join two sequences, for example, this doesn't work:

template<size_t... Ix1, size_t... Ix2>
constexpr auto make_arr(std::index_sequence<Ix1...>, std::index_sequence<Ix2...>)
    return std::array{(Ix1, Ix2)...};
}

(Above code will just populate array with values from second sequence).

Another potential solution would be to use constexpr function which would first define an array with default values, and than copy values from index sequences into it, but while that work with ints, that wouldn't work with some more elaborate types, which are not default-constructible (obviously, they wouldn't be part of index sequences, but they could be something else).

Is there any solution which would not require looping and default-constructing values? Any available C++ standard is fair game.

Answer 1

With some utilities to extract first number from std::index_sequence, you might do:

template <typename Seq> struct pop_front;
template <typename Seq> using pop_front_t = typename pop_front<Seq>::type;
template <std::size_t I, std::size_t ... Is> struct pop_front<std::index_sequence<I, Is...>>
{
    using type = std::index_sequence<Is...>;
};

template <std::size_t I, std::size_t ... Is>
constexpr std::size_t get_front(std::index_sequence<I, Is...>) { return I; }

template <std::size_t ... Res, typename ... Seqs>
auto make_interleaved_seq(std::index_sequence<Res...>, Seqs...)
{
    if constexpr (((Seqs::size() == 0) && ...)) {
        return std::index_sequence<Res...>{};
    } else {
        static_assert(((Seqs::size() != 0) && ...), "Sequences don't have the same size");
        return make_interleaved_seq(std::index_sequence<Res..., get_front(Seqs{})...>{},
                                    pop_front_t<Seqs>{}...);
    }
}

template <std::size_t ... Is>
constexpr std::array<std::size_t, sizeof...(Is)> make_array(std::index_sequence<Is...>)
{
    return {{Is...}};
}

template <typename ... Seqs>
auto make_interleaved_array(Seqs... seqs)
{
    return make_array(make_interleaved_seq(std::index_sequence<>{}, seqs...));
}

Demo

Answer 2

So far I know of two solutions.

In the first one, I managed to do it using C++ fold expressions and operator overloading. This code is terrible, and I am not proud of it - but it is there. Everyone is welcome to comment and contribute:

#include <utility>
#include <array>

struct Int {
    size_t i;
};

constexpr std::array<Int, 2> operator+(Int i1, Int i2) {
    return {i1, i2};
}

template<size_t SZ, size_t... Ix>
constexpr auto concat(std::array<Int, 2> arr1, std::array<Int, SZ> arr2, std::index_sequence<Ix...>)
{
    return std::array<Int, SZ+2>{arr1[0], arr1[1], arr2[Ix]...};
}

template<size_t SZ>
constexpr auto operator+ (std::array<Int, 2> arr1, std::array<Int, SZ> arr2) {
    return concat(arr1, arr2, std::make_index_sequence<SZ>{});
}


template<size_t SZ, size_t... Ix>
constexpr auto convert_impl(std::array<Int, SZ> arr, std::index_sequence<Ix...>) {
    return std::array{arr[Ix].i...};
}

template<size_t SZ>
constexpr auto convert(std::array<Int, SZ> arr) {
    return convert_impl(arr, std::make_index_sequence<SZ>{});
}

template<size_t... IX1, size_t... IX2>
constexpr auto make_arr(std::index_sequence<IX1...>, std::index_sequence<IX2...>) {

    return convert(((Int{IX1} + Int{IX2})+ ...));
}

using i1 = std::index_sequence<1, 3, 5, 7>;
using i2 = std::index_sequence<2, 4, 6, 8>;
auto k = make_arr(i1{}, i2{});

Second solution is a way better:

#include <utility>
#include <array>

template<size_t... Ix, class T, size_t SZ>
auto concat(T t1, T t2, std::array<T, SZ> arr, std::index_sequence<Ix...>) {
    return std::array{t1, t2, arr[Ix]...};
}

template<size_t i0, size_t... Ix0, size_t i1, size_t... Ix1>
auto make_array(std::index_sequence<i0, Ix0...>, std::index_sequence<i1, Ix1...>) {

    if constexpr (sizeof...(Ix0) > 0) {
        return concat(i0, 
                      i1,
                      make_array(std::index_sequence<Ix0...>{}, std::index_sequence<Ix1...>{}),
                      std::make_index_sequence<sizeof...(Ix0) + sizeof...(Ix1)>{}
                     );
    } else {
        return std::array{i0, i1};
    }
}

using i1 = std::index_sequence<1, 3, 5, 7>;
using i2 = std::index_sequence<2, 4, 6, 8>;
std::array<size_t, 8> k = make_array(i1{}, i2{});

Answer 3

What about a little play with indexes (shift, modulus... this sort of things) ?

#include <array>
#include <iostream>
#include <type_traits>

template <typename T, std::size_t ... Is>
constexpr auto make_arr_helper (T const & arr0,
                                std::index_sequence<Is...>)
 { 
   constexpr auto  DD2 = sizeof...(Is) >> 1;

   return std::array{arr0[(Is>>1)+(Is%2 ? DD2 : 0u)]...};
 }

template <std::size_t ... IX1, std::size_t ... IX2>
constexpr auto make_arr (std::index_sequence<IX1...>,
                         std::index_sequence<IX2...>)
 {
   static_assert( sizeof...(IX1) == sizeof...(IX2) );

   return make_arr_helper(std::array{IX1..., IX2...},
                          std::make_index_sequence<(sizeof...(IX1)<<1)>{});
 }

int main ()
 {
   using i1 = std::index_sequence<1, 3, 5, 7>;
   using i2 = std::index_sequence<2, 4, 6, 8>;

   constexpr auto k = make_arr(i1{}, i2{});

   for ( auto const & i : k )
      std::cout << i << ' ';

   std::cout << std::endl;
 }

-- EDIT --

The OP asks

But what if you want to merge 3 of them? 4? Would shifts/modules work?

Not shift (that in the 2 case is a simplification for multiplication and division by 2) but, using multiplication and division, works.

The make_arr_helper(), for case 3, is simple

template <typename T, std::size_t ... Is>
constexpr auto make_arr_helper (T const & arr0,
                                std::index_sequence<Is...>)
 { 
   constexpr auto  DD3 = sizeof...(Is) / 3u;

   return std::array{arr0[(Is/3u)+((Is%3) * DD3)]...};
 }

and passing the number of sequences as argument, can be easily generalized.

The following is the full case 3 example

#include <array>
#include <iostream>
#include <type_traits>

template <typename T, std::size_t ... Is>
constexpr auto make_arr_helper (T const & arr0,
                                std::index_sequence<Is...>)
 { 
   constexpr auto  DD3 = sizeof...(Is) / 3u;

   return std::array{arr0[(Is/3u)+((Is%3) * DD3)]...};
 }

template <std::size_t ... IX1, std::size_t ... IX2,
          std::size_t ... IX3>
constexpr auto make_arr (std::index_sequence<IX1...>,
                         std::index_sequence<IX2...>,
                         std::index_sequence<IX3...>)
 {
   static_assert( sizeof...(IX1) == sizeof...(IX2) );
   static_assert( sizeof...(IX1) == sizeof...(IX3) );

   return make_arr_helper(std::array{IX1..., IX2..., IX3...},
                          std::make_index_sequence<(sizeof...(IX1)*3u)>{});
 }

int main ()
 {
   using i1 = std::index_sequence<1, 4, 7, 10>;
   using i2 = std::index_sequence<2, 5, 8, 11>;
   using i3 = std::index_sequence<3, 6, 9, 12>;


   constexpr auto k = make_arr(i1{}, i2{}, i3{});

   for ( auto const & i : k )
      std::cout << i << ' ';

   std::cout << std::endl;
 }