C ++ std :: vector如何实现？
我一直在使用std::vector ，最近我问自己这个问题：“ std::vector如何实现？
我有两个select：
1）链接列表，然后使API感觉像随机访问（即重载operator[] ）。
2）使用new ，例如Foo* temp = new Foo[20] ：我相信他们做了这样的事情，但是这引发了更多的问题。 他们总是分配一个最大（ uint32_t ）存储来给随机访问？ （这在内存方面效率低下。）
或者还有什么我应该知道的？
它通过使用底层数组来实现。
用链表实现std::vector<T>是不可能的，因为标准保证列表中的元素将被保存在连续的内存中。
我相信这是第三种select。 它不能仅仅使用new T[n]因为它实际上必须构build尽可能多的对象，因为它分配。 例如
std::vector<Foo> v; v.reserve(10);
如果你的实现只是做了new Foo[10]那么你只是构build了10个Foo实例。
相反，它使用其分配器来分配和释放原始内存（不包括构造对象），并根据需要（例如，实际上push_back对象）将复制构造的实例放置到其保留区中的正确内存位置，并使用placement new 调用析构函数 （你只能和新的位置结合使用）。 分配器类为我假设向量的实现使用提供以下方法
void construct(pointer p, const_reference val); Returns: new((void *)p) T(val) void destroy(pointer p); Returns: ((T*)p)->~T()
（“回报”可能应该读作“效果”或类似。）
更多关于安置新的
他们使用dynamic分配的数组，根据需要重新生成。 有必要使用类似于数组的东西，以便元素在标准保证的内存中是连续的。
顺便提一下，重新生成数组的一种常见方式是根据需要将其大小加倍。 这是如此，如果你插入n项最多只有O(log n)再生长，最多O(n)空间被浪费。
您可以在SGI （最初构思STL）时阅读其中的一个实现。
没有一个方法可以实施。 不同的实现可以是不同的，只要保持语义和满足要求即可。
在任何时候，都必须有一个T的原始数组来满足连续性的要求。 但是，如何分配，增长，缩小和释放取决于实现者。
你可以阅读你自己的实现，它就在头文件中。
我可以告诉你没有实现使用链表。 他们不符合标准的要求。
该标准的第23.2.4节¶1要求，对指向vector的指针的算术与指向数组的指针相同。
一个向量的元素是连续存储的，这意味着如果v是一个向量，其中T是除bool之外的某种types，那么对于所有的0 <= n <v，它遵从标识＆v [n] ==＆v [0] + n 。尺寸（）。
这保证了存储在一个数组中。 当然，如果你调整数组的大小，它可能会被移到内存中。
一个称为“Vec”的容器的教学（因此简化）版本在精彩的（介绍性的）“Accelerated C ++”一书的第11章讨论。 他们描述的是std :: vector的精简版本，但我认为还是值得注意的是：
1）他们按照一个数组来实现他们的模板类，
2）他们讨论的push_back分配更多存储的技巧（上面提到的）比需要的更多，当它们用完时回来，
3）他们使用allocator <T >进行内存pipe理。 新操作符在这个上下文中不够灵活，因为它既分配也初始化了内存。
不过，我再说一遍，这并不意味着实际的实现有这么简单。 但是由于“加速C ++”相当普遍，有兴趣的人可以在相关的章节中find一种可以创build，复制，分配和销毁类向量对象的方法。
编辑：在一个相关的笔记，我只是find了以下博客文章由香草萨特在其中他评论在安德鲁柯尼希早些时候的博客文章，关于是否应该担心向量元素在内存中连续： 不是：vector保证是连续的 。
我相信STL使用选项＃2（或类似的东西），因为std :: vector <>保证将元素存储在连续的内存中。
如果您正在寻找不需要使用连续内存的内存结构，请查看std :: deque。
在任何体面的实现中都没有真正的数组（如果存在的话，没有默认的构造函数就不能使用任何对象），而只是分配的原始内存。 它的分配方式通常在每次需要扩展时都会加倍。
一旦每个插槽实际上被实际使用，该vector就会使用适当的位置分配来调用该类的构造函数。
当有扩展它将尝试重新分配到位（但这有点傻，通常不工作，认为Windows 98堆压缩），但通常会最终作出一个全新的分配和复制。
一个标准的stl向量总是在一起，但并不是所有的实现都是这样工作的（我知道，已经写了一些）。 可能没有一个确实是一个链表，但是，无论是。
从我读过的书籍和储备的function以及向量的要素是连续的要求，我认为这可能是实现向量的一种可能的方式。
1）向量的元素是连续的，支持O（1）随机访问，并且向量应该与C数组兼容。 这只是意味着没有链接列表。
2）当你打电话保留时，它保留额外的内存。 但储备确实打电话
new T[newSize]
预留更多的内存。 否则，它会调用默认的构造函数。 正如叔叔所解释的，只要保留被调用，vector类只是在分配器（如果需要的话）中分配更多未初始化的内存，并使用放置new将新对象复制到内存中（如果分配了更多的内存）
3）最初vector有一些默认容量。 当构造vector对象时为其分配未初始化的内存
4）push_back拷贝构造对象到第一个可用位置。 如果需要更多的内存必须以类似的方式分配储备
