Custom comparator for priority queue

Question

I want to implement K nearest neighbor search using KD tree

For maintaining nearest points, I construct a priority queue where each element is of type double* (pointer to array). I have my custom comparator class to which I pass 2 parameters, double* query and int d (dimension):

priority_queue <double* , vector<double*>, comparator(query,d) > min_heap;

My comparator class looks like this:

class comparator{
    double* query;
    int d;
    public:
        int operator()( double* point1,  double* point2) {
            double dist1 = 0,dist2 = 0;
            for(int i=0;i<d;i++){
                dist1 += (point1[i] - query[i]) * (point1[i] - query[i]);
                dist2 += (point2[i] - query[i]) * (point2[i] - query[i]);
            }
            return dist1 < dist2;
        }

        comparator(double * query,int d)
        {
            this->query = query;
            this->d = d;
        }
};

I get the following errors:

main.cpp:92:63: error: temporary of non-literal type ‘comparator’ in a constant expression

priority_queue , comparator(query,d) > min_heap;

main.cpp:20:7: note: ‘comparator’ is not literal because:
class comparator{

main.cpp:20:7: note: ‘comparator’ is not an aggregate, does not have a trivial default constructor, and has no constexpr constructor that is not a copy or move constructor

main.cpp:92:65: error: type/value mismatch at argument 3 in template parameter list for ‘template class std::priority_queue’

priority_queue , comparator(query,d) > min_heap;

main.cpp:92:65: note: expected a type, got ‘comparator(query, d)’

I am not well versed with const and constexpr and their usage. I am stuck here for a while and can't understand the errors. Any help is appreciated.

Sergey Kalinichenko Sergey Kalinichenko · Accepted Answer · 2018-03-30T14:15:41

You are trying to pass the object to the template parameter; however, template parameters must be types, so the third parameter needs to be the type of your comparator.

As for the comparator object, it needs to be passed to the constructor of your priority_queue, like this:

comparator pq_cmp(query, d);
priority_queue <double* , vector<double*>, decltype(pq_cmp) > min_heap(pq_cmp);

Demo.

Custom comparator for priority queue

1 Answers