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

Question

我正在尝试实现一个A*算法,我需要一个优先级队列,但这std::priority_queue对我不起作用,因为我需要找到一个元素(一个Node对象)是否在priority_queue,访问其数据和修改如果有必要的话.

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

我很感激代码建议,因为我没有太多的经验std::priority_queue.

Answer 1

“但是 stl::priority_queue 对我不起作用，因为我需要查找元素（Node 对象）是否在priority_queue 中，以访问其数据并在必要时修改它。”

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

std::priority_queue<T>要求底层Container遵守a的概念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需要适当调整。

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;

“访问其数据并在必要时修改它。”

std::shared_ptr如上例所示使用优先级队列，还可以让您不再需要在队列中查找实例，并从原始实例同步数据修改。