具有自定义类型和比较器的 C++ 优先级队列不起作用

Question

我正在尝试将 C++ STL 优先级队列与自定义类型和比较器一起使用，但无论我怎么说，我总是收到错误。

有人知道问题出在哪里吗？我正在尝试从文档中复制语法，但没有任何效果...

自定义类型是指向LeetCode中使用的ListNodeclass的指针：

 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

在我的 class 中，我有一个静态比较函数：

static bool compare(ListNode* n1, ListNode* n2) {
    return n1->val < n2->val;
}

我正在尝试像这样初始化优先级队列：

priority_queue<ListNode*, vector<ListNode*>, decltype(compare)> pq(compare);

但我一直收到错误消息：

In file included from prog_joined.cpp:1:
In file included from ./precompiled/headers.h:55:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/queue:64:
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_queue.h:485:18: error: data member instantiated with function type 'bool (ListNode *, ListNode *)'
      _Compare   comp;
                 ^
Line 137: Char 73: note: in instantiation of template class 'std::priority_queue<ListNode *, std::vector<ListNode *, std::allocator<ListNode *>>, bool (ListNode *, ListNode *)>' requested here
        priority_queue<ListNode*, vector<ListNode*>, decltype(compare)> pq(compare);
                                                                        ^
1 error generated.

谢谢！

Answer 1

您应该指定函数指针类型，而不是函数类型作为 priority_queue 的模板参数。

改变

priority_queue<ListNode*, vector<ListNode*>, decltype(compare)> pq(compare);

至

priority_queue<ListNode*, vector<ListNode*>, decltype(compare)*> pq(compare);
//                                                            ^

Answer 2

您可以定义一个 lambda，而不是声明和定义静态函数。

auto compare = [](ListNode* n1, ListNode* n2) {
    return n1->val < n2->val;
};

由于 lambda 的类型由编译器自动解析，因此您无需考虑参数类型是函数指针还是函数等问题

decltype(...) 无论如何都会解析为可调用对象。

具有自定义类型和比较器的 C++ 优先级队列不起作用

C++ Priority queue with custom type and comparator not working

c++

compiler-errors

priority-queue