使用奇怪的循环模板模式 (CRTP) 计算多维数组的线性索引

Question

我正在用 C++ 编写一个多维数组 class 并且想要它的静态和动态内存版本。根据我的之一的回答，我使用 CRTP 定义了一个基础 class，然后它可以访问具有连续内存的相应数据容器（std::array 和 std::vector）在派生的 classes.

我希望在基础 class 本身中实现多维下标运算符（例如，访问 4x3 矩阵的 (1, 2) 条目，该矩阵的 12 个条目连续存储在内存中），以便以避免代码重复。请注意，我只是选择了下标运算符，因为它是最简单的 class 方法，可以说明我希望实现的目标。我试图将@Jarod42 给出的的多维下标线性化解决方案应用到我的 CRTP 案例中。但是，我不确定如何在派生的 classes 中存储数组维度，以便在计算线性化索引时在基础 class 中推断它们。我希望下面的代码能清楚地说明我的问题（我正在使用 C++20 进行编译）：

#include <array>
#include <cassert>
#include <vector>

/** Multi-dimensional Array Base Class with CRTP. */
template <class derived, class T>
class MultiDimArray
{
private:
  constexpr derived& Derived() noexcept { return static_cast<derived&>(*this); }

  constexpr const derived& Derived() const noexcept { return static_cast<const derived&>(*this); }

protected:
  constexpr MultiDimArray() {}

public:
  // I've butchered the syntax in the following subscript operators, but I hope it captures what I intend to do.
  constexpr const T& operator()(HookTypeToPack<Derived().Dimensions, std::size_t> ...Is) const {
    return *(this->Derived()[ComputeIndex<Derived().Dimensions...>(Is...)]);
  }

  constexpr T& operator()(HookTypeToPack<Derived().Dimensions, std::size_t> ...Is) {
    return *(this->Derived()[ComputeIndex<Derived().Dimensions...>(Is...)]);
  }
};

/** Static Multi-dimensional Array Class */
template <class T, std::size_t ...Dims>
class StaticMultiDimArray : public std::array<T, (Dims * ...)>,
                            public MultiDimArray<StaticMultiDimArray<T, (Dims * ...)>, T>
{
private:
  constexpr static std::size_t nEntries = (Dims * ...);
  constexpr static std::tuple<HookTypeToPack<Dims, std::size_t>...> Dimensions = std::make_tuple(Dims...);
  friend MultiDimArray<StaticMultiDimArray<T, (Dims * ...)>, T>;

public:
  constexpr StaticMultiDimArray() : std::array<T, nEntries>(InitStaticArray<T, nEntries>(0.0)) {}
};

/** Dynamic Multi-dimensional Array Class */
template <class T>
class DynamicMultiDimArray : public std::vector<T>, public MultiDimArray<DynamicMultiDimArray<T>, T>
{
private:
  std::size_t nEntries;
  std::tuple<...> Dimensions; // Not sure what to use here considering a tuple is immutable
  friend MultiDimArray<DynamicMultiDimArray<T>, T>;

public:
  DynamicMultiDimArray() : std::vector<T>() {}

  template <typename ...Dims>
  DynamicMultiDimArray(Dims ...dimensions) : std::vector<T>((dimensions * ...), 0.0) { Resize(dimensions...); }

  template <typename ...Dims>
  void Resize(Dims ...dimensions)
  {
    nEntries = (dimensions * ...);
    this->resize(nEntries);
    // store dimensions in Dimensions...
  }
};

上面用到的支持函数InitStaticArray、HookTypeToPack、ComputeIndex定义如下：

template <class T, std::size_t size>
constexpr auto InitStaticArray(const T& value)
{
  std::array<T, size> arr;
  std::fill(arr.begin(), arr.end(), value);
  return arr;
}

template <std::size_t, typename T>
using HookTypeToPack = T;

template <std::size_t ...Dims>
constexpr std::size_t ComputeIndex(HookTypeToPack<Dims, std::size_t> ...multi_index)
{
  constexpr std::size_t dims_arr[] = {Dims...};
  std::size_t multi_index_arr[] = {multi_index...};

  std::size_t index(0), factor(1);
  for(int i = 0; i < sizeof...(Dims); i++)
  {
    assert(0 <= multi_index_arr[i] && multi_index_arr[i] < dims_arr[i]);
    index += factor * multi_index_arr[i];
    factor *= dims_arr[i];
  }

  assert(0 <= index && index < (Dims * ...));
  return index;
}

任何人都可以给我一些关于如何在 StaticMultiDimArray 和 DynamicMultiDimArray 中存储数组维度的建议，以便可以在 MultiDimArray 中的 operator() 重载中适当地调用它们？

Answer 1

有几个选项。您已经暗示的一个：将维度存储在派生 class 中。但是，不要使用 std::tuple;这允许每个元素具有不同的类型，而我们只希望每个维度的大小为 std::size_t。对静态数组使用 std::array，对动态数组使用 std::vector：

template <class T, std::size_t ...Dims>
class StaticMultiDimArray :
    public std::array<T, ...>,
    public MultiDimArray<...>
{
  constexpr static std::array dimensions{Dims...};
  ...
};

template <class T>
class DynamicMultiDimArray :
    public std::vector<T>,
    public MultiDimArray<...>
{
  std::vector<std::size_t> dimensions;
  ...
};

您也不需要将 DynamicMultiDimArray 的构造函数设为模板，而是可以让它以 std:initializer_list 作为参数，如下所示：

DynamicMultiDimArray(std::initializer_list<std::size_t> dimensions) :
    std::vector<T>(std::accumulate(dimensions.begin(), dimensions.end(), std::size_t{1}, std::multiplies<std::size_t>())),
    Dimensions(dimensions) {}

是的，实际元素向量的初始化现在看起来很难看。我建议不要为此使用继承，而是使用组合。那么可以先初始化维度，再初始化数据的array/vector，并且可以在MultiDimArray中创建一个成员变量来计算条目数：

template <class derived, class T>
class MultiDimArray {
  ...
  constexpr std::size_t nEntries() const {
    const auto &dimensions = Derived().dimensions;
    return std::accumulate(dimensions.begin(), dimensions.end(), std::size_t{1}, std::multiplies<std::size_t>());
  }
  ...
};

template <class T>
class DynamicMultiDimArray :
    public MultiDimArray<...>
{
  std::vector<std::size_t> dimensions;
  std::vector<T> data;
  ...
public:
  DynamicMultiDimArray(std::initializer_list<std::size_t> dimensions) :
      Dimensions(dimensions),
      data(nEntries()) {}
};

同样，您可以让 operator() 为索引取一个 std::initializer_list<std::size_t>。使用它的代码如下所示：

DynamicMultiDimArray dimarr({3, 5, 7}); // create new array
...
std::cout << dimarr({1, 2, 3}) << '\n'; // print element at index 1, 2, 3

这避免了很多模板麻烦。您甚至可以考虑创建自定义多维索引类型而不是 std::initializer_list<std::size_t>，这样可以更轻松地将索引存储在变量中并传递它们。

使用奇怪的循环模板模式 (CRTP) 计算多维数组的线性索引

Computing the linear index of a multi-dimensional array when using the curiously recurring template pattern (CRTP)

c++

templates

inheritance

c++20

crtp