std :: vector internals

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>文件并开始检查.