STL priority_queue copies comparator class

Question

I'm trying to create a priority queue with a custom comparator:

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

My problem is that MyComparator has a method that stores additional state. Because MyComparator is copied to the priority queue (as far as I can tell), there's no way for me to call this method on the MyComparator instance held by the priority queue. Is there any way to either:

• get access to the MyComparator instance held by the priority queue, or:
• somehow pass the original MyComparator instance in by reference

Answer 1

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

Answer 2

You can try specifying a reference type in the template specialisation:

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

But IIRC there are cases where this still doesn't work and STL implementations may force a copy anyway. I'm not sure from your question if maybe you need to define a copy constructor/assignment operator to copy whatever the internal state is, although that's painful if it's expensive to copy.

Answer 3

I've run into this before myself with std::sort's comparator template argument. Defining a proper copy constructor should do the trick, e.g.:

class MyComparator
{
    public:

        MyComparator(const MyComparator& other)
        {
            // copy members
        }

        // ...
};

Unless your comparator class is heavy (and if so, that leads to plenty of other questions..) it shouldn't cause much of an issue.

Answer 4

Comparison objects used in STL containers as well as predicates used in STL algorithms must be copyable objects and methods and algorthims are free to copy these functions however they wish.

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

If you want your comparison object to containt mutable state then the problem is more complex as any copies of your comparison object need to share the mutable state. If you can maintain the state as a separate object then you can have your comparison objects keep a pointer to this external state; if not you will probably find that you need shared ownership of the common state so you will probably require something like tr1::shared_ptr to manage this.