custom comparator without default constructor as template parameter

Question

Let's look at a toy example of finding the smallest m pairs of numbers from two sorted arrays. The algorithm efficiency issue aside, I would want to supply the priority queue with a comparator that needs certain parameters during initialization:

class Foo {
    struct natural_order {
        const std::vector<int> &x,&y;
        natural_order( const std::vector<int> &x, const std::vector<int> &y ): x(x), y(y) {};
        bool operator () ( const std::pair<int,int> &a, const pair<int,int> &b ) const {
            return x[a.first]+y[a.second] < x[b.first]+y[b.second];
        }
    };
    struct cmp {
        std::unique_ptr<natural_order> o;
        cmp( const std::vector<int> &x, const std::vector<int> &y ) {
           o= std::make_unique<natural_order>(x,y);
        }
        bool operator () ( const std::pair<int,int> &a, const pair<int,int> &b ) const {
            return (*o)(b,a);
        }
    };
public:
    std::vector<std::vector<int>> m_smalles_pairs( std::vector<int> &x, std::vector<int> &y, int m ) {
        std::vector<std::vector<int>> res(m);
        std::priority_queue<int,std::vector<int>,cmp(x,y)> pq; //<-- the problem is here. Does not compile
        for ( int i= 0; i < m; ++i ) {
            auto pr= pq.top(); pq.pop();
            res[i]= std::vector<int>{x[pr.first],y[pr.second]};
            if ( pr.first+1 < x.size() )
                pq.push({pr.first+1,pr.second});
            if ( pr.second+1 < y.size() )
                pq.push({pr.first,pr.second+1});
        }
        return res;
    }
};

Essentially, I would like the comparator to be initialized with an argument, but how to supply this as the third argument of priority_queue? If the x and y params were not needed, I would simply write cmp in the above.

EDIT: it appears to proceed in similar lines using lambdas, as described here C++ priority_queue with lambda comparator error I was able to solve my problem, but just being curious if struct-comparator allows this sort of thing.

score 1 · Accepted Answer · answered Feb 04 '20 at 12:47

Essentially, the problem with your code is the implementation of the Compare. Technically speaking, a Compare-class must satisfy some requirements:

The type T satisfies BinaryPredicate ---> CopyConstructible

Your class cmp is not copy constructible because one of its members is a std::unique_ptr (it cannot be copied).

So I would say that a proper solution should be to refactor your design in accordance with that principle. I am not aware of the full domain of your problem, so I cannot suggest what it's the proper design (moreover this may be a personal choice).

Perhaps, you can remove the std::unique_ptr from your class and just having natural_order type as a member. Of course, that implies different copy-construction calls.

At that point, you can just initialize the comparator of your std::priority_queue using the proper constructor.

(2) explicit priority_queue(const Compare& compare)
           : priority_queue(compare, Container()) { }

Your code should be something like:

std::priority_queue<int,std::vector<int>,cmp> pq(cmp{x, y});

custom comparator without default constructor as template parameter

1 Answers1