STL容器如何跟踪容器当前的大小？

Question

给定的

vector<int> a;

如果完成了a.push_back()，vector如何知道是通过重新分配内存来增加大小，还是有可用的空间(因为当大小满时，vector会分配一些额外的空间以减少开销)。

P.S.同样的技术适用于其他类型的容器，如stack、queue等。

我认为它与C.中的"struct“相同。

Answer 1

方法capacity()返回可以存储在向量中而无需重新分配的项数。

方法size()返回当前存储在向量中的项数。

在插入另一项之前，如果size() == capacity()需要提供更多的容量，这是合理的。这将涉及重新分配，以提供更多的能力。

同样的技术也适用于其他类型的容器，如堆栈、队列等。

堆栈和队列构建在其他std容器之上。这些底层容器(通常是矢量或deque)采用了类似的技术。

我认为它的作用与C中的"struct“相同。

不是的。

Answer 2

通常，向量(以及C#中的列表)将分配一个内存块。当您向其添加元素时，它将标记越来越多的内存被消耗。然后，当块已满时，它将分配一个新的较大块，将内容复制到新的较大块中，并删除旧块。再次，新的更大的块有更多的自由空间，然后，再一次，它可以填补。其思想是，向量总是有一个连续的空间，所以它可以用于考虑数组的应用程序中。因为它有连续的空间，所以访问单个元素的机器指令非常简单，因此随机访问非常快。C#中的List具有类似的语义。与实现相关的事情很大程度上取决于新的更大的块有多大。有时他们会把这个比例提高一个百分点。有时它们只是两倍的大小。