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

Question

我知道标准并不要求std::vector分配连续的内存块，但所有实现都遵守这一点。

假设我想创建一个多维静态数组的向量。为简单起见，考虑2个维度和长度为N的向量。也就是说，我希望创建一个由N个元素组成的向量，每个元素都是int [5]类型的。

我能确信所有的N * 5个整数现在都是连续的吗？因此，原则上我只需知道第一个元素的地址就可以访问所有整数吗？这是否取决于实现？

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

- user787267

---

我知道标准并没有强制要求std::vector分配连续的内存块。但是，从C++03开始，它的确如此。参考这里。 - kennytm

@KennyTM：不知道它不在C++98中。谢谢。我猜这仍然是一个实际的要求，为了满足元素访问的操作复杂度规定，对吧？就像std::string一直以来实践中都有连续的元素存储一样，尽管直到C++0x之前并没有明确规定。 - Lightness Races in Orbit

Answer 1

标准确实要求一个 std::vector 的内存是连续的。另一方面，如果你写了这样的代码：

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

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

std::vector<double> v;

并且要计算索引，就像你建议使用float一样。 （如果需要的话，您还可以创建第二个地址为std::vector<float*>的向量。 但是，我通常只是重新计算索引。）

- James Kanze

---

+1，对于一种最初的方法，您可以考虑在C++ FAQ lite中查看此示例。 - David Rodríguez - dribeas

David：好的参考资料。每个喜欢“二维数组”的人都应该阅读它和接下来的条目，直到他们能够在睡梦中重复它为止;-) - FrankH.

Answer 2

正如@Als已经指出的那样，是的，std :: vector（现在）保证连续分配。然而，我不会用指针数组模拟2D矩阵。相反，我建议采用以下两种方法之一。其中更简单的方法是仅使用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的，但我在以前的答案中发布了这种技术的演示。

- Jerry Coffin

Answer 3

向量的元素按照C++标准保证是连续的。
标准引用如下：

来自n2798（C++0x草案）：

23.2.6类模板vector [vector]

1 vector是一种支持随机访问迭代器的序列容器。此外，它支持在末尾进行（摊销）常数时间插入和删除操作；在中间插入和删除需要线性时间。存储管理是自动处理的，但可以提供提示以提高效率。向量的元素是连续存储的，这意味着如果v是一个T类型（而不是bool）的向量，则它遵守所有0 <= n < v.size()的恒等式&v[n] == &v[0] + n。

C++03标准（23.2.4.1）：

向量的元素是连续存储的，这意味着如果v是一个T类型（而不是bool）的向量，则它遵守所有0 <= n < v.size()的恒等式&v[n] == &v[0] + n。

此外，查看此处Herb Sutter对此的看法。

- Alok Save

---

std::vector<bool>万岁:D :D :D - Armen Tsirunyan

但是C++0X还不是官方标准。 - user787267

Answer 4

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

那不是一个二维数组，那是一个指针数组。如果你想要一个真正的二维数组，这就是做法:

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++中使用数组的内容。

- fredoverflow

---

这段代码是C++语言中的一种数据类型，称为“vector of arrays”。其中每个数组包含五个浮点数。 - Lightness Races in Orbit

@Tom：嗯，那看起来很美味！ - fredoverflow

Answer 5

在技术层面，一个向量可能长这样（伪代码）：

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

现在，如果你创建一个 vector<vector<T> >，布局将会是这样的。

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

或者以“内联”形式呈现

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

是的，vector-vector因此使用连续的内存，但并不像您想象的那样。它很可能存储指向外部位置的指针数组（和其他一些变量）。

标准只要求vector的数据是连续的，而不是整个vector。

- Sebastian Mach

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]作为地址传递给需要某种“平面缓冲区”的低级函数。

但正如你所看到的，它会把天真的期望颠倒过来，因为它是myarray[y][x]。

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

编辑：如上所述，这是一个简单的例子。完全没有尝试边界检查。就像“一个数组”一样。

- FrankH.