快速元素访问用于连续数组的多维表示

Question

我有一个在内存中连续表示的多维数组.我希望隐藏这种表示,让用户访问数组元素就好像它是多维的:例如my_array[0][3][5]或my_array(0,3,5)类似的东西.直到运行时才确定对象的尺寸,但是使用指定它具有多少维度的类型创建对象.这个元素查找需要被调用数十亿次,因此希望每次调用都需要最小的开销.

我看过类似的问题,但没有真正找到一个好的解决方案.使用[]运算符需要创建N-1维对象,这对于像向量矢量这样的多维结构很好,因为对象已经存在,但是对于连续的数组,它看起来很快就会卷曲并需要某种切片通过原始数组.

我还研究了重载(),这似乎更有希望,但需要指定参数的数量,这将根据数组的维数而变化.我曾考虑使用列表初始化或向量,但希望避免实例化对象.

我对模板和图形只有一点了解,应该有一些方法可以使用C++的宏伟模板功能来()为不同类型(例如不同数量的维度)的数组指定唯一的重载.但我只在真正基本的通用情况下使用模板,比如使用函数float和两者double.

我想象的是这样的:

template<typename TDim>
class MultiArray {
public:
  MultiArray() {} //build some things
  ~MultiArray() {} //destroy some things

  // The number of arguments would be == to TDim for the instantiated class
  float& operator() (int dim1, int dim2, ...) {
    //convert to contiguous index and return ref to element
    // I believe the conversion equation is something like:
    // dim1 + Maxdim1 * ( dim2 + MaxDim2 * ( dim3 + MaxDim3 * (...)))
  }

private:
  vector<float> internal_array;
  vector<int> MaxDimX; // Each element says how large each corresponding dim is.
};

因此,如果我初始化此类并尝试访问元素,它将看起来像这样:

my_array = MultiArray<4>();
element = my_array(2,5,4,1);

我如何使用模板进行此操作？这甚至可能吗？

Answer 1

template<class T>
struct slice {
    T* data = 0;
    std::size_t const* stride = 0;
    slice operator[](std::size_t I)const {
        return{ data + I* *stride, stride + 1 };
    }
    operator T&()const {
      return *data;
    }
    T& operator=(typename std::remove_const<T>::type in)const {
      *data = std::move(in); return *data;
    }
};

存储vector<T>的数据,和一个std::vector<std::size_t> stride进步的,其中stride[0]是在元件的步幅,所述第一索引就是了.

template<class T>
struct buffer {
  std::vector<T> data;
  std::vector<std::size_t> strides;

  buffer( std::vector<std::size_t> sizes, std::vector<T> d ):
    data(std::move(d)),
    strides(sizes)
  {
    std::size_t scale = 1;
    for (std::size_t i = 0; i<sizes.size(); ++i){
      auto next = scale*strides[sizes.size()-1-i];
      strides[sizes.size()-1-i] = scale;
      scale=next;
    }
  }
  slice<T> get(){ return {data.data(), strides.data()}; }
  slice<T const> get()const{ return {data.data(), strides.data()}; }
};

c ++ 14. 实例.

如果你使用的不够[]s,它指的是所讨论的子阵列的第一个元素.如果你使用太多,那就是UB.它在尺寸和尺寸方面都进行零尺寸检查.

两者都可以添加,但会降低性能.

维度的数量是动态的.您可以分为buffer两种类型,一种拥有缓冲区,另一种提供它的尺寸视图.