std::vector 和多维数组的连续内存

Question

我知道标准不会强制 std::vector 分配连续的内存块，但所有实现仍然遵循这一点。

假设我希望创建一个多维静态数组的向量。为简单起见，考虑 2 维和长度为 N 的向量。也就是说，我希望创建一个具有 N 个元素的向量，例如 int[5]。

我能否确定所有 N*5 整数现在在内存中都是连续的？这样我原则上就可以通过知道第一个元素的地址来访问所有整数？这个实现依赖吗？

作为参考，我目前在连续内存块中创建 2D 数组的方式是首先创建一个长度为 N 的 float* 的（动态）数组，在一个数组中分配所有 N*5 个浮点数，然后将每 5 个元素的地址复制到float* 的第一个数组。

Answer 1

标准确实需要std::vector的内存
连续的。另一方面，如果您编写如下内容：

std::vector<std::vector<double> > v;

全局内存（所有 v[i][j]）将不是连续的。这
创建二维数组的常用方法是使用单个

std::vector<double> v;

数组并计算索引，正如您建议使用 float 所做的那样。
（您还可以使用地址创建第二个 std::vector
如果你想。然而，我总是只是重新计算索引。）

Answer 2

正如 @Als 已经指出的那样，是的，std::vector（现在）保证了连续分配。然而，我不会用指针数组模拟二维矩阵。相反，我建议采用两种方法之一。 （到目前为止）更简单的是仅使用 operator() 进行下标，并进行乘法将 2D 输入转换为向量中的线性地址：

template <class T>
class matrix2D { 
     std::vector<T> data;
     int columns;
public:
     T &operator()(int x, int y) {
         return data[y * columns + x];
     }

     matrix2D(int x, int y) : data(x*y), columns(x) {}
};

如果出于某种原因，您想要使用matrix[a][b]样式寻址，可以使用代理类来处理转换。虽然它是针对 3D 矩阵而不是 2D，但我在 上一个答案。

Answer 3

根据 C++ 标准，Vector 的元素保证是连续的。
标准引用如下：

From n2798 (C++0x 草案):

23.2.6 类模板向量 [向量]

1 向量是支持随机访问迭代器的序列容器。此外，它还支持末尾（摊销）恒定时间插入和擦除操作；中间的插入和擦除需要线性时间。存储管理是自动处理的，但可以给出提示以提高效率。向量的元素是连续存储的，这意味着如果 v 是一个向量，其中 T 是 bool 以外的某种类型，那么对于所有 0 < ，它遵循恒等式 &v[n] == &v[0] + n ;= n < v.size()。

C++03 标准 (23.2.4.1)：

向量的元素是连续存储的，这意味着如果v 是一个向量，其中 T 是 bool 以外的某种类型，那么对于所有 0 <= n < ，它遵循恒等式 &v[n] == &v[0] + n v.size()。

另外，请参阅这里赫伯·萨特对此的看法。

Answer 4

仅供参考，我目前在连续内存块中创建 2D 数组的方式是首先创建一个长度为 N 的 float* 的（动态）数组，在一个数组中分配所有 N*5 个浮点数，然后复制每个浮点数的地址第一个 float* 数组中的第 5 个元素。

这不是一个二维数组，而是一个指针数组。如果您想要一个真正的二维数组，那么它是如何完成的：

float (*p)[5] = new float[N][5];

p [0] [0] = 42;   // access first element
p[N-1][4] = 42;   // access last element

delete[] p;

请注意，只有一个分配。我可以建议您阅读有关在 C++ 中使用数组的更多信息吗？

Answer 5

在底层，向量可能看起来大约类似于（p 代码）：

class vector<T> {
    T      *data;
    size_t  s;
};

现在，如果您创建一个 vector >，将会有这样的布局

vector<vector<T>> --> data {
    vector<T>,
    vector<T>,
    vector<T>
};

或“内联”形式的

vector<vector<T>> --> data {
    {data0, s0},
    {data1, s1},
    {data2, s2}
};

布局是的，向量-向量因此使用连续的内存，但是不，不是你想要的那样。它很可能存储指向外部位置的指针数组（以及一些其他变量）。

该标准只要求向量的数据是连续的，而不是向量作为一个整体。

Answer 6

创建一个简单的类，如您所说的，二维数组，类似于：

template <class T> 2DArray {
private:
    T *m_data;
    int m_stride;
public:
    2DArray(int dimY, int dimX) : m_stride(dimX) : m_data(new[] T[dimX * dimY]) {}
    ~2DArray() { delete[] m_data; }
    T* operator[](int row) { return m_data + m_stride * row; }
}

可以这样使用：

2DArray<int> myArray(30,20);

for (int i = 0; i < 30; i++)
    for (int j = 0; j < 20; j++)
        myArray[i][j] = i + j;

或者甚至传递 &myArray[0][0]< /code> 作为采用某种“平面缓冲区”的低级函数的地址。

但正如您所看到的，它扭转了天真的期望，因为它是 myarray[y][x]。

一般来说，如果您与需要某种经典 C 风格平面数组的代码交互，那么为什么不直接使用它呢？

编辑：如上所述，上面的内容很简单。没有任何边界检查尝试。就像“数组”一样。