C++ 优先级队列查找和修改对象

Question

我正在尝试实现一个 A* 算法并且我需要一个优先级队列，但是 std::priority_queue 对我不起作用，因为我需要找到一个元素(a Node 对象)是否在 priority_queue 中，以访问其数据并在必要时修改它。

我能以某种方式使用 std::priority_queue 来做到这一点吗？

我将不胜感激代码建议，因为我对 std::priority_queue 没有太多经验。

Answer 1

"but the the stl::priority_queue doesn't work for me because I need to find whether an element(a Node object) is in the priority_queue or not, to access its data and to modify it if necessary."

您可以对提供适当 Compare 的任何类型的类执行此操作类参数。

std::priority_queue<T>需要基础 Container遵守一个 SequenceContainer 的概念.

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

你可以取std::priority_queue<T>::front()的地址引用并遍历队列以查找特定实例。

---

如果你真的需要有唯一存在的对象实例，那应该由一些优先级算法额外管理，存储智能指针(例如 std::shared_ptr<T> )而不是值或原始指针可能是个好主意。 Compare当然，类(class)需要适当调整。

---

struct CompareNodes {
    bool operator
        ( const std::shared_ptr<Node>& lhs
        , const std::shared_ptr<Node>& rhs
        ) {
        // Provide some operation to compare lhs < rhs (less) results in true
        // This function is meant to determine the actual priority of your Node
        // instances, when referenced in the priority_queue<> in question.
    }
};

std::priority_queue
    < std::shared_ptr<Node>
    , std::vector<std::shared_ptr<Node>>
    , CompareNodes
    > myQueue;

---

"to access its data and to modify it if necessary."

使用优先级队列 std::shared_ptr如上面的示例所示，您甚至无需在队列中查找实例，并同步来自原始实例的数据修改。