C++仍然按值排序的數據結構＆操作FIFO

我正在尋找一種執行快速排序插入並基於FIFO操作的數據結構。C++仍然按值排序的數據結構＆操作FIFO

我想要實現的是一個固定大小的數據結構來保存一系列值。在迭代的每一個新步驟中，我都希望能夠高效地找到最小或最大值（因此我希望數據結構始終被排序），並且在請求插入新元素時，最早的元素將自動（或者至少能夠有效地）彈出/丟棄。

所以我想我正在尋找某種FIFO優先級隊列。

任何幫助非常感謝。

2012-04-21 oracle3001

[有限空間的優先級隊列：尋找一個好的算法]的可能的副本（http://stackoverflow.com/questions/2933758/priority-queue-with-limited-space-looking-for-a-good-算法） – geekosaur 2012-04-21 21:10:23

那張海報問的是「元素不需要以任何方式排序」的數據結構。我需要固定大小的FIFO，並且始終保持排序狀態。 – oracle3001 2012-04-21 21:15:36

這是不適合的：http://msdn.microsoft.com/en-us/library/4ef4dae9.aspx？根據容器的大小，我只是使用vector或deque，並且在需要時應用'algorithm'函數'sort'，'min'和'max'，它應該仍然足夠快以滿足您的需求。 – EdChum 2012-04-21 21:19:49

爲什麼不把std :: set或multiset和一個像std :: queue的迭代器這樣的常規FIFO隊列放入該集合？在每次插入時，檢查隊列是否大於最大大小，然後從隊列和集合中刪除前端元素。

來源

2012-04-21 21:40:21

我可以看到，如何從隊列或指針堆頂部彈出非常高效。但是，從一個集合中繼續刪除操作的效率如何，其中元素可能位於二叉查找樹中的任何位置？ – oracle3001 2012-04-21 22:23:22

根據http://www.sgi.com/tech/stl/SortedAssociativeContainer.html，刪除給定的迭代器是O（1）。 – 2012-04-21 22:25:20

好吧，我現在想我可能會使用Boost循環緩衝來存儲指針。在「運行期」之後，它應該簡單地通過在每次迭代時彈出前端元素。 – oracle3001 2012-04-21 22:36:51

C++仍然按值排序的數據結構＆操作FIFO

回答

相關問題