C++数据结构，按值保持排序并使用FIFO操作

Question

我正在寻找一种数据结构，它可以快速地进行排序插入，并且基于先进先出（FIFO）的操作方式。

我试图创建一个固定大小的数据结构，用于保存一系列数值。在每次迭代的新步骤中，我希望能够有效地找到最小或最大值（因此我希望数据结构始终保持排序状态），并在请求插入新元素时自动弹出/丢弃最旧的元素（或者至少能够高效地实现）。

因此，我想找到一种基于FIFO的优先队列。

非常感谢任何帮助。

- oracle3001

---

可能是重复的问题：有限空间的优先队列：寻找一个好的算法 - geekosaur

那个发帖者询问一种数据结构，其中“元素不需要以任何方式排序”。我需要固定大小、先进先出，并且始终保持排序。 - oracle3001

这个链接不适合吗：http://msdn.microsoft.com/en-us/library/4ef4dae9.aspx？根据容器的大小，我会使用vector或deque，并在需要时应用“algorithm”函数“sort”，“min”和“max”，它应该仍然足够快以满足您的需求。 - EdChum

我将要重复执行这个过程数百万次，并且作为实时流程的一部分，因此我的初步想法是不断重新排序并不是最好的方式。 - oracle3001

如果网络足够稳定，让我再试一次：实际上这个重复的链接是https://dev59.com/g1XTa4cB1Zd3GeqP0EiW，它显然错误地指向了那个链接。 - geekosaur

抱歉，我仍然没有在那篇文章中看到解决方案。虽然它再次满足了固定大小和排序的要求，但没有讨论如果发送插入请求并且已达到最大大小时如何删除“最旧”的元素。 - oracle3001

Answer 1

为什么不同时使用 std::set 或 multiset 和像 std::queue 一样的常规 FIFO 队列，用于迭代器指向该集合? 在每次插入时，检查队列是否变得比最大大小更大，然后从队列和集合中删除前面的元素。

- Tavian Barnes

---

我可以理解从指针队列或堆的头部不断弹出元素有多么高效。然而，从集合中连续删除元素的效率如何？因为这些元素可能在二叉搜索树的任意位置。 - oracle3001

根据 http://www.sgi.com/tech/stl/SortedAssociativeContainer.html，给定一个迭代器进行删除的时间复杂度为 O(1)。 - Tavian Barnes

好的，很酷......我现在在考虑使用Boost Circular Buffer来存储指针。经过“运行期”后，每次迭代只需弹出前面的元素即可。 - oracle3001

对于任何来到这个帖子的人...我现在发现，显然你要找的是LRU（最近最少使用）Map，或者根据你的需求是LRA（最近最少添加）Map。 - oracle3001