C++标准库中的vector是如何实现的？

Question

我一直在大量使用std::vector，最近我问了自己一个问题：" std::vector是如何实现的呢？"

我有两种选择：

1）使用链表，然后让API感觉像是随机访问（例如重载operator[]）。

2）使用new，例如Foo * temp = new Foo [20]：我相信他们做了类似这样的事情，但这又引起了另一个问题。他们是否总是分配一个最大（uint32_t）存储来实现随机访问？（这在内存方面是低效的。）

还是应该注意其他什么事情？

- Arun

---

请查看向量的capacity()方法：http://www.cplusplus.com/reference/stl/vector/capacity/ - Mike DeSimone

Answer 1

通过使用底层数组实现。

无法使用链表来实现std::vector<T>，因为标准保证列表中的元素将在连续的内存中保存。

- JaredPar

---

此外，查找时间很重要。 - Ed S.

连续的内存只是即将到来的C++标准所要求的。但是今天所有可用的实现都会使用数组。这是O(1)访问时间的间接要求。 - Axel Gneiting

根据当前（2003年）的标准：“向量的元素被依次存储在一起”（23.2.4/1）。 - James McNellis

@Axel：不，这已经是C++03所要求的了。虽然C++98没有要求，但它一直被认为是连续的，因此C++03明确规定了它的连续性。 - jalf

好的，看起来我搞混了那个。很抱歉。 - Axel Gneiting

Answer 2

我相信第三种方法是正确的。不能只使用new T[n]，因为它实际上需要构造与分配的对象数量相同的对象，例如

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

如果您的实现只是简单地使用new Foo[10]，那么您只是创建了10个Foo实例。

相反，它使用其分配器来分配和释放原始内存（而不构造对象），并在需要时（例如，当您实际push_back对象时）使用placement new将复制构造的实例放置到其保留中的正确内存位置，并使用显式调用析构函数将它们移除（这是仅与placement new结合使用的情况）。分配器类为此提供以下方法，我假设vector的实现会使用它们。

 void construct(pointer p, const_reference val);

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

  void destroy(pointer p);

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

（“returns”可能应该读作“效果”或类似的词。）

更多关于放置new的内容，请参见此处。

- UncleBens

---

是的，实际上这是唯一一个回答如何实现向量的问题，其他的都在重复连续存储器方面的琐事。 - pfalcon

对象也可以通过'move'构造，如果可能的话，例如push_back(Foo())。它如何跟踪存储的对象并记得调用它们的析构函数？！它们在底层内存中可能不是连续的。 - Mehran

Answer 3

他们使用动态分配的数组，需要根据需要重新增长。必须使用类似于数组的东西，以便元素在内存中是连续的，这是标准保证的。

顺便说一下，重新增长数组的一种常见方法是按需加倍大小。这样，如果您最多插入n个项，则执行的重新增长次数最多为O(log n)，最多浪费O(n)的空间。

您可以在SGI（STL最初构思的地方）自行阅读一个实现。

- jason

Answer 4

没有一种实现方式是固定的。不同的实现可以不同，只要保留语义并满足要求即可。

在任何给定时间，必须有一个基本类型为 T 的数组来满足连续性的要求。但是，如何分配、增长、缩小和释放它取决于实现者。

你可以自己阅读实现代码，它就在头文件中。

我可以告诉你，没有实现使用链表。它们与标准的要求不一致。

- bmargulies

---

我会毫不含糊地声明，没有一种实现是链表。 - jason

所需语义的一部分是O(1)随机访问。链表不是一个选择。 - jamesdlin

-1：标准要求“向量的元素被连续地存储，这意味着如果 v 是一个 vector<T, Allocator>，其中 T 是除 bool 之外的某种类型，则它遵循恒等式 &v[n] == &v[0] + n，对于所有 0<=n<v.size()。”如果有另一种实现方式，则它与数组无法区分。 - Potatoswatter

@bmargulies：在push_back()操作上，需要摊销常数时间的要求，这需要底层数组呈指数增长。唯一的余地就是增长因子是什么。我认为2最常见，但据我所知，1.5被证明是最优的。 - Drew Hall

它由向量的分配器分配和释放，其中默认分配器仅调用operator new()、operator delete()和类的构造函数/析构函数。除了重新调整步骤公式之外，请列举两个实现之间的一个潜在差异。 - Potatoswatter

Answer 5

标准的第23.2.4节第1段要求指针对向量的算术运算与指向数组的指针相同。

向量的元素是连续存储的，这意味着如果v是一个类型为T（除了bool）的向量，则遵守等式&v[n] == &v[0] + n，其中0 <= n < v.size()。

这保证了存储在数组中。当然，如果将数组的大小调整为更大，它可能会在内存中移动。

- Potatoswatter

Answer 6

在精彩的（入门级）书籍《Accelerated C++》的第11章中讨论了一个名为“Vec”的容器的教学（因此简化）版本。他们描述的是std::vector的简化版本，但我认为仍然值得注意以下几点：

1）他们通过数组实现了他们的模板类，

2）他们讨论了push_back，使用了比所需更多的存储空间的技巧，并在用完时再回来获取更多，

3）他们使用allocator <T>进行内存管理。在这种情况下，new运算符不够灵活，因为它既分配又初始化内存。

我再次重申，这并不意味着实际存在的实现就是这么简单。但由于《Accelerated C++》相当普及，有兴趣的人可以在相关章节中找到一种创建、复制、赋值和销毁向量对象的方法。

编辑：另外，我刚刚发现Herb Sutter的博客文章，其中他评论了Andrew Koenig早期的博客文章，关于是否应该担心向量元素在内存中是连续的： 不用惊慌：向量保证是连续的。

- Alexandros Gezerlis

Answer 7

我相信STL使用选项#2（或类似选项），因为std::vector<>保证将元素存储在连续的内存中。

如果你正在寻找一个不需要使用连续内存的内存结构，请查看std::deque。

- oz10

Answer 8

在任何体面的实现中，实际上根本没有数组（如果有的话，你不能在其中使用任何对象而不带默认构造函数），只有被分配的原始内存。它的分配方式通常是每次需要扩展时翻倍。

然后，向量使用就地分配来调用类的构造函数，以便在每个插槽实际使用时将其放置在正确的位置。

当需要扩展时，它会尝试就地重新分配（但这有点愚蠢，通常不起作用，想想Windows 98堆压缩），但通常最终会进行全新的分配并复制过去。

标准STL向量总是在一起的，但并非所有实现都像那样工作（我知道，因为我写过其中一些）。可能没有一个完全是链表，但也不是全部都是。

- Charles Eli Cheese

---

或多或少，但你从哪里开始进行原地重新分配呢？ - UncleBens

Answer 9

根据我在书籍中的阅读以及对于reserve()函数的功能和向量元素必须连续的要求，我认为下面是可能实现vector的一种方式。

向量的元素是连续的，支持O（1）随机访问，并且向量应与C数组兼容。这仅意味着没有链接列表。

当调用reserve()时，它会保留额外的内存。但是reserve()不会调用new T[newSize]来保留更多的内存；如果它这样做，它将为新元素调用默认构造函数。如uncleben所解释的那样，每次调用reserve()时，向量类只是使用其分配器（如果需要）分配更多未初始化的内存，并使用放置new在该内存中复制构造新对象（如果已经分配了更多内存）。

最初向量具有一些默认容量，在构造向量对象时分配未初始化的内存。 push_back()将对象复制构造到第一个可用位置。如果需要分配更多内存，则以类似reserve()的方式进行分配。

- Yogesh Arora