C++ 怎么样？ std::vector 实施了吗？
我经常使用 std::vector，最近我问自己这个问题：“std::vector 是如何实现的？”
我有两种选择：
1) 链接列表，然后使 API 感觉像随机访问（即重载 operator[]）。
2）使用new，例如Foo* temp = new Foo[20]：我相信他们做了类似的事情，但它又提出了一个问题。他们是否总是分配最大（uint32_t）存储来提供随机访问？ （这在记忆方面效率很低。）
或者还有什么我应该注意的吗？
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（9）
它是通过使用底层数组来实现的。
不可能实现
std::vector< /a> 使用链表，因为标准保证列表中的元素将保存在连续的内存中。It's implemented by using an underlying array.
It's not possible to implement a
std::vector<T>with a linked list because the standard guarantees the elements in the list will be held in contiguous memory.我相信这是第三种选择。它不能只使用 new T[n] ，因为那样它实际上必须构造与分配的对象一样多的对象。例如，
如果您的实现只是简单地执行
new Foo[10]那么您就构造了 10 个 Foo 实例。相反，它使用其分配器来分配和释放原始内存（无需构造对象），并根据需要（例如，当您实际
push_back对象时）将复制构造的实例放置到其保留中的正确内存位置中placement new 并通过显式调用析构函数删除它们（您只能与placement new 结合使用）。分配器类提供了以下方法，我认为向量的实现使用这些方法（“返回”可能应该读为“效果”或类似的。）
有关 新展示位置
I believe it is the third option. It can't just use
new T[n]because then it would actually have to construct as many objects as it allocates. E.gIf your implementation simply ended up doing
new Foo[10]then you'd just have constructed 10 instances of Foo.Instead it uses its allocator to allocate and deallocate raw memory (without constructing objects), and as needed (for example, when you actually
push_backobjects) places copy-constructed instances into correct memory locations in its reserve using placement new and removes them with explicit calls to the destructor (something you'd only do in combination with placement new). The allocator class provides following methods for that which I presume vector's implementations use(The "returns" probably should read "effect" or similar.)
More about placement new
它们使用根据需要重新增长的动态分配的数组。有必要使用类似数组的东西，以便元素在内存中是连续的，这是标准所保证的。
顺便说一句，重新增长数组的一种常见方法是根据需要将大小加倍。这样，如果您插入
n个项目，最多只会执行O(log n)次重新增长，并且最多O(n)空间被浪费了。您可以在 SGI（STL 最初构想的地方）上亲自阅读一个实现。
They use a dynamically allocated array that is regrown as needed. It is necessary to use something like an array so that the elements are contiguous in memory which is guaranteed by the standard.
Incidentally, one common way of regrowing an array is to double the size as needed. This is so that if you are inserting
nitems at most onlyO(log n)regrowths are performed and at mostO(n)space is wasted.You can read one implementation for yourself at SGI (where STL was originally conceived).
没有一种方法可以实现它。不同的实现可以不同，只要保留语义并满足要求即可。
在任何给定时间，都必须有一个 T 的原始数组来满足连续性的要求。然而，如何分配、增长、收缩和释放它取决于实现者。
您可以自己阅读实现，它就在头文件中。
我可以告诉您没有实现使用链表。它们不符合标准的要求。
There is no one way it is implemented. Different implementations can be different, so long as the preserve the semantics and satisfy the requirements.
At any given time, there has to be a primitive array of T to satisfy the requirements of contiguity. However, how it is allocated, grown, shrunk, and freed is up to the implementor.
You can read the implementation for yourself, it's right there in the header file.
I can tell you that no implementations use linked lists. They aren't consistent with the requirements of the standard.
标准第 23.2.4 节第 1 节要求对向量中的指针进行的算术运算与对数组中的指针进行的算术运算相同。
这保证了存储在数组中。当然，如果您将数组调整得更大，它可能会移动到内存中。
Section 23.2.4, ¶1 of the standard requires that arithmetic on pointers into a vector work the same as with pointers into an array.
This guarantees that the storage is in an array. Of course, if you resize the array to be bigger, it might get moved in memory.
精彩（介绍性）书籍“Accelerated C++”的第 11 章讨论了名为“Vec”的容器的教学（因此简化）版本。他们描述的是 std::vector 的精简版本，但我认为仍然值得注意的是：
1）他们用数组实现了模板类，
2）他们根据技巧讨论了 Push_back（提到过）上面）分配比需要更多的存储空间，并在用完时返回更多存储空间，
3）他们使用分配器>用于内存管理。 new 运算符在这种情况下不够灵活，因为它既分配又初始化内存。
不过，我再说一遍，这并不意味着实际的实现就这么简单。但由于“加速 C++”相当普遍，感兴趣的人可以在相关章节中找到一种创建、复制、分配和销毁类向量对象的方法。
编辑：在相关说明中，我刚刚找到了 Herb Sutter 的以下博客文章，其中他对 Andrew Koenig 之前的一篇博客文章进行了评论，讨论是否应该担心向量元素在内存中是连续的：
不要畏缩：向量保证是连续的。
A pedagogic (and thus simplified) version of a container called "Vec" is discussed in Chapter 11 of the wonderful (introductory) book "Accelerated C++". What they describe is a stripped-down version of std::vector, but I think it is still worth noting that:
1) they implement their template class in terms of an array,
2) they discuss push_back in terms of the trick (mentioned above) of allocating more storage than is needed, and coming back for more when they run out, and
3) they use allocator
<T> for memory management. The new operator is not flexible enough in this context, since it both allocates and initializes memory.I repeat, though, that this doesn't mean that actual implementations out there are this simple. But since "Accelerated C++" is quite widespread, those interested can find in the relevant chapter one way vector-like objects can be created, copied, assigned, and destroyed.
EDIT: On a related note, I just found the following blog post by Herb Sutter in which he comments on an earlier blog post by Andrew Koenig, regarding whether or not one should be worried about vector elements being contiguous in memory:
Cringe not: Vectors are guaranteed to be contiguous.
我相信 STL 使用选项#2（或类似的选项），因为 std::vector<>保证将元素存储在连续的内存中。
如果您正在寻找不需要使用连续内存的内存结构，请查看 std::deque。
I believe the STL uses option #2 (or something similar) because a std::vector<> is guaranteed to store the elements in contiguous memory.
If you're looking for a memory structure that doesn't need to use contiguous memory, look at std::deque.
在任何像样的实现中根本没有实际的数组（如果有的话，如果没有默认构造函数，则不能使用其中的任何对象），而只是分配的原始内存。它的分配方式通常是每次需要扩展它时都会加倍。
然后，一旦每个槽实际使用，向量就会使用就地分配在适当的位置调用类的构造函数。
当有扩展时，它会尝试就地重新分配（但这有点愚蠢，通常不起作用，想想 Windows 98 堆压缩），但通常最终会进行全新的分配并复制。
标准的 stl 向量总是在一起，但并非所有实现都像这样工作（我知道，已经编写了其中一些）。不过，也可能没有一个是严格意义上的链表。
There's no actual array at all in any decent implementation (if there is, you can't use any object in it without a default constructor), but just raw memory that gets allocated. It gets allocated in a manner that's usually along the lines of doubling every time you need to expand it.
The vector then uses in place allocation to call the constructors of the class in the proper location once each slot actually gets used actually used.
When there is expansion it will try to reallocate in place (but this is a bit silly and doesn't normally work, think windows 98 heap compaction) but usually will end up making a whole new allocation and copying over.
A standard stl vector is always all together, but not all implementations work like that (I know, having written some of them). Probably none are exactly a linked list, though, either.
根据我在书中读到的内容，以及从
reserve()的功能以及向量元素连续的要求，我认为这可能是实现vector< 的可能方法/代码>。向量的元素是连续的，支持 O(1) 随机访问，并且向量应与 C 数组兼容。这仅仅意味着没有链接列表。
当您调用
reserve()时，它会保留额外的内存。但是reserve()不会调用new T[newSize]来保留更多内存；如果是这样，它将为新元素调用默认构造函数。正如 Uncleben 所解释的，每当调用 Reserve() 时，向量类都会使用其分配器（如果需要）分配更多未初始化的内存，并使用以下方法将新对象复制构造到该内存中：放置新（如果已分配更多内存）。最初向量有一些默认容量，在构造向量对象时为其分配未初始化的内存。
push_back()copy 将对象构造到第一个可用位置。如果需要，必须分配更多内存，其方式与reserve()类似。From what I have read in books, and from the functionality of
reserve()and the requirement that elements of vectors be contiguous, this is what I think could be a possible way to implementvector.Elements of vectors be contiguous, supporting O(1) random access and vectors should be compatible with C arrays. This just implies there are no linked lists.
When you call
reserve()it reserves additional memory. Butreserve()does not callnew T[newSize]to reserve more memory; if it did, it would call default constructors for the new elements. Asunclebenexplained, wheneverreserve()is called, the vector class just allocates more uninitialized memory using its allocator (if required) and copy-constructs new objects into that memory using placementnew(if more memory has been allocated).Initially vector has some default capacity, for which uninitialized memory is allocated when the vector object is constructed.
push_back()copy constructs the object into the first available location. If required more memory has to be allocated, in similar manner asreserve().