C++具有 lambda 比较器错误的priority_queue

Question

我尝试在 VC2010 中编译以下错误代码，但收到错误 C2974 仅当我包含 lambda 表达式时才会发生这种情况，所以我猜测它与此有关。

typedef pair<pair<int, int>, int> adjlist_edge;
priority_queue< adjlist_edge , vector<adjlist_edge>,
    [](adjlist_edge a, adjlist_edge b) -> bool {
        if(a.second > b.second){ return true; } else { return false; }
    }> adjlist_pq;

我知道模板定义的形式是正确的，可以按

priority_queue<int , vector<int>, greater<int>> pq;

预期工作。有什么想法我做错了吗？ lambda 是否有明显的问题，看起来有问题，而我可能会忽略？感谢您的阅读！

Answer 1

首先定义 lambda 对象，然后使用 decltype 将其传递给模板的类型，并直接将其传递给构造函数。

auto comp = []( adjist a, adjlist b ) { return a.second > b.second; };
priority_queue< adjlist_edge , vector<adjlist_edge>, decltype( comp ) >
     adjlist_pq( comp );

Answer 2

priority_queue 将比较器作为模板参数。 Lambda 函数是对象，因此不能用作模板参数（只有极少数类型可以用作模板参数，其中包括整型）。

您可以尝试在那里使用 decltype：

priority_queue< adjlist_edge , vector<adjlist_edge>,
               decltype( [](adjlist_edge a, adjlist_edge b) -> bool {
                if(a.second > b.second){ return true; } else { return false; }
               })>
adjlist_pq( [](adjlist_edge a, adjlist_edge b) -> bool {
                if(a.second > b.second){ return true; } else { return false; }
             } );

如果失败（它会），您可以使用 function<>：

priority_queue< adjlist_edge , vector<adjlist_edge>,
                function<bool(adjlist_edge,adjlist_edge)> >
adjlist_pq( [](adjlist_edge a, adjlist_edge b) -> bool {
                if(a.second > b.second){ return true; } else { return false; }
            } );

Answer 3

接受的答案回答了如何使用 lambda 表达式将priority_queue 定义为自定义 Compare 对象。
我会解决这个问题的另一个方面：为什么以您的方式定义 pq 时会失败：

typedef pair<pair<int, int>, int> adjlist_edge;
priority_queue< adjlist_edge , vector<adjlist_edge>,
    [](adjlist_edge a, adjlist_edge b) -> bool {
        if(a.second > b.second){ return true; } else { return false; }}> adjlist_pq;

为什么我们在构造优先级队列时必须将 lambda 作为参数传递？原因在于lambda表达式没有默认构造函数。因此，如果在构造优先级队列时不提供它，则将调用 lambda 表达式的“假定现有的默认构造函数”。显然，它会失败。

关于您的问题：Compare 对象（lambda 或函数对象）是否具有默认构造函数会产生差异。

Answer 4

以下是使用优先级队列构建最小堆的示例。我使用 lambda 来定义比较器，给定由 vector定义的链表。 &列表

// This comparator will be used to build minheap.
auto comp = [&](ListNode *a, ListNode *b) {
    return a->val > b->val;
};

// This priority queue is the min heap
priority_queue<ListNode *, vector<ListNode *>, decltype(comp)> pq(comp);

Answer 5

从 C++ 20 开始，没有捕获的 lambda 是默认可构造的，因此我们可以简单地将 lambda 包装在 decltype 中作为第三个模板参数，而根本不需要单独的变量。

priority_queue<adjlist_edge, vector<adjlist_edge>, 
  decltype([](adjlist_edge &a, adjlist_edge &b){return a.second > b.second;})> pq;