c++ - 表示为一维的多维数组(为 n 维模板化)

Question

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

问题

然而，正如所讨论的 in other SO thread regarding arrays，在 C++ 中声明动态分配的多维数组(大小仅在运行时已知)非常棘手.要使用多个方括号(在二维数组的情况下)保留相同的语法，您需要创建一个指针数组，它指向另一组数组(行)。随着维度的增加，它会增加更多(不必要的)间接级别、内存碎片，并且对于较小的数组，指针可能比实际数据占用更多的内存。

解决方案之一是使用一维数组，然后重新计算索引。

示例:

尺寸为 10、3 和 5 的 3D 数组。我想要一个位于位置 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 循环，还有一个用于一维分辨率的数组:

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++ 语言中，有没有办法同时获得灵 active (任意维数)和性能(与专门为某些维数编写的代码相比，零开销)？如果必须有开销，那么硬编码更有意义，比如最多 5 个维度。 在一些现有的库中是否已经实现了动态多维数组？

Answer 1

从存储中分离 View 。

T 的 n 维数组 View 是一个指向 T 的类以及一些获得 n-1 步幅大小的方法。 []返回一个 n-1 维数组 View 。

这种观点有两种不同的风格。第一个存储步幅，第二个存储一个指向连续步幅缓冲区的指针。两者各有优势；当某些或所有尺寸固定时，第一个小心甚至可以优化。但我会做第二个。

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>做链式[]在。这类似于我为 3 个维度编写它的方式。

如果你喜欢 (x,y,z)语法，您唯一的问题是 for 循环，担心编译器没有将其展平，您可以使用包扩展将其强制展平。但首先分析和检查优化的程序集。