如何迭代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容器。但是，您需要将优先级编码为包含对象状态的一部分。