1

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

那么，为什么您不能期望包含其他向量的向量具有连续的总集合呢？

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

但在这个问题上似乎存在一些争论，关于这是否属实。可以安全地依赖它吗？有些人似乎竭尽全力实现这一目标，而我认为这是有保证的。

4

6 回答 6

5

向量向量中的每个向量都是一个单独的对象，因此负责它的存储。所以，不，它决不能保证是连续的，事实上我无法真正看到存储在外部向量和它的内部向量中的数据可能是一个连续的内存块的情况。

于 2013-04-05T00:46:31.087 回答
3

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

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

于 2013-04-05T00:49:28.217 回答
3

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

[...]向量的元素是连续存储的，这意味着如果v是a vector<T, Allocator>，其中T是bool以外的某种类型，则它服从恒等式

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

对于所有人0 <= n < v.size()。

请注意，这讨论&v[i]了向量的各个元素的地址，特别是意味着向量的每个元素都具有恒定的大小sizeof(T)（因为这就是指针算法的工作原理）。

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

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

于 2013-04-05T01:43:33.567 回答
0

让我们看一下vector的（逻辑）内存布局：

[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

这意味着向量有一个指向连续内存存储向量的指针，每个向量都存储指向另一个堆的元素，其中连续内存存储元素。

但是，如果您设法创建一个供向量使用的分配器，以便它分配连续的内存块，您仍然会面临这样的问题，即如果嵌套向量之一被删除，则内存不再是连续的。更不用说嵌套向量具有不同大小的情况了。

根据您的用例，您可以将客户连续块内存分配器用于向量向量，也可以使用手动分配和释放一个连续内存块的旧方法。

于 2013-04-05T00:50:01.837 回答
0

问题是向量模板不包含它处理“内联”或直接处理的数据。换句话说，向量类将它所持有的数据数组装箱：向量类持有一个指向包含元素数组的内存区域的指针。它在结构上等价于：

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

并不是

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

这需要SIZE在编译时知道（即 a constexpr），以便arr将元素包含在结构中。

我想应该可以专门vector<vector<T>>包含指向单个内存块的指针，并让它的方法返回共享该内存块的片的临时实例vector<T>，尽管它背后的逻辑可能有点毛茸茸。

于 2013-04-05T01:04:50.013 回答
0

简单地说 - std::vector 保证元素连续存储。但这仅包括元素的成员数据，在向量的情况下，它将是它的大小、容量和类似的东西，加上指向实际向量数据的指针。

因此，向量向量将为您提供一个连续的向量向量，但这些向量的数据将动态分配在任意内存地址上。

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

于 2013-04-05T01:20:52.833 回答