c++ - 如何迭代 boost::mutable_queue

Question

我需要一个优先级队列，我可以在其中增加或减少优先级键。因此，尽管缺少文档，boost::mutable_queue 看起来还是很完美的。

问题是我需要在某个时候迭代队列中的所有元素。我该怎么做？

或者是否有其他可用的数据结构(最好在 boost 中)？

Answer 1

队列不用于迭代。队列的全部意义在于您只能查看队列前端的元素。

如果你想迭代那么我建议只使用 std::set ，这是有序的。当你想修改一个元素时，你必须删除它并用新键重新插入它。您可以使用 mySet.begin() 获得最高优先级的元素(返回一个迭代器给它)。

理想情况下，您需要使用堆。 STL 提供了制作堆的函数，这就是 std::priority_queue 的作用使用。但是，您不能修改堆中的键，因为它没有接口(interface)。

如果您自己管理堆，那么您可以。但是，您需要使用 std::__adjust_heap来自 <heap.h> 的函数，这是无证的。您可以在 this interview with Alexander Stepanov 中阅读所有有关此功能未记录的原因的信息。 (STL 的发明者)。它必须被“删除”，因为显然 STL 太大了，这也是原始标准中散列映射所发生的情况。