Перечисление по кратному выражению - PullRequest
Новая
       42

Перечисление по кратному выражению

0 голосов
/ 19 января 2019

У меня есть некоторый вспомогательный код, который выполняет перестановку векторов, используя индексы времени компиляции. Крайне важно, чтобы сгенерированный код был максимально эффективным. Я полагаюсь на пакеты параметров с выражениями свертывания, и мне было интересно, как лучше всего писать такой код.

Практический пример: пусть существует функция insert, которая вставляет элементы контейнера y в контейнер x в позициях Ii, где позиции являются константами времени компиляции. Основная сигнатура этой функции будет выглядеть примерно так: 

template<size_t... Ii, size_t Xsize, size_t Size>
constexpr container<Xsize> insert(container<Xsize> x, container<Ysize> y);

И это вызывается так: insert<0, 2>(x, y). Я вижу две очевидные возможности реализации этого.

Во-первых: использование вспомогательной индексной переменной для итерации по y: 

template<size_t... Ii, size_t Xsize, size_t Size>
constexpr container<Xsize> insert(container<Xsize> x, container<Ysize> y) {
  int i = 0;
  ((x[Ii] = y[i++]), ...);
  return x;
}

Моя проблема с этим решением - переменная i: мне нужно полагаться на компилятор, чтобы оптимизировать его.

Второе решение позволяет избежать любых зависимостей во время выполнения, но требует вспомогательной функции, что делает всю реализацию довольно уродливой: 

template<size_t... Ii, size_t... Yi, size_t Xsize, size_t Size>
constexpr container<Xsize> insert_(container<Xsize> x, container<Ysize> y, std::index_sequence<Yi...>) {
  ((x[Ii] = y[Yi]), ...);
  return x;
}

template<size_t... Ii, size_t Xsize, size_t Size>
constexpr container<Xsize> insert(container<Xsize> x, container<Ysize> y) {
  return insert_<Ii...>(x,y, std::make_index_sequence<sizeof...(Ii)> {});
}

Есть ли способ сделать это, избегая как переменных времени выполнения, так и вспомогательной функции?

Ответы [ 2 ]

0 голосов
/ 19 января 2019

Крайне важно, чтобы сгенерированный код был максимально эффективным.

Просто примечание, касающееся вашего примера: вы должны убедиться, что производительность не страдает от передачи аргументов функции по значению. То же самое для возвращаемого значения.

Есть ли способ сделать это, избегая как переменных времени выполнения, так и вспомогательной функции?

Вы можете реализовать многократно используемые вспомогательные функции. В качестве примера рассмотрим следующий код. 

static_assert(__cplusplus >= 201703L, "example written for C++17 or later");

#include <cstddef>

#include <array>
#include <type_traits>
#include <utility>

namespace detail {

template<std::size_t... inds, class F>
constexpr void gen_inds_impl(std::index_sequence<inds...>, F&& f) {
  f(std::integral_constant<std::size_t, inds>{}...);
}

}// detail

template<std::size_t N, class F>
constexpr void gen_inds(F&& f) {
  detail::gen_inds_impl(std::make_index_sequence<N>{}, std::forward<F>(f));
}

// the code above is reusable

template<
  std::size_t... inds_out,
  class T, std::size_t size_out, std::size_t size_in
>
constexpr std::array<T, size_out> insert1(
  std::array<T, size_out> out,
  std::array<T, size_in> in
) {
  static_assert((... && (inds_out < size_out)));
  static_assert(sizeof...(inds_out) <= size_in);

  gen_inds<sizeof...(inds_out)>([&] (auto... inds_in) {
    ((out[inds_out] = in[inds_in]), ...);
  });

  return out;
}

Аналогичной альтернативой является static_for подход: 

static_assert(__cplusplus >= 201703L, "example written for C++17 or later");

#include <cstddef>

#include <array>
#include <type_traits>
#include <utility>

namespace detail {

template<std::size_t... inds, class F>
constexpr void static_for_impl(std::index_sequence<inds...>, F&& f) {
  (f(std::integral_constant<std::size_t, inds>{}), ...);
}

}// detail

template<std::size_t N, class F>
constexpr void static_for(F&& f) {
  detail::static_for_impl(std::make_index_sequence<N>{}, std::forward<F>(f));
}

// the code above is reusable

template<
  std::size_t... inds_out,
  class T, std::size_t size_out, std::size_t size_in
>
constexpr std::array<T, size_out> insert2(
  std::array<T, size_out> out,
  std::array<T, size_in> in
) {
  static_assert(sizeof...(inds_out) >= 1);

  static_assert((... && (inds_out < size_out)));
  static_assert(sizeof...(inds_out) <= size_in);

  constexpr std::size_t N = sizeof...(inds_out);

  static_for<N>([&] (auto n) {
    // note the constexpr
    constexpr std::size_t ind_out = std::array{inds_out...}[n];
    constexpr std::size_t ind_in = n;
    out[ind_out] = in[ind_in];
  });

  return out;
}
0 голосов
/ 19 января 2019

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

И мне очень нравится ваше второе решение, но ... как насчет использованияитераторы для y (если y поддерживает cbegin() и, очевидно, итераторы).

что-то вроде (осторожно: код не проверен) 

template <std::size_t Ii...., std::size_t Xsize, std::size_t Ysize>
constexpr container<Xsize> insert(container<Xsize> x, container<Ysize> const & y) {
   auto it = y.cbegin();
   ((x[Ii] = *it++), ...);
   return x;
}

Это почти ваше первое решение, нодоступ к y, увеличивающему итератор, должен быть (я полагаю, для последовательного обхода, для некоторых контейнеров) более эффективным (немного более эффективным), чем использование operator[]().

Но я также предполагаю, что с хорошим оптимизатором заметной разницы нет.

...