为什么 C + + std: : Vector 中没有 pop_front 方法？

为什么在 C + + std::vector中没有 pop_front方法？

136270 次浏览
小开

因为 push_back和 pop_back是向量的特殊操作，只需要 O(1)计算。任何其他推或弹需要 O(n)。

这不是一个“ bug”或“ quilk”，这只是向量容器的一个属性。如果需要快速 pop _ front，可以考虑更改为其他容器。

小开

可能是因为对于大型矢量来说，它会非常慢。

对于一个包含1000个对象的向量，pop_front()需要999次 operator=()调用。

小开
最佳答案

因为与其他容器不同，std::vector在前端插入元素方面没有特殊的功能。每个容器 对那个集装箱来说很合理提供的功能。

您可能应该使用 std::deque，这是显式的 很好在前面插入 还有回来。

看看 这张图。

小开

但是，如果需要在矢量中使用 pop _ front 和 不关心元素的索引，那么可以使用类似

template<typename T>
void pop_front(std::vector<T>& vec)
{
vec.front() = vec.back();
vec.pop_back();
}

Dan Higgins 也谈到了这一点: https://youtu.be/oBbGC-sUYVA?t=2m52s

小开

向量通常是这样实现的:

struct
{
T* begin; // points to the first T in the vector
T* end; // points just after the last T in the vector
int capacity; // how many Ts of memory were allocated
};

“ start”具有“指向向量中第一个 T 的指针”和“指向我们分配的所有内存的指针”的双重作用因此，不可能通过简单地递增“ start”来“弹出”向量前面的元素——这样做，你就不再有一个指向需要释放的内存的指针。会泄露内存。所以“ pop _ front”需要将所有 T 从向量的后面复制到向量的前面，这相对来说比较慢。所以他们决定把它排除在标准之外。

你想要的是这样的东西:

struct
{
T* allocated; // points to all the memory we allocated
T* begin; // points to the first T in the vector
T* end; // points just after the last T in the vector
int capacity; // how many Ts of memory were allocated
};

通过这种方法，您可以通过向前和向后移动“ start”来“ pop _ front”，而不会忘记以后要释放哪些内存。为什么 std: : Vector 不这样工作？我想这是写标准的人的品味问题。他们的目标可能是提供最简单的“动态可调整数组”，我认为他们成功了。

小开

虽然在大型向量上效率不高，但下面的代码相当于 std::vector的 pop_front()

vec.erase(vec.begin());

如其他答案所述，std::vector的设计不是为了删除第一个元素，而是需要移动/复制所有剩余的元素。根据特定的用例，考虑其他容器可能会很方便。

小开

向量看起来像一个堆栈容器，我们有一个堆栈来存储数据。 所以我们只是 pop_back不是 pop_front。 如果你想要 pop_front，std::list可能是一个更好的选择。因为它是一个双向的队列结构。

小开 
#define push_front(v,val) v.insert(v.begin(), 1, val);
#define pop_front(v)  if(!v.empty())v.erase(v.begin());

您可以直接编写这个并使用它

push_front(vec,val);
pop_front(vec);

提交答案