用1D数组表示的多维数组（n维度通用模板）

Question

在C++中声明具有静态大小的多维数组非常容易，然后该数组将存储在一个连续的内存块中（行主布局）。

问题

然而，在C++中声明动态分配的多维数组（仅在运行时知道大小）非常棘手，如其他关于数组的SO线程所讨论的那样。为了保留具有多个方括号的相同语法（在2D数组的情况下），您需要创建一个指向另一组数组（行）的指针数组。随着维数的增加，它会增加更多（不必要的）间接级别、内存碎片化，并且对于数组的小尺寸来说，指针可能占用比实际数据更多的内存。

其中一种解决方案是使用1D数组，然后重新计算索引。

例如：

一个大小为10、3和5的三维数组。我想要在位置3、1、4处的元素，而不是写3darray[3][1][4]，我会写3darray[index]，其中index将被计算为3*(y_dym_size*z_dym_size) + 1*(z_dym_size) + 4，当代入后，结果为3*(3*5)+1*(5)+4。

我可以轻松地创建一个封装动态分配数组并以所述方式重新计算索引的类，但这并不实用，因为需要为每个维数编写它。

问题:

我想创建一个模板，它适用于任意数量的维度，并且没有额外开销（这是现代C++的精神——具有可重用的代码/类，其中更多的工作被转移到编译器）。我有以下代码，它适用于n维数组，但没有0开销。它包含for循环，并且还有一个在1D分辨率中使用的数组：

template <class T, size_t DIM>
class arrayND{
    std::array<size_t, DIM> sizes;
    std::array<size_t, DIM-1> access_multiplier;
    vector<T> data;

  public:
    using iterator = typename vector<T>::iterator;
    using const_iterator = typename vector<T>::const_iterator;

    template <typename... Args, typename std::enable_if_t<sizeof...(Args) == DIM, int> = 0>
    arrayND(Args&&... args) {
        std::array<size_t, DIM> temp{args...};
        sizes = temp;
        size_t mult = 1;
        for(int i = DIM-2; i >= 0; --i){
            mult *= sizes[i+1];
            access_multiplier[i] = mult;
        }
        data.resize(mult*temp[0]);
    }

    template <typename... Args, typename std::enable_if_t<sizeof...(Args) == DIM, int> = 0>
    T& get(Args&&... args){
        std::array<size_t, DIM> idx_copy{args...};
        size_t index = idx_copy[DIM-1];
        for(int i = DIM-2; i >= 0; --i){
            index += idx_copy[i]*access_multiplier[i];
        }
        return data[index];
    }

    template <typename... Args, typename std::enable_if_t<sizeof...(Args) == DIM, int> = 0>
    T& operator()(Args&&... args){
        return get(args...);
    }

    void set(const T& elem){
        fill(begin(data), end(data), elem);
    }

    iterator begin(){
        return begin(data);
    }

    iterator end(){
        return end(data);
    }

    const_iterator begin() const{
        return cbegin(data);
    }

    const_iterator end() const{
        return cend(data);
    }
};

我想到的另一种方法是利用可变参数模板，希望在编译器优化后与专门为某些维度编写的代码完全相同：

int getIndex(size_t index){
    return index;
}

template<typename... Args>
int getIndex(size_t index, Args... args){
    return access_multiplier[DIM-sizeof...(Args)-1]*index + getIndex(args...);
}

template <typename... Args, typename std::enable_if_t<sizeof...(Args) == DIM, int> = 0>
T& get(Args&&... args){
    return data[getIndex(args...)];
    /*std::array<size_t, DIM> idx_copy{args...};
    size_t index = idx_copy[DIM-1];
    for(int i = DIM-2; i >= 0; --i){
        index += idx_copy[i]*access_multiplier[i];
    }
    return data[index];*/
}

在当前版本的C++17或C++语言中，是否有一种方法可以同时获得灵活性（任意数量的维度）和性能（与专门为某些维度编写的代码相比零开销比较）？如果必须有开销，则对于最多5个维度，硬编码更有意义。是否已经在某些现有库中实现了动态多维数组？

- Šimon Hrabec

---

静态大小的数组不需要向量，而且有许多方法可以使用[]来实现它们。如果你感到困惑，或者有一些需要你运用技巧的限制条件，那么要解决一个没有明确限制条件的问题就会很困难。 - Yakk - Adam Nevraumont

@Yakk：他想要声明arrayND<3> small(2,2), big(200,200); - 维度数量是类型的一部分，但每个维度的大小都通过构造函数传递。这需要一个向量（或其他动态分配的缓冲区）。 - Martin Bonner supports Monica

感谢Martin提供的示例，就像您写的那样。@yakk我已经更新了问题并明确说明这个问题是关于动态分配数组（我错过了）。 - Šimon Hrabec

Answer 1

将视图从存储中分离。

T的n维数组视图是一个指向T的指针和获取n-1个步幅大小的方法的类。 []返回一个n-1维数组视图。

这种视图有两种不同的风格。第一种存储步幅，第二种存储连续步幅缓冲区的指针。两者都有各自的优点；第一种甚至可以在某些或所有维度固定时进行优化。但我会采用第二种。

template<class T, std::size_t N>
struct slice {
  T* ptr=0;
  std::size_t const* strides=0;
  slice<T,N-1> operator[]( std::size_t i )const{
    return { ptr + i**strides, strides+1 };
  }
};
template<class T>
struct slice<T,1> {
  T* ptr=0;
  std::size_t const* strides=0;
  T& operator[]( std::size_t i )const{
    return *(ptr + i**strides);
  }
};

这个允许每个元素的跨度。

现在你只需要暴露一个stride<T,N>来进行链接[]。 这与我为三个维度编写代码的方式类似。

如果你更喜欢(x,y,z)语法，而你唯一的问题是for循环并且担心编译器没有展开它，你可以使用pack扩展强制展开它。 但是请先进行分析和优化汇编。

- Yakk - Adam Nevraumont