优先级队列的自定义比较器

Question

我想用KD树实现K近邻搜索

为了维护最近点，我构建了一个优先级队列，其中每个元素都是 double* 类型（指向数组的指针）。我有我的自定义比较器 class，我向其传递了 2 个参数，double* query 和 int d (dimension):

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

我的比较器 class 看起来像这样：

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;
        }
};

我收到以下错误：

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: 注意：“比较器”不是字面意思，因为：
class 比较器{

main.cpp:20:7: 注意：'comparator' 不是聚合，没有平凡的默认构造函数，也没有不是复制或移动构造函数的 constexpr 构造函数

main.cpp:92:65: 错误：type/value ‘template class std::priority_queue'
的模板参数列表中的参数 3 不匹配

priority_queue , comparator(query,d) > min_heap;

main.cpp:92:65: 注意：需要一个类型，得到了‘comparator(query, d)’

我不太熟悉 const 和 constexpr 及其用法。我被困在这里一段时间，无法理解错误。感谢任何帮助。

Answer 1

您正在尝试将对象传递给模板参数；但是，模板参数必须是类型，因此第三个参数需要是比较器的类型。

至于比较对象，需要传递给你的priority_queue的构造函数，像这样：

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

Demo.

优先级队列的自定义比较器

Custom comparator for priority queue

c++

priority-queue