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

Question

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

- Alessandro Jacopson

Answer 1

因为与其他一些容器不同，std::vector在插入元素方面没有特别的功能。每个容器提供的功能对于该容器都是有意义的。

你可能应该使用一个 std::deque，它明确地擅长在前端和后端插入元素。

请查看此图表。

- Lightness Races in Orbit

---

图表很好，但全是黑色的，难以理解。 - AnotherDeveloper

这并没有真正解释为什么没有pop_front()方法，它只谈到了插入。插入元素与弹出元素有什么关系？ - Rasmus Dall

希望能有一种方法来修复这个图表。 - cpchung

请注意，您说的是“插入”，而OP询问的是“pop_front()”，如果我没记错的话，这是删除/移除（擦除）。不是插入。 - Alexis Wilke

Answer 2

虽然对于大向量效率较低，但以下内容等同于std::vector的pop_front()

vec.erase(vec.begin());

正如其他答案所述，std::vector并不适合删除第一个元素，并且需要移动/复制所有剩余的元素。根据具体的使用情况，考虑使用其他容器可能更为方便。

- SEGStriker

---

这个方法可以使用，但在大向量上效率不高。 - Alexis Wilke

这个东西的时间复杂度会是多少？ - Swastik Singh

@SwastikSingh O(n) - OwnageIsMagic

Answer 3

vector通常被实现为以下样式：

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
};

"begin"在向量中既充当“指向第一个T的指针”，又充当“指向我们分配的所有内存的指针”。因此，仅通过递增“begin”就无法从向量前端“弹出”元素 - 这样做会使您不再拥有需要释放的内存的指针。这将导致内存泄漏。因此，“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
};

通过这种方式，您可以通过将“begin”向前和向后移动来执行“pop_front”，而不必担心稍后需要释放哪个内存。为什么std::vector不能以这种方式工作呢？我想这是标准撰写人员口味的问题。他们的目标可能是提供尽可能简单的“动态可调整大小的数组”，我认为他们成功了。

- user223264

---

不只是“品味”。想象一下所有的任意决定：向前推会耗尽头部的自由空间。重新分配或仅移动项目，直到末尾有空闲空间，如果有的话？同样地，向末尾推，我们是向前移动还是重新分配？仅仅移动似乎很浪费，但重新分配的成本很高。让它变成循环并进入索引计算地狱？然后是容量。Reserve（100），我们把第一个元素放在哪里？前面？中心？为什么？让我们弹出一些项目，现在它是空的，开始遇到了结束，我们调整它们向前，中心，结束还是什么都不做？通过类型特征/等等进行配置太多了。 - quetzalcoatl

Answer 4

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

这不是一个“bug”或一个“怪癖”，这只是向量容器的一种属性。如果你需要快速的pop_front，请考虑切换到另一个容器。

- orlp

---

如果你需要快速执行pop_front()操作，可以考虑改用std::deque<>。 - ildjarn

自然地，它必须进行重新分配，但为什么与“push_back”的重新分配相比，它会是O(n)呢？ - deceleratedcaviar

@Daniel：因为push_back并不总是需要重新分配空间。 - Lightness Races in Orbit

为什么 pop_front 不能是 O(1)？你只需要将指针向前移动一个元素到数组的开头即可。 - Jonathan.

@Jonathan。你可以这样做，但不能使用普通向量的相同实现方式，需要有更多的逻辑。请参见https://github.com/orlp/devector（实现尚未完成，但概念已经在那里）。 - orlp

Answer 5

然而，如果你需要进行pop_front操作并且不关心向量中元素的索引，你可以使用类似以下方法进行类似于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

- marchelbling

---

如果你真的不在意元素的顺序，那么这将是一个奇怪的情况，因为你既关心又不关心元素的顺序。因为如果你真的不在意，那么这会更容易：模板<typename T> void pop_front(std::vector<T>& v) { v.pop_back(); }。 - MSalters

你的评论对我来说似乎是错误的。通过执行 template<typename T> void pop_front(std::vector<T>& v) { v.pop_back(); }，你将无法删除预期的 front 元素。我的建议是“交换” front 和 back 元素并删除最后一个元素。 - marchelbling

此外，如果您想操作连续的内存缓冲区，则可能会在不深入关注元素顺序时使用向量。我并不争论这是否是一个好主意，但在这种非常特定（并且已指定）的情况下，这是以O(1)的时间复杂度执行pop_front的有效方法。 - marchelbling

相当聪明，但大多数情况下没什么用 :) 我给你点赞。 - Super-intelligent Shade

@marchelbling 我认为这是一个O(2)，因为你有一个复制和一个删除。如果你只是使用一个向量来保存N个项目而不是按特定顺序保存N个项目，那么我认为这是一种聪明的方法。 - Alexis Wilke

Answer 6

#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);

- Shubham Kumar Gupta

---

问题不是“我该怎么做？”而是“为什么没有这样的函数？”... - Alexis Wilke

C语言打来电话，要求把它的宏定义还回去...这些宏定义存在所有通常问题，并且快乐地忽略了具有模拟操作优化版本的容器。请编写一个模板。 - Max Truxa

Answer 7

可能是因为对于大向量来说，这将会非常缓慢。

在包含1000个对象的向量上执行pop_front()需要999次operator=()调用。

- Roddy

---

不比 erase(v.begin()) 慢。这是因为向量在开头插入没有特殊属性，与在末尾插入（或弹出）相反。 - orlp

@nightcracker - 确实，erase() 也同样糟糕。我同意想要在向量上使用 pop_front() 是一种好的“迹象”，表明您正在使用错误类型的容器！ - Roddy

Answer 8

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

- Ezra Lin