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

Question

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

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

vector v是否分配在栈上？

Answer 1

vector 对象将在堆栈 上分配，并将在内部包含指向堆上元素的开始 的指针.

堆 上的元素赋予vector 类按需增长和收缩的能力。

stack 上的 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