带有lambda比较器错误的C++ 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<ListNode *> &lists

// 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);