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

Question

我需要一个优先级队列，我可以在其中增加或减少优先级键。所以 boost::mutable_queue 尽管缺乏文档，但似乎很完美。

问题是我需要在某个时候迭代队列中的所有元素。我怎样才能做到这一点？

或者是否有其他可以工作的数据结构（最好是在 boost 中）？

Answer 1

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

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

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

如果您自己管理堆，那么您可以。但是，您需要使用未记录的std::__adjust_heap函数 from <heap.h>。您可以在 Alexander Stepanov （STL 的发明者）的采访中了解为什么没有记录此功能。它必须被“删除”，因为显然 STL 太大了，这也是原始标准中的哈希映射发生的情况。

Answer 2

问题是我需要在某个时候迭代队列中的所有元素。我怎样才能做到这一点？

这mutable_queue只是一个适配器。传入适当的底层容器。进一步注意，作为适配器，它会修改您可用的接口。根据定义，队列通常不允许迭代。如果是这样，则无需使用此适配器。有关此限制，请参阅 SGI STL 文档。

或者是否有其他可以工作的数据结构（最好是在 boost 中）？

您可能需要为您的目的使用不同的数据结构。适当的选择取决于您希望如何存储和访问数据。你可能想看看std::deque容器。但是，您需要将优先级编码为包含对象状态的一部分。