C++ std :: vector是如何实现的？

Question

我一直在使用std::vector很多,最近我问自己这个问题:"如何std::vector实施？"

我有两个选择:

1)链接列表,然后使API感觉像随机访问(即重载operator[]).

2)使用new,例如Foo* temp = new Foo[20]:我相信他们做了这样的事情,但随后又提出了一个问题.他们是否总是分配最大(uint32_t)存储来提供随机访问？(这在内存方面效率很低.)

或者还有其他我应该注意的事情吗？

Answer 1

它是通过使用底层数组实现的.

std::vector<T>使用链表实现a 是不可能的,因为标准保证列表中的元素将保存在连续的内存中.

Answer 2

我相信这是第三种选择.它不能仅仅使用,new T[n]因为它实际上必须构造与分配的对象一样多的对象.例如

std::vector<Foo> v;
v.reserve(10);

如果你的实现只是结束了new Foo[10]那么你就构建了10个Foo实例.

相反,它使用其分配器来分配和释放原始内存(不构造对象),并根据需要(例如,当您实际push_back对象时)使用placement new将复制构造的实例放入其保留的正确内存位置,并使用显式调用将其删除析构函数(你只能将它与放置新元素结合起来).allocator类为我假设vector的实现使用的方法提供了以下方法

 void construct(pointer p, const_reference val);

  Returns:
    new((void *)p) T(val)

  void destroy(pointer p);

  Returns:
    ((T*)p)->~T()

("回报"可能应该是"效果"或类似的.)

更多关于新的安置

Answer 3

它们使用动态分配的数组,根据需要重新生成.有必要使用类似数组的东西,以便元素在内存中是连续的,这是由标准保证的.

顺便提一下,重新生成阵列的一种常见方法是根据需要将大小加倍.这样,如果您n最多插入项目,则仅O(log n)执行再生,并且最多O(n)浪费空间.

您可以在SGI(最初构思STL)中为自己阅读一个实现.