push_back 是如何在 STL 向量中实现的?

2021-12-21 00:00:00 vector c++

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

I was asked this question in an interview.

我回答的点是这样的

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

1) an index pointing to the current position;

2) 必要时调整大小.

2) resize if neccessary.

谁能说得详细点?

推荐答案

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

An STL vector has a size (current number of stored elements) and a capacity (currently allocated storage space).

  • 如果 size <容量，push_back 只是将新元素放在最后，并将size 增加 1.
  • 如果 size == capacity 在 push_back 之前，一个新的更大的数组被分配(两倍的大小是常见的，但这是依赖于实现的afaik)，所有复制当前数据(包括新元素)，并释放旧分配的空间.如果分配失败，这可能会引发异常.
  • If size < capacity, a push_back simply puts the new element at the end and increments the size by 1.
  • If size == capacity before the push_back, a new, larger array is allocated (twice the size is common, but this is implementation-dependent afaik), all of the current data is copied over (including the new element), and the old allocated space is freed. This may throw an exception if the allocation fails.

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

The complexity of the operation is amortized O(1), which means during a push_back that causes a resize, it won't be a constant-time operation (but in general over many operations, it is).

相关文章