如何迭代boost :: mutable_queue

Question

我需要一個優先級隊列，我可以增加或減少優先級鍵。所以儘管缺少文檔，boost :: mutable_queue看起來很完美。

問題是我需要在隊列中的所有元素的某個點迭代。我怎樣才能做到這一點？

或者是否有其他數據結構可以工作（最好是提升）？

Answer 1

隊列不用於迭代。隊列的全部要點是你只能看到隊列前面的元素。

如果你想迭代，那麼我建議只使用std::set，它是有序的。當你想修改一個元素時，你必須刪除它並用新的鍵重新插入它。您可以使用mySet.begin()（返回一個迭代器）獲得最高優先級的元素。

理想情況下，您需要使用堆。 STL提供堆砌功能，這就是std::priority_queue使用的功能。但是，您無法修改堆中的密鑰，因爲它沒有接口。

如果你自己管理堆，那麼你可以。但是，您需要使用<heap.h>中的std::__adjust_heap函數，該函數沒有記錄。你可以在this interview with Alexander Stepanov（STL的發明者）閱讀關於爲什麼這個功能沒有記錄的所有信息。它必須被「刪除」，因爲顯然STL太大了，這也是原始標準中哈希映射的情況。

Answer 2

問題是我需要在隊列中的所有元素的某個點迭代。我怎樣才能做到這一點？

mutable_queue只是一個適配器。傳入適當的基礎容器。還要注意，作爲一個適配器，它會修改可用的接口。根據定義，隊列通常不允許迭代。如果是這樣，就不需要使用這個適配器。請參閱關於this限制的SGI STL文檔。

或者是否有其他數據結構可以工作（最好是在boost中）？

您可能需要爲您的目的使用不同的數據結構。一個合適的選擇取決於你想如何存儲和訪問你的數據。你可能想看看std::deque容器。但是，您需要將優先級編碼爲包含對象狀態的一部分。