为什么不存在std :: vector :: push_front()？

Question

既然std::vector::push_back()存在,为什么不std::vector::push_front()存在呢？

我知道还有其他存储对象的工作方式几乎相同,并且具有两者push_back()和push_front()函数的实现,但我很好奇为什么std::vector没有.

Answer 1

你不想在矢量上推送push_front.向前面添加元素意味着将向量中的每个元素移回一个元素:O(n)复制.表现糟糕.

Answer 2

有一个重要原因：std::vector<> 是一个连续的单端数组容器。它分配内存并在分配区域的开头开始写入元素。它通常分配比存储所有当前元素所需的更多内存，因此当您调用 push_back() 时，它会在末尾写入新元素并增加其元素计数。它快速高效。

另一方面，Push_front() 需要在所有当前元素之前以某种方式在位置 [0] 处写入新元素 - 但这并非微不足道，因为您的数组位置 [0] 已经被占用。Push_front() 会导致整个数组被重新复制，以便可以修改它的前端。如果没有设计 std::vector<> 类，这将是一种低效的操作。

当然，您仍然可以通过调用

std::vector::insert(begin(), 1, val)

但它会导致整个数组被复制只是为了添加一个元素。