我使用的是 STL 双端队列结构,在我的算法的每次迭代中,我从前面删除 n
元素并在末尾添加 n
元素。所以,基本上,我的双端队列大小永远不会改变,而且我正在进行数百万次迭代。
有没有办法确保内存大小在其生命周期内不会改变(或至少不会下降)?也许由于双端队列的底层实现,这可能是不可避免的,但我想确定一下。
最佳答案
不,您不能总是期望这种行为。这些是特定于实现的细节。我认为标准中没有任何规范强制执行此行为。
但是,还有另一种解决方案。您可以在 boost 中使用循环缓冲区。 (文档:https://www.boost.org/doc/libs/1_67_0/doc/html/circular_buffer.html) 它为您需要的确切功能提供了最优化的实现之一。 它将在构造时分配给定大小的内存(因为它如您所提到的常量)。在调用和 pop_{front/back} 时,它不会释放内存,也不会在 push_{front/back} 上分配内存。它只是移动开始和结束迭代器以指向适当的成员。
因此,您需要的所有操作都是 O(1)。它还提供空间局部性,从而使遍历速度非常快。
关于c++ - STL 双端队列 : keep minimum size,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33634333/