Как создать массив из двух последовательностей индекса во время компиляции - PullRequest
6 голосов
/ 06 марта 2019

( Спойлер - это вопрос с самостоятельным ответом) Давайте представим, что у меня есть две индексные последовательности, например using i1 = std::index_sequence<1, 3, 5, 7>; и using i2 = std::index_sequence<2, 4, 6, 8>;

Я хочу создать массив (при компиляции раз), который будет иметь 8 элементов в последовательности: 1, 2, 3, 4, 5, 6, 7, 8, чтобы следующий код работал (скажем, в глобальной области видимости):

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

Примечание: если я просто хочу одну последовательность, решение будет простым:

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

Но это не так тривиально, если мне нужно объединить две последовательности, например, это не работает:

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

(Приведенный выше код будет просто заполнять массив значениями из второй последовательности).

Другим потенциальным решением было бы использование функции constexpr, которая сначала определяла бы массив со значениями по умолчанию, а затем копировала бы значения из последовательностей индекса в него, но, хотя это работает с целыми числами, это не сработает с некоторыми более сложными типы, которые не являются конструируемыми по умолчанию (очевидно, они не будут частью последовательностей индекса, но они могут быть чем-то другим).

Есть ли какое-либо решение, которое не требовало бы циклических значений и значений по умолчанию? Любой доступный стандарт C ++ является честной игрой.

Ответы [ 5 ]

2 голосов
/ 07 марта 2019

С некоторыми утилитами для извлечения первого числа из std::index_sequence вы можете сделать:

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

Демо

1 голос
/ 07 марта 2019

Как насчет небольшой игры с индексами (сдвиг, модуль ... такого рода вещи)?

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

- РЕДАКТИРОВАТЬ -

ОП спрашивает

Но что, если вы хотите объединить 3 из них?4?Будут ли сдвиги / модули работать?

Не сдвиг (что в случае 2 является упрощением умножения и деления на 2), но, используя умножение и деление, работает.

The make_arr_helper(), для случая 3, прост

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)]...};
 }

и передача числа последовательностей в качестве аргумента может быть легко обобщена.

Ниже приведен полный пример случая 3

#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;
 }
1 голос
/ 06 марта 2019

До сих пор я знал о двух решениях.

В первом мне удалось сделать это с помощью выражений свертывания C ++ и перегрузки операторов.Этот код ужасен, и я не горжусь этим - но он есть.Каждый может комментировать и вносить свой вклад:

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

Второе решение намного лучше:

#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{});
0 голосов
/ 07 марта 2019

В современном C ++ я бы всегда предпочел нормальное программирование constexpr вместо метапрограммирования шаблонов.

К сожалению, алгоритмы C ++ еще не constexpr.Итак, мы должны переопределить их:

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

Если std::merge было constexpr, функция join_arr была 5-строчной.

Если вы не знаете, что i1 и i2 отсортированы, вам нужно реализовать собственную constexpr версию std::sort.

Если вы хотите объединить последовательности индексов, просто чередуясь, вы можете сделать это аналогично, используя

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

вместо (б).Оператор throw не проблема, если вы на самом деле не бросаете.(Таким образом, исключение преобразуется в ошибку времени компиляции. Это именно то, что вам нужно.)

Наконец, если тип не является конструктором по умолчанию, вы можете написать

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

вместо (а), т. е. вы заполняете свои результаты некоторым случайным экземпляром.Для этого требуется только копируемый конструктив (чего требуют все представленные решения).

0 голосов
/ 07 марта 2019

Это кажется интересным испытанием, но цель не совсем понятна для меня. В частности, я не понимаю, что вы подразумеваете под «чем-то другим» в своих объяснениях:

Другое потенциальное решение [...] не будет работать с некоторыми другими сложные типы, которые не являются конструируемыми по умолчанию (очевидно, они не будет частью индексных последовательностей, , но они могут быть чем-то еще ).

Можете ли вы привести пример, демонстрирующий требования к желаемой технике? Если требованием является «без циклов, без построения по умолчанию», то решением может быть std::forward_as_tuple, за которым следует std::tuple_cat, за которым следует «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;
  }
}
...