STL priority_queue copies the comparator class

Question

I am trying to create a priority queue using a special comparator:

std::priority_queue<int, std::vector<int>, MyComparator> pq; 

My problem is that MyComparator has a way to store additional state. Since MyComparator is copied to the priority queue (as far as I can tell), I will not be able to call this method on the MyComparator instance stored in the priority queue. Is there any way:

• Access the MyComparator instance stored in the priority queue, or:
• somehow pass the original instance of MyComparator by reference

Answer 1

Comparison objects used in STL containers, as well as predicates used in STL algorithms, must be objects to be copied, and methods and algorithms can copy these functions, no matter how they wish.

This means that if the comparison object contains a state, this state must be copied correctly, so you may need to provide a suitable copy constructor and copy assignment operator.

If you want the comparison object to contain a variable state, the problem is more complicated, since any copies of the comparison object must share the mutable state. If you can save state as a separate object, then you can have comparison objects keep a pointer to this external state; if not, you will probably find that you need shared ownership of the shared state, so you might need something like tr1::shared_ptr to manage this.

Answer 2

I came across this before myself with the std :: sort compator template argument. Determining the appropriate copy constructor should do the trick, for example:

 class MyComparator { public: MyComparator(const MyComparator& other) { // copy members } // ... }; 

If your comparator class is heavy (and if so, this leads to many other questions ..), this should not cause a big problem.

Answer 3

This is disgusting, but you can give your MyComparator a member of static MyComparator* me , and then overload the copy constructor to assign this this pointer. There may be a better way, but nothing comes to mind.

Answer 4

You can try to specify the reference type in the template specialization:

 std::priority_queue<int, std::vector<int>, MyComparator&> pq; 

But there are cases in IIRC when this still doesn't work, and the STL implementation can force a copy anyway. I'm not sure about your question, maybe you need to define a copy / assignment constructor operator to copy any internal state, although it hurts if it's expensive to copy.