C++ Priority queue to find and modify objects

Question

I am trying to implement an A* algorithm and I need a priority queue, but the the std::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.

Can I do this using the std::priority_queue somehow?

I would appreciate code suggestions since I don't have much experience with 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."

You can well do this for any kind of class providing an appropriate Compare class parameter.

std::priority_queue<T> requires the underlying Container to comply with the concept of a SequenceContainer.

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

you can take the address of the std::priority_queue<T>::front() reference, and iterate through the queue, to find certain instances.

---

If you really need to have uniquely existent instances of objects, that should be managed additionally by some priority algorithm, it could be a good idea to store smart pointers (e.g. std::shared_ptr<T>), rather than values or raw pointers. The Compare class needs to be adapted appropriately of course.

---

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."

Using the priority queue with std::shared_ptr as shown in the above sample, may also release you from even need to find instances in the queue, and synchronize data modifications from the original instance.