枚举折叠表达式

Question

我有一些辅助代码可以使用编译时索引执行向量重组。生成的代码尽可能高效是最重要的。我依赖于带有折叠表达式的参数包，我想知道编写此类代码的最佳实践是什么。

一个实际的例子：假设有一个函数 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)> {});
}

有没有一种方法可以避免运行时变量和辅助函数来完成这项工作？

Answer 1

我认为不可能同时避免运行时变量和辅助函数（希望有人能反驳这一点）。

我非常喜欢你的第二个解决方案，但是......为 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[]().

但我也认为，使用好的优化器，不会有明显的差异。

Answer 2

It is of upmost importance that the generated code is as efficient as possible.

关于您的示例的附注：您应该确保性能不会受到按值传递函数参数的影响。 return 值相同。

Is there a way to get this done avoiding both runtime variables and an auxiliary function?

您可以实现可重用的辅助函数。例如，考虑以下代码。

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

枚举折叠表达式

Enumerating over a fold expression

c++

template-meta-programming

variadic-templates

fold-expression

c++17