c++ - std::vector 内部结构

Question

是如何std::vector实现的，使用什么数据结构？当我写

void f(int n) {
  std::vector<int> v(n);
  ...
}

向量是否v在堆栈上分配？

Answer 1

该vector对象将在堆栈​​上分配，并在内部包含指向堆上元素开头的指针。

堆上的元素使vector类能够按需增长和缩小。

虽然将vector放在堆栈上会给对象带来超出范围时被破坏的好处。

关于您的[]问题，vector该类重载了[]运算符。我会在内部说，当你这样做时，它基本上是在做这样的事情array[1]：

return *(_Myfirst+ (n * elementSize))

在哪里vector跟踪它的内部堆的开始_Myfirst。

当你vector开始填满时，它会为你分配更多的内存。一种常见的做法是每次将所需的内存量加倍。

请注意，vector继承自_Vector_val，其中包含以下成员：

pointer _Myfirst;   // pointer to beginning of array
pointer _Mylast;    // pointer to current end of sequence
pointer _Myend; // pointer to end of array
_Alty _Alval;   // allocator object for values

Answer 2

你v被分配在自动内存中。（俗称栈，是的）

没有指定实现细节，但最常见的是使用动态数组来实现，如果您尝试添加比先前分配更多的元素，该数组会调整大小。

该标准仅指定接口（它应该具有哪些方法）和执行时间边界。

由于vector是模板，因此实现是可见的，因此找到您的<vector>文件并开始检查。

Answer 3

void f(int n) {
  std::vector<int> v(n);
  ...
}

上面的向量具有自动存储持续时间，并在堆栈上分配。但是，向量管理的数据数组是在堆上分配的。

向量的内部结构是特定于实现的，但典型的实现将包含 3 个指针；一个来跟踪数组的开始，向量的大小和向量的容量。