c++ - push_back 如何在 STL vector 中实现？

Question

我在一次采访中被问到这个问题。

我回答的点是这样的

1) 指向当前位置的索引；

2) 必要时调整大小。

谁能详细说明一下？

Answer 1

STL vector有一个 size (当前存储元素的数量)和 capacity (当前分配的存储空间)。

• 如果size < capacity , 一个 push_back简单地将新元素放在末尾并递增 size 1.
• 如果size == capacity在 push_back 之前，分配了一个新的更大的数组(两倍大小是常见的，但这是依赖于实现的 afaik)，所有当前数据都被复制(包括新元素)，并释放旧分配的空间。如果分配失败，这可能会引发异常。

操作的复杂性是摊销 O(1)，这意味着在 push_back 期间导致调整大小，它不会是一个恒定时间操作(但通常在许多操作中，它是)。