push_back是如何在STL vector中实现的？

Question

我在一次面试中被问到了这个问题。

我回答的要点是这样的

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

2)必要时调整大小。

有没有人能更详细地解释一下？

Answer 1

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

• 如果为size < capacity，则push_back仅将新元素放在末尾，并将size递增1。
• 如果在push_back之前为
• ，则分配一个更大的新数组(大小是普通数组的两倍，但这取决于afaik的实现)，复制所有当前数据(包括新元素)，并释放旧的分配空间。如果分配失败，可能会抛出异常。

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

Answer 2

template< typename T >
void std::vector<T>::push_back(const T& obj)
{
    this->insert(this->end(),obj);
}

Answer 3

当然，这是内在的实现定义。假设这是一个关于某人如何实现动态数组的问题，通常是这样的：

1. push_back检查capacity()并确保它至少比size().
2. If大1如果没有新元素的容量，向量重新分配它的整个底层存储，将旧存储的内容复制到新存储。旧的存储是deallocated.
3. The新元素被复制到动态数组的末尾。

一些STL实现将通过使用交换(即容器的容器)省略一些副本，但在大多数情况下，这正是它的工作方式。