C ++ Priority Queue for finding and modifying objects

Question

I am trying to implement the A * algorithm, and I need a priority queue, but std::priority_queue does not work for me, because I need to determine whether an element ( Node object) is in priority_queue or not, in order to access its data and, if necessary, change it.

Can I do this with std::priority_queue somehow?

I would appreciate code suggestions since I don't have much experience with std::priority_queue .

Answer 1

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

You can do this for any class by providing the appropriate Compare class parameter.

std::priority_queue<T> requires the underlying Container conform to the concept of SequenceContainer .

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

you can take the directory address std::priority_queue<T>::front() and iterate through it in turn to find specific instances.

---

If you really need to have uniquely existing instances of objects that need to be additionally managed using some sort of priority algorithm, it might be a good idea to store smart pointers (like std::shared_ptr<T> ) rather than values ​​or raw pointers. The Compare class must be adapted accordingly.

---

 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 his data and, if necessary, modify it."

Using the priority queue with std::shared_ptr , as shown in the above example, can also free you from even having to find instances in the queue and synchronize data changes with the original instance.