STL中vector与queue频繁压入弹出操作的效率对比咨询

绝大多数场景下，你这种无顺序要求的使用场景，选std::vector效率远高于std::queue，核心原因如下：

• 缓存效率优势：std::vector采用连续内存存储，CPU缓存命中率远高于默认基于std::deque实现的std::queue。你批量操作8个元素的场景下，连续内存可以最大化发挥CPU预取机制的作用，内存访问延迟比分块链表结构的deque低一个数量级。
• 弹出操作可优化到O(1)零开销：因为不需要保序，你完全可以不用移动vector前部元素，仅需交换待弹出元素和尾部元素后调用pop_back()即可，示例实现：

// 弹出vector中任意位置元素的无移动实现，这里以弹出首个元素为例
std::swap(vec[0], vec.back());
vec.pop_back();

pop_back()本身是无额外开销的O(1)操作，比queue的pop()操作开销更低。

• 压入操作开销更低：你可以提前调用reserve()方法预估总容量预留空间，std::vector的尾部压入push_back()就完全不会产生扩容拷贝开销，均摊复杂度为O(1)。而std::queue底层的deque每次压入弹出都要维护块指针、跨块访问的额外开销，缓存不命中带来的性能惩罚远高于vector偶尔的扩容开销。

只有当你存储的元素是体积极大的不可拷贝对象，且完全无法预估总容量导致vector频繁全量扩容的极端场景下，才需要考虑使用std::queue，这类场景在实际开发中非常少见。

内容的提问来源于stack exchange，提问作者Joxixi