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.

Kellda

Is 1 3 5 7 2 4 6 8 an acceptable result? – Absorptivity

@Absorptivity not really, sorry. That would be trivial. – Kellda

OK. Just want to make sure. – Absorptivity

Do you want the two sequences sorted or interleaved? – Flexure

@Flexure in the example above they are interleaved – Kellda

I'm just asking because the solution will be different if sorting also needs to happen. – Flexure

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

Agree

Yeah, this is good as well. Head-tail solution not unlike the second one in my answer. – Kellda

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{});

Kellda

Very cool. I just tested this and noticed that k is actually a std::array<Int, 8> where Int is a struct { size_t i; };. Do you think you could add a reduction from std::array<Int, N> to std::array<size_t, N>? – Leeds

@alterigel my bad, I didn't copy the code properly. Fixed. This was the whole purpose of convert there. – Kellda

The first solution does not give a std::array<int,8>. – Victoir

@Victoir it does in my tests. Can you provide yours? – Kellda

Sorry my fault; you construct indeed a std::array<size_t,8> which happens not to be std::array<int,8> – Victoir

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;
 }

Cesaro

Creative. Upvoted. But what if you want to merge 3 of them? 4? Would shifts/modules work? – Kellda

@Kellda - shift, in this case, is only a substitute for "multiplication for 2" and "division for 2"; so... substituting shift with multiplication and division... why not? Give me some minutes and I try to prepare the 3 case. – Cesaro

Only if it fancies you :) – Kellda

@Kellda - case 3 added; as you can see, the make_arr_helper() can be easily generalized (and, maybe, parametrized with the number of sequences). The problem can be in make_arr() if you want generalize the number of sequences: I don't know how to concatenate the indexes of a variadic sequence of std::index_sequence. – Cesaro

Answer 4

This seems like an interesting challenge, but the purpose is not entirely clear to me. In particular, I do not understand what you mean by "something else" in your explanations:

Another potential solution [...] 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).

Can you give an example that demonstrates the requirements on the desired technique? If the requirement is "no loops, no default construction" then a solution may be std::forward_as_tuple followed by std::tuple_cat followed by "detie into array":

#include <cstddef>

#include <array>
#include <iostream>
#include <tuple>
#include <type_traits>
#include <utility>

template<std::size_t... gs, class T0, class... Ts>
constexpr std::array<std::decay_t<T0>, 1+sizeof...(Ts)> detie_into_array(
  std::index_sequence<gs...>,
  const std::tuple<T0&&, Ts&&...>& tuple// TODO: think about the type deduction
) {
  static_assert(
    std::is_same<
      std::index_sequence<gs...>,
      std::make_index_sequence<1+sizeof...(Ts)>
    >{}
  );

  static_assert(
    std::conjunction<
      std::is_same<std::decay_t<T0>, T0>,
      std::is_same<std::decay_t<T0>, Ts>...
    >{}
  );

  return {std::get<gs>(tuple)...};
}



template<int... is, int... js>
constexpr auto make_array(
  std::integer_sequence<int, is...>,
  std::integer_sequence<int, js...>
) {
  static_assert(sizeof...(is) == sizeof...(js), "How to interleave otherwise?");

  using GlobalSeq = std::make_index_sequence<sizeof...(is) + sizeof...(js)>;

  return detie_into_array(
    GlobalSeq{},
    std::tuple_cat(
      std::forward_as_tuple(is, js)...// TODO: think about the type deduction
    )// NOTE: first idea was `std::tie`, but that is based on lvalue refs
  );
}

////////////////////////////////////////////////////////////////////////////////

template<class T>
void inspect(const T&) {
  std::cout << __PRETTY_FUNCTION__ << std::endl;
}

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

  auto arr = make_array(i1{}, i2{});

  inspect(arr);
  for(auto&& i : arr) {
    std::cout << i << std::endl;
  }
}

Bonne

Answer 5

In modern C++, I would always prefer constexpr normal-programming instead of template meta-programming.

Unfortunately, the C++ algorithms are not yet constexpr. So, we have to reimplement them:

#include<array>
#include<utility>
#include<algorithm>

template<std::size_t... Ix1, std::size_t... Ix2>
constexpr auto make_array(std::index_sequence<Ix1...>,std::index_sequence<Ix2...>)
{
    const auto a1 = std::array{Ix1...};
    const auto a2 = std::array{Ix2...};
    constexpr std::size_t N1 = a1.size();
    constexpr std::size_t N2 = a2.size();

    std::array<std::size_t,N1+N2> result{};   // (a)
    // std::merge(a1.begin(), a1.end(), a2.begin(), a2.end(), result.begin());
    // (b)
    std::size_t i=0, j=0, k=0;
    while (k<N1+N2)
    {
        if(i<N1 && (j==N2||a1[i] < a2[j]))
            { result[k] = a1[i]; ++k; ++i; }
        else
            { result[k] = a2[j]; ++k; ++j; }
    }
    // end of (b)
    return result;
}

using i1 = std::index_sequence<1, 3, 5, 7>; 
using i2 = std::index_sequence<2, 4, 6, 8>;


int main() {
    constexpr auto a = make_array(i1{},i2{});
    // ...
}

If std::merge was constexpr, the function join_arr was a 5-liner.

If you do not know that i1 and i2 are sorted, you need to implement your own constexpr version of std::sort.

If you want to combine the index sequences just alternating, you can do it analogously using

    if (N1!=N2) throw std::logic_error("The index sequences need to have the same length.");
    for (std::size_t i=0; i<N1; ++i)
    {
        result[2*i  ] = a1[i];
        result[2*i+1] = a2[i];
    }

instead of (b). The throw statement is no problem as long as you do not actually throw. (So, the exception is translated to a compile-time error. This is exactly what you want.)

Finally, if the type is not default constructibe, you can write

std::array<T,N1+N2> result{a1[0]};

instead of (a), i.e., you fill your results with some random instance. This only requires copy constructible (which all the presented solutions require).

Victoir

the question was just to interleave the sequences, not merge them, but I agree that constexpr is much more manageable than template metaprograming – Bethlehem

Okey, this is possible the same way. The question was rather unclear on that. – Victoir

This answer fails to take into account the limitations mentioned in the question - type might not be default constructible. – Kellda

@Victoir also requires assignable. – Kellda

You have not asked for types that are not copy-assignable. – Victoir

@Victoir I did not, but I see this as a drawback of your solution. Other solutions presented here do not require this. – Kellda