logo标签列表

使C++14的constexpr函数兼容C++11

c++c++11templatesvariadic-templatestemplate-meta-programming
12

我写了一个名为multi_array的类，它是std::array在多维上的扩展。

template <typename T, std::size_t... N>
class multi_array {
    template <std::size_t... I, typename... Idx>
    constexpr std::size_t linearized_index(meta::index_sequence<I...>,
                                           Idx... idx) const {
        std::size_t index = 0;
        using unpack = std::size_t[];
        (void)unpack{0UL,
                     ((void)(index = (index + unpack{std::size_t(idx)...}[I]) *
                                     meta::pack_element<I + 1, N...>::value),
                      0UL)...};
        return index + unpack{std::size_t(idx)...}[sizeof...(idx) - 1];
    }

    // Storage
    T m_data[meta::product<N...>::value];

    //...
};

我已经实现了在C++14中使用constexpr元素访问的功能。问题出在函数linearized_index上。它可以在编译时计算线性索引。为了这样做，它以某种方式减少索引元组和维度元组。对于这个缩减操作，我需要函数内部的一个局部变量，但是在C++11中不允许这样做。我的环境不允许使用C++14。我能否以某种方式重写此函数以使其在C++11中工作？
我已经准备了一个完整（不是最小的）示例，在C++14中编译通过。
#include <cstddef> // std::size_t

namespace meta {

// product

template <std::size_t...>
struct product;

template <std::size_t head, std::size_t... dim>
struct product<head, dim...> {
    static constexpr std::size_t const value = head * product<dim...>::value;
};

template <>
struct product<> {
    static constexpr std::size_t const value = 1;
};

// pack_element

template <std::size_t index, std::size_t head, std::size_t... pack>
struct pack_element {
    static_assert(index < sizeof...(pack) + 1, "index out of bounds");
    static constexpr std::size_t const value =
        pack_element<index - 1, pack...>::value;
};

template <std::size_t head, std::size_t... pack>
struct pack_element<0, head, pack...> {
    static constexpr std::size_t const value = head;
};

// index_sequence

// https://dev59.com/G3M_5IYBdhLWcg3w2XLw#24481400
template <std::size_t... I>
struct index_sequence {};

template <std::size_t N, std::size_t... I>
struct make_index_sequence : public make_index_sequence<N - 1, N - 1, I...> {};

template <std::size_t... I>
struct make_index_sequence<0, I...> : public index_sequence<I...> {};

} // namespace meta

template <typename T, std::size_t... N>
class multi_array {
    template <std::size_t... I, typename... Idx>
    constexpr std::size_t linearized_index(meta::index_sequence<I...>,
                                           Idx... idx) const {
        std::size_t index = 0;
        using unpack = std::size_t[];
        (void)unpack{0UL,
                     ((void)(index = (index + unpack{std::size_t(idx)...}[I]) *
                                     meta::pack_element<I + 1, N...>::value),
                      0UL)...};
        return index + unpack{std::size_t(idx)...}[sizeof...(idx) - 1];
    }

    // Storage
    T m_data[meta::product<N...>::value];

public:
    constexpr multi_array() {}

    template <typename... U>
    constexpr multi_array(U... data) : m_data{T(data)...} {}

    template <typename... Idx>
    constexpr T operator()(Idx... idx) const noexcept {
        std::size_t index = linearized_index(
            meta::make_index_sequence<sizeof...(idx) - 1>{}, idx...);
        return m_data[index];
    }
};

int main() {
    constexpr multi_array<double, 2, 2> const b = {0, 0, 0, 1};
    static_assert(b(1, 1) == 1, "!");
}

在Wandbox上实时演示(C++14) 和 在Wandbox上实时演示(C++11)

4个回答
7
您使用index的关键部分是一个迭代循环：
index = (index*a) + b

在您自己的C++14解决方案中，使用了一个解包参数包的技巧。在C++11中，您可以通过递归的constexpr函数来表达它:

struct mypair {
    size_t a;
    size_t b;
};

constexpr std::size_t foo(std::size_t init) {
    return init;
}

template<class... Pair>
constexpr std::size_t foo(std::size_t init, mypair p0, Pair... ps) {
    return foo((init+p0.a)*p0.b, ps...);
}

我们使用 mypair 而不是 std::pair，因为C++11中的 std::pair 构造函数不是 constexpr。然后你的迭代循环可以被字面上地翻译成：

    template <std::size_t... I, typename... Idx>
    constexpr std::size_t linearized_index(meta::index_sequence<I...>,
                                           Idx... idx) const {
        using unpack = std::size_t[];
        return foo(0, mypair{unpack{std::size_t(idx)...}[I], meta::pack_element<I+1, N...>::value}...) + unpack{std::size_t(idx)...}[sizeof...(idx) - 1];
    }

Live Demo

4
如果在operator()中，不是调用
 std::size_t index = linearized_index(
    meta::make_index_sequence<sizeof...(idx) - 1>{}, idx...);

you call

 std::size_t index = linearized_index<N...>(idx...);

或者更好的方法（使operator()成为constexpr）：

 return m_data[linearized_index<N...>(idx...)];

您可以将 linearized_index() 递归地改写如下。
  // ground case
  template <std::size_t>
  constexpr std::size_t linearized_index (std::size_t idx0) const
   { return idx0; }

  // recursive case
  template <std::size_t, std::size_t... Is, typename... Idx>
  constexpr std::size_t linearized_index (std::size_t idx0,
                                          Idx ... idxs) const
   { return idx0 * meta::product<Is...>::value
        + linearized_index<Is...>(idxs...); }

如果您喜欢的话，地面情况可以写成如下形式：
  template <typename = void>
  constexpr std::size_t linearized_index () const
   { return 0; }

请注意，您不再需要使用 meta::index_sequence、meta::make_index_sequence 或 meta::pack_element。以下是一个完整的 C++11 编译示例。
#include <cstddef> // std::size_t

namespace meta
 {
   template <std::size_t...>
    struct product;

   template <std::size_t head, std::size_t... dim>
   struct product<head, dim...>
    { static constexpr std::size_t const value
         = head * product<dim...>::value; };

   template <>
   struct product<>
    { static constexpr std::size_t const value = 1; };

} // namespace meta

template <typename T, std::size_t... N>
class multi_array
 {
   private:
      // ground case
      template <std::size_t>
      constexpr std::size_t linearized_index (std::size_t idx0) const
       { return idx0; }

      // alternative ground case
      //template <typename = void>
      //constexpr std::size_t linearized_index () const
      // { return 0; }

      // recursive case
      template <std::size_t, std::size_t... Is, typename... Idx>
      constexpr std::size_t linearized_index (std::size_t idx0,
                                              Idx ... idxs) const
       { return idx0 * meta::product<Is...>::value
            + linearized_index<Is...>(idxs...); }

      // Storage
      T m_data[meta::product<N...>::value];

   public:
      constexpr multi_array()
       { }

      template <typename ... U>
      constexpr multi_array(U ... data) : m_data{T(data)...}
       { }

      template <typename... Idx>
      constexpr T operator() (Idx... idx) const noexcept
       { return m_data[linearized_index<N...>(idx...)]; }
 };

int main()
 {
   constexpr multi_array<double, 2, 2> const b = {0, 0, 0, 1};

   static_assert( b(1, 1) == 1, "!" );

   constexpr multi_array<double, 4, 3, 2> const c
    { 0, 0,   0, 0,   0, 0,
      0, 0,   0, 0,   0, 0,
      0, 0,   2, 0,   0, 0,
      0, 0,   0, 0,   0, 1};

   static_assert( c(3, 2, 1) == 1, "!" );
   static_assert( c(2, 1, 0) == 2, "!" );
 }

奖励建议：如果您添加以下constexpr函数(multi_array内的static方法?)
  constexpr static std::size_t prod ()
   { return 1U; }

  template <typename ... Args>
  constexpr static std::size_t prod (std::size_t v, Args ... vs)
   { return v * prod(vs...); }

您可以通过调用 struct product 来删除其内容。
  // Storage
  T m_data[prod(N...)];

并且。
  // recursive case
  template <std::size_t, std::size_t... Is, typename... Idx>
  constexpr std::size_t linearized_index (std::size_t idx0,
                                          Idx ... idxs) const
   { return idx0 * prod(Is...) + linearized_index<Is...>(idxs...); }
这也是一个非常好的答案，我很快就会用一点小赏金来奖励它。 - Henri Menke
顺便说一下，在C++11中我无法使operator()成为constexpr，因为其中constexpr意味着const（这非常令人恼火）。 - Henri Menke
@HenriMenke - 或许可以像 operator[]/at() 的传统一样提供两个版本？template <typename... Idx> constexpr T const & operator() (Idx... idx) const { return m_data[linearized_index<N...>(idx...)]; } template <typename... Idx> T & operator() (Idx... idx) { return m_data[linearized_index<N...>(idx...)]; }？ - max66
2

避免使用数组的简单方法：

#include <tuple>
#include <type_traits>
#include <cstddef>

template
<
    typename          x_IndexTypesTuple
,   ::std::size_t ... x_dimension
> class
t_MultiIndexImpl;

template
<
    typename          x_LeadingIndex
,   typename ...      x_Index
,   ::std::size_t     x_leadding_dimension
,   ::std::size_t ... x_dimension
> class
t_MultiIndexImpl
<
    ::std::tuple<x_LeadingIndex, x_Index ...>, x_leadding_dimension, x_dimension ...
> final
{
    static_assert
    (
        ::std::is_same<::std::size_t, x_LeadingIndex>::value
    ,   "index type must be ::std::size_t"
    );

    public: static constexpr auto
    Op
    (
        ::std::size_t const  stride_size
    ,   x_LeadingIndex const leading_index
    ,   x_Index const ...    index
    ) -> ::std::size_t
    {
        return stride_size * leading_index
            + t_MultiIndexImpl<::std::tuple<x_Index ...>, x_dimension ...>::Op
            (
                stride_size * x_leadding_dimension, index ...
            );
    }
};

template<> class
t_MultiIndexImpl<::std::tuple<>> final
{
    public: static constexpr auto
    Op(::std::size_t const /*stride_size*/) -> ::std::size_t
    {
        return ::std::size_t{0};
    }
};

template<::std::size_t ... x_dimension, typename ... x_Index> inline constexpr auto
Caclculate_MultiIndex(x_Index const ... index) -> ::std::size_t
{
    static_assert
    (
        sizeof...(x_dimension) == sizeof...(x_Index)
    ,   "arguments count must match dimensions count"
    );
    return t_MultiIndexImpl<::std::tuple<x_Index ...>, x_dimension ...>::Op(::std::size_t{1}, index ...);
}

online compiler | godbolt

最终我想在CUDA代码中使用multi_array，所以不用std::tuple :( 但是当然会给你一个赞，因为你的解决方案很好！ - Henri Menke
1
@HenriMenke 嗯，这里的元组仅用于打包索引类型，因此从技术上讲，它可以被任何带有参数包的随机类模板替换或完全删除。 - user7860670
你是否总是在 std 前面加上 ::？你曾经因为简单的 std::something 而遇到过任何问题吗？ - YSC
@YSC 我会在全局命名空间中的所有名称前加上 :: 前缀。是的，我确实经常遇到代码不遵循相同约定的问题。我也遇到过 std:: 不是 ::std:: 的问题：情况1 - 库定义了一个嵌套的 std 命名空间，其中包含实现未来标准的内容（用于回溯），情况2 - enum std {vector，list ...}（用于序列化标准容器）。因此，我认为没有理由不对 std 命名空间进行前缀处理，而不是例外处理。 - user7860670
1
我通过递归重写函数，成功获得了一个与C++11兼容的解决方案。这不仅能够正常运行，而且阅读起来更加清晰易懂。
template <typename... Idx>
constexpr std::size_t linearized_index(std::size_t n, Idx... idx) const {
    using unpack = std::size_t[];
    return unpack{std::size_t(idx)...}[n] +
           (n == 0 ? 0
                   : unpack{std::size_t(N)...}[n] *
                         linearized_index(n - 1, idx...));
}
我发现另一种使用模板特化的解决方案，避免了递归函数调用，并将其替换为递归实例化。
namespace meta {

template <size_t n, size_t... N>
struct linearized_index {
    template <typename... Idx>
    constexpr std::size_t operator()(Idx... idx) const {
        using unpack = std::size_t[];
        return unpack{std::size_t(idx)...}[n] +
               unpack{std::size_t(N)...}[n] *
                   linearized_index<n - 1, N...>{}(idx...);
    }
};

template <size_t... N>
struct linearized_index<0, N...> {
    template <typename... Idx>
    constexpr std::size_t operator()(Idx... idx) const {
        using unpack = std::size_t[];
        return unpack{std::size_t(idx)...}[0];
    }
};

} // namespace meta

并且 multi_array 调用运算符

template <typename... Idx>
constexpr T operator()(Idx... idx) const noexcept {
    return m_data[meta::linearized_index<sizeof...(idx) - 1, N...>{}(
        idx...)];
}

这将生成完美的汇编代码：https://godbolt.org/g/8LPkBZ
很遗憾，这会破坏你的优化器。原始版本。 - Passer By
2
哎呀，我错过了一个表达式。这确实会产生最佳汇编。 - Passer By
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接