我已经花了一段时间研究这个问题,但还没有找到答案,而且我知道一种具有各种功能的 40 多年历史的语言可能会做到这一点。
我正在寻找一种只能容纳 500 个整数的数据结构。我需要能够将其中的最大整数与给定的整数进行比较。我还希望该结构删除最早插入的,例如队列。
是否有支持两者的数据结构?除了在其上运行 min()
之外,我不需要随机访问。
有优先级队列,支持 max
但它们不自动处理大小。我可以编写自己的函数来执行此操作,但我想我还是会问/
最佳答案
要仅容纳 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 个整数的最小值/最大值应该非常快。但是如果你反对线性扫描的算法复杂性,你可以试试这个:
- 将元素存储在
set<int>
中这给了你*begin()
和*rbegin()
获取最小值和最大值。 - 将迭代器存储到集合中的单独循环缓冲区中。集合迭代器不会因其他迭代器的插入和删除而失效,因此这是安全的。当循环缓冲区已满时,从集合中删除最旧的迭代器,然后将其从循环缓冲区中删除。
关于支持pop oldest inserted和max的C++数据结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36929772/