I implemented a priority queue using STL. And that part is working great. Now, looking back on my problem it seems as though I need to know if a certain node exists in the queue. So I am looking some advice on what the best course of action would be in regards to searching an existing priority queue.

I was thinking something along the lines of a hash table, but I have little experience in implementing them so I am not really sure on how to start.

In any case, any help would be appreciated.

Check out the implementations of map and multimap if you want to know about the implementation of hash tables.

But in my view instead of creating a separate hash table why not use the functionality of priority_queue itself which has the largest element always at top? Try to collect the elements of the priority_queue in decreasing order may be in an array over which you can use a binary search.