一个二维向量数组在内存中如何对齐?

12

我理解 Set size of vector of vectors at run time 所描述的,可以在运行时声明向量的向量

vector<vector<int> > ref;

然后调整第一级大小:

ref.resize(i);

并在第二层推送元素:

ref[i].push_back(23);

但是,向量的向量在内存中如何对齐?

对于简单的向量,它是一个容器,并连续对齐其元素,就像一个数组;但是,在向量的向量的情况下,我无法看到整个图像。

由于每个内部向量(向量的向量中的向量)的大小可能会发生变化,外部向量的向量(向量的向量中的向量)是否会连续对齐内部向量?外部向量是否为每个内部向量保留内存空间?如果一个向量超出了预先分配的空间会怎样?

3个回答

22
ref 中存储的 vector<int> 结构体大小是恒定的。常见实现将其作为三个指针,或在 32 位架构上约为 12 字节,在最新的 64 位架构上约为 24 字节。
因此,ref 大约管理着连续存储的 ref.capacity() * 12 字节。 ref 中的每个元素/vector<int> 管理其自己的整数,独立于 ref 管理的元素。在下面的艺术渲染中,为了简单起见,ref.size() == ref.capacity()

Pretty picture

所以你的

ref.resize(i);

只影响顶行。您的

ref[i].push_back(23);

仅影响第i列。


常见的实现大约需要12字节,或者在64位架构上需要24字节(这更可能是OP正在尝试的)。 - Matthieu M.

4
vector<vector <int>> m;
  1. 内部向量或行被实现为自由存储器上的独立对象。
  2. 每行中的元素被紧凑地存储,能够通过push_backresizing执行动态分配。
  3. vector< vector<int> >中的每个内部向量都不需要具有相同的大小。因此,内部向量(而不是它们的元素)不是连续存储的。这意味着m[i]的第一个元素不是存储在m[i-1]的最后一个元素直接下一个地址中。

向量的向量(向量中的向量)是否对齐内部向量?

不对齐。请参见点#2。

外部向量是否为每个内部向量保留内存空间?

不保留。请参见点#1。您需要对内部向量进行resizepush_back

向量的向量如何在内存中对齐?

请参见点#3。

vector<T> vec;

消耗这么多内存

sizeof(vector<T>) + (vec.size() ∗ sizeof(T))

在这里,

sizeof(vector<T>) = 12 字节

其中 T 是指一个向量中的向量vector<int>.

因此,对于一个大小为3x4的 vector<vector<int>>,所占用的内存空间为。

 = sizeof(vector<vector<int>>) + (vec.size() * sizeof(vector<int>))
 = 12 + 3 * 12 
 = 48 

如果一个向量超出范围会发生什么?

当大小过大时,vector.resize函数会破坏内存


2

vector<vector<int>> 在内存中可能像这样:

+-+-+-+
|b|e|c|  vector<vector<int>
+-+-+-+ 
 | | |
 | | +-------------------+
 | |                     |
 | +---------------+     |
 |                 |     |
 V                 V     V
+-+-+-+-+-+-+-+-+-+
|b|e|c|b|e|c|b|e|c|  3x vector<int>
+-+-+-+-+-+-+-+-+-+ 
 | | | | | | | | |
 | | | | | | | | +-------------+
 | | | | | | | |               |
 | | | | | | | +-------+       |
 | | | | | | |         |       |
 | | | | | | V         V       V
 | | | | | |+-+-+-+-+-+      
 | | | | | ||i|i|i|i|i|   5x int   
 | | | | | |+-+-+-+-+-+      
 | | | | | |       
 | | | | +-+---+ 
 | | | |       | 
 | | | V       V 
 | | |+-+-+-+-+  
 | | ||i|i|i|i|  4x int
 | | |+-+-+-+-+
 | | |
 | +-+-----------+
 |               |
 V               V
+-+-+-+-+-+-+-+-+
|i|i|i|i|i|i|i|i|  8x int
+-+-+-+-+-+-+-+-+

这里的b表示begin()指针,e表示end()指针,c表示capacity()指针。
你会发现,与矩阵结构所期望的连续内存不同,每一行在内存中都是非连续的。每个向量(包括内部和外部向量)都负责自己的内存分配,而外部向量并不关心它的元素正在做什么。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接