C++數據結構，支持彈出最老的插入和最大

Question

我花了一段時間研究這個，還沒有找到答案，我知道一個40多歲的語言與各種功能可能會這樣做。

我正在尋找一個數據結構來保存500個整數。我需要能夠比較最大int與給定的int。我還希望該結構能夠刪除最早插入的隊列。

是否有支持兩者的數據結構？除了運行min()之外，我不需要隨機訪問。

有優先級隊列，支持max，但它們不自動處理大小。我可以寫我自己的功能來做到這一點，但認爲我會問無論如何/

Answer 1

要保存500個整數你想要一個循環緩衝區。它在加速：

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

你可以不完全兩者同時進行，因爲要求刪除的最古老的元素，首先需要通過插入順序排序，而要求發現min或max元素需要以某種方式按值排序（線性或像priority_queue那樣的堆）。

在現代機器上查找500個整數的最小/最大值應該非常快。但是，如果你反對線性掃描的算法複雜度，你可以試試這個：在set<int>，讓你*begin()和*rbegin()

1. Store中的元素，以獲得最小值和最大值。
2. 將迭代器存儲到集合中的一個單獨的循環緩衝區中。通過插入和擦除其他迭代器，設置迭代器不會失效，所以這是安全的。當循環緩衝區已滿時，從集合中刪除最老的迭代器，然後從循環緩衝區中清除它。