CODEWITHSUNDEEP
c++c++11stdpriority-queue
amit
amit

Reputation: 178411

Unable to pass derived Compare to std::priority_queue

I need to pass a derived comparator to std::priority_queue, but for some reason the base class' operator() is being called.

Here is a minimal code that shows this behavior:

class Base {
    public:
    virtual bool operator() (int l, int r) const {
        cout << "Should not be called" << std::endl;
        return 0;
    }
    virtual ~Base() {}
};
class A : public Base { 
    public:
    bool operator() (int l, int r) const override {
        cout << "Should be called!!!!";
        return l < r;
    }
};
int main() {
    priority_queue<int, vector<int>, Base> pq((A()));
    pq.push(1);
    pq.push(2);
    pq.push(3);
    pq.push(0);
    cout << pq.top();
    return 0;
}

The code is available on ideone as well

Note that I cannot use priority_queue<int, vector<int>, A>, because I have other subclasses for Base, and that will result in a lot of code duplication1.

What am I doing wrong? How can I pass a comparator to the priority_queue that will be used during its life time?

(1) I know I can bypass the code duplication issue by using template functions that accept priority_queue<int,vector<int>, T> - but I really rather not to.

Upvotes: 6

Views: 199

Answers (2)

NathanOliver
NathanOliver

Reputation: 180490

The constructor takes a const Compare& which would not cause any slicing when passing the object to the function but we then have in the documentation

Copy-constructs the underlying container c with the contents of cont. Copy-constructs the comparison functor comp with the contents of compare.

Since a copy is happening and the template type is Base you are only going to copy and store the Base part of the A object.

You will have to wrap the comparison object in some sort of wrapper and expose a non virtual operator () that will call the virtual operator() of the type passed to the priority_queue constructor.

Upvotes: 5

Zulan
Zulan

Reputation: 22660

The standard specifies Compare comp as value members of the class template in 23.6.4.1. The constructors are said to:

Initializes comp with x and c with y (copy constructing or move constructing as appropriate);

Therefore you have slicing, even if the parameter type is actually a const Compare&.

To work around that, you could implement a pimpl-wrapper for the comparator. This wrapper would internally keep a Base& to the actual comparator, and in it's non-virtual operator() simply call the virtual operator() of the Base / A comparator.

Please think carefully about the lifetime of your A Object. Depending on the needed state of your Comparator, you could implement a virtual clone-method in Base. And keep Base as a std::unique_ptr<Base> in your PimplCompare - which you clone in it's copy-ctor. Or you keep it as std::shared_ptr<Base>.

Upvotes: 8

Related Questions