为什么矢量的矢量不能保证是连续的？ （或者是吗？）

Question

我知道std::vector元素在内存中保证是连续的。

那么为什么你不能期望一个载体包含其他载体的总集合是连续的？

该向量应该保证其封闭项目的连续内存布局，如果这些附件也是向量，那么我会期望最顶端的向量的全部内容在连续的内存中。

但是在这个问题上似乎存在一些争论，关于这是否属实。一个人可以安全地依靠它吗？一些人似乎go out of their way达到这一点，而我认为这是有保证的。

Answer 1

向量向量中的每个向量都是单独的对象，因此它负责存储。所以，不，这绝不是保证连续的，实际上我不能确定存在于外部矢量中的数据和内部矢量中的数据是否是连续的内存块。

Answer 2

向量是一个包含指向实际数组的指针的对象。

向量向量将是一个对象，其中有一个指向对象数组的指针，每个对象指向堆中其他地方的自己的数组。所以不，他们永远不会像你问的那样连续。

Answer 3

让我们看看矢量的（逻辑的）存储器布局：

[size:4/8 bytes] 
[capacity:4/8 bytes] 
[other datamembers:n bytes] 
*[elements:size*sizeof(element) bytes] << one contiguous memory (pointer to heap) 

随着矢量的矢量它看起来像这样：

[size:4/8 bytes] 
[capacity:4/8 bytes] 
[other datamembers:n bytes] 
* [ 
    [Vector:0] 
     [size:4/8 bytes] 
     [capacity:4/8 bytes] 
     [other datamembers:n bytes] 
     *[elements:size*sizeof(element) bytes] << pointer to contiguous memory for elements 
    [Vector:1] 
     [size:4/8 bytes] 
     [capacity:4/8 bytes] 
     [other datamembers:n bytes] 
     *[elements:size*sizeof(element) bytes] 
    [Vector:2] 
     [size:4/8 bytes] 
     [capacity:4/8 bytes] 
     [other datamembers:n bytes] 
     *[elements:size*sizeof(element) bytes] 
    ... 
    ... 
] << contiguous memory of vectors 

这意味着一个矢量具有的指针，以连续存储器存储矢量，其中的每一个存储它们的元素指向具有存储元素的连续存储器的另一个堆。

但是，如果你设法创建了一个分配器供向量使用，这样它将分配连续的内存块，但如果其中一个嵌套向量被删除，那么仍然会遇到问题，内存是不再连续。更不用说具有嵌套向量具有不同大小的情况。

根据您的使用情况，您可以使用客户连续块存储器分配器作为向量矢量，或者仅使用手动分配和取消分配一个连续存储器块的旧方式。

Answer 4

问题是，矢量模板不包含它处理“嵌入”数据或直接。另一种说法是，vector类将其保存的数据数组包含在其中：vector类包含指向包含元素数组的内存区域的指针。它在结构上等同于：（即，constexpr）

template <typename T> 
struct vector_eq { 
    T *ptr; 
}; 

和不

template <typename T> 
struct vector_neq { 
    T arr[SIZE]; 
}; 

这将需要SIZE到在编译时已知的，被包括在struct arr元件。

我想象塔尔应该可以专门vector<vector<T>>包含一个指向一个单独的内存块，并有其方法返回的内存块的vector<T>共享片特设的情况下，虽然它背后的逻辑很可能是有点毛茸茸的。

Answer 5

简单说就是 - std :: vector保证元素是连续存储的。但是，只包含元素的成员数据，在矢量的情况下，它的大小，容量和类似的东西，再加上指向实际矢量数据的指针。因此，一个向量向量会给你一个连续的向量向量，但是这些向量将在任意的内存地址上动态分配它们的数据。

由于在编译时需要知道对象大小，因此不能让对象具有不同的大小，唯一的方法是使用动态内存分配。如果您有一个固定大小的自定义矢量，它在内部不使用动态内存分配，那么std::vector<customVector>会连续存储customVectors，但您仍将拥有额外的辅助成员，它们将“中断”customVector元素数据的实际连续性。

Answer 6

我认为回答这个（相对于现有描述实现方式）的最正确的正式的方式是基于§23.3.6.1/ 1：

[...]的载体的元素被存储连续的，这意味着如果v是vector<T, Allocator>其中T是某种类型比其他布尔，那么它服从所有0 <= n < v.size()身份

&v[n] == &v[0] + n 

。

注意这谈到了向量的各个元素的&v[i]的地址和所暗示的，特别是该向量的每个元素都有固定大小sizeof(T)（因为这是指针运算是如何工作的）。

这意味着矢量元素在运行时不可能改变大小。如果一个vector<vector<T>>被实现为一个连续的内存块，那么外部向量的成员（它们本身就是向量）将被允许改变大小。

因此，必须有一个额外的间接级别，即各个向量必须包含某种指向存储在不同位置的可变长度数据结构的指针。