6

(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.

Improve this question
6
  • Is 1 3 5 7 2 4 6 8 an acceptable result? Commented Mar 6, 2019 at 20:42
  • @NathanOliver not really, sorry. That would be trivial. Commented Mar 6, 2019 at 20:45
  • OK. Just want to make sure. Commented Mar 6, 2019 at 20:45
  • Do you want the two sequences sorted or interleaved? Commented Mar 6, 2019 at 22:06
  • @rubenvb in the example above they are interleaved Commented Mar 6, 2019 at 22:19

5 Answers 5

Reset to default
3

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

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

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

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

5 Comments

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>?
@alterigel my bad, I didn't copy the code properly. Fixed. This was the whole purpose of convert there.
The first solution does not give a std::array<int,8>.
@Handy999 it does in my tests. Can you provide yours?
Sorry my fault; you construct indeed a std::array<size_t,8> which happens not to be std::array<int,8>
1

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;
 }
Improve this answer

4 Comments

Creative. Upvoted. But what if you want to merge 3 of them? 4? Would shifts/modules work?
@SergeyA - 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.
Only if it fancies you :)
@SergeyA - 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.
0

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;
  }
}
Improve this answer

Comments

0

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).

Improve this answer

6 Comments

the question was just to interleave the sequences, not merge them, but I agree that constexpr is much more manageable than template metaprograming
Okey, this is possible the same way. The question was rather unclear on that.
This answer fails to take into account the limitations mentioned in the question - type might not be default constructible.
@Handy999 also requires assignable.
You have not asked for types that are not copy-assignable.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.