如何在STL向量中实现push_back？

Question

我在接受采访时被问到这个问题.

我回答的观点是这样的

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

2)必要时调整大小.

任何人都可以详细说明吗？

Answer 1

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

• 如果size < capacity,push_back只需将新元素放在最后并按size1 递增.
• 如果size == capacity在之前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

感谢一些评论，我正在彻底修改一个非常不正确的原始答案。

根据STL规范，你的答案是正确的。该向量被实现为动态调整大小的数组：

向量容器被实现为动态数组；就像常规数组一样，向量容器将其元素存储在连续的存储位置中，这意味着不仅可以使用迭代器，还可以使用指向元素的常规指针的偏移量来访问其元素。

但与常规数组不同的是，向量中的存储是自动处理的，允许根据需要扩展和收缩。