c++ - STL 双端队列 : keep minimum size

Question

我使用的是 STL 双端队列结构，在我的算法的每次迭代中，我从前面删除 n 元素并在末尾添加 n 元素。所以，基本上，我的双端队列大小永远不会改变，而且我正在进行数百万次迭代。

有没有办法确保内存大小在其生命周期内不会改变(或至少不会下降)？也许由于双端队列的底层实现，这可能是不可避免的，但我想确定一下。

Answer 1

不，您不能总是期望这种行为。这些是特定于实现的细节。我认为标准中没有任何规范强制执行此行为。

但是，还有另一种解决方案。您可以在 boost 中使用循环缓冲区。 (文档:https://www.boost.org/doc/libs/1_67_0/doc/html/circular_buffer.html)它为您需要的确切功能提供了最优化的实现之一。它将在构造时分配给定大小的内存(因为它如您所提到的常量)。在调用和 pop_{front/back} 时，它不会释放内存，也不会在 push_{front/back} 上分配内存。它只是移动开始和结束迭代器以指向适当的成员。

因此，您需要的所有操作都是 O(1)。它还提供空间局部性，从而使遍历速度非常快。