支持pop oldest inserted和max的C++数据结构

Question

我已经花了一段时间研究这个问题，但还没有找到答案，而且我知道一种具有各种功能的 40 多年历史的语言可能会做到这一点。

我正在寻找一种只能容纳 500 个整数的数据结构。我需要能够将其中的最大整数与给定的整数进行比较。我还希望该结构删除最早插入的，例如队列。

是否有支持两者的数据结构？除了在其上运行 min() 之外，我不需要随机访问。

有优先级队列，支持 max 但它们不自动处理大小。我可以编写自己的函数来执行此操作，但我想我还是会问/

Answer 1

要仅容纳 500 个整数，您需要一个循环缓冲区。在 Boost 中:

http://www.boost.org/doc/libs/release/doc/html/circular_buffer.html

但这不会帮助您找到容器中的最小值或最大值。为此，您需要这些:

http://en.cppreference.com/w/cpp/algorithm/min_element http://en.cppreference.com/w/cpp/algorithm/max_element http://en.cppreference.com/w/cpp/algorithm/minmax_element

您不能完全同时执行这两项操作，因为首先删除最旧元素的要求需要按插入顺序排序，而查找最小或最大元素的要求需要以某种方式按值顺序排序(线性或线性)像 priority_queue 这样的堆)。

在现代机器上查找 500 个整数的最小值/最大值应该非常快。但是如果你反对线性扫描的算法复杂性，你可以试试这个:

1. 将元素存储在 set<int> 中这给了你 *begin()和 *rbegin()获取最小值和最大值。
2. 将迭代器存储到集合中的单独循环缓冲区中。集合迭代器不会因其他迭代器的插入和删除而失效，因此这是安全的。当循环缓冲区已满时，从集合中删除最旧的迭代器，然后将其从循环缓冲区中删除。