为什么函数比较器不能像在排序中那样在优先级队列中工作？

Question

We have a question, which discusses how to use a comparator in priority_queue in C++. He gives the overloaded operator class (or struct) as the third argument and it works fine. But bool function doesn't work. Why ? But it works fine in sort of the <algorithm>. When I looked into docs (priority_queue && algo/sort), 它们都将 class Compare 作为可选的第三个参数。

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

bool cmp (const int &a,const int &b){ return a > b; }

struct cmp2
{
    bool operator() (const int &p1,const int &p2)
    {
        return p1 > p2;
    }
};

int main ()
{
//  freopen("test.txt","r",stdin);
    int a[10];
    vector<int> b(10);
    sort( a , a + 10, cmp );    // working cool
    sort( b.begin() , b.end() , cmp);   // working great
    priority_queue<int, vector<int> , cmp2 > x;    // as usual, working....
    priority_queue<int, vector<int> , cmp > y;   // not working why ?

    return 0;
}

错误：

A:\pqvsarray.cpp    In function 'int main()':
27  40  A:\pqvsarray.cpp    [Error] type/value mismatch at argument 3 in template parameter list for 'template<class _Tp, class _Sequence, class _Compare> class std::priority_queue'
27  40  A:\pqvsarray.cpp    [Error] expected a type, got 'cmp'
27  43  A:\pqvsarray.cpp    [Error] invalid type in declaration before ';' token

那么，为什么不同？

Answer 1

答案在编译器错误中。优先级队列的第三个模板参数是比较器类型（如结构或类）而不是函数。

Answer 2

如错误消息所示，函数不能用作模板参数。 priority_queue 将复制 比较类型 的对象。例如，这可能是 std::less<int>，其中该类型的对象是 std::less<int>()，被调用的是 std::less<int>()(x, y)。在 C++11 中，您可以使用 decltype，但在 C++03 中，"canonical" 方法是创建一个 "functor"（一个专门用作函数对象的完整类型。 ) 这就是 lambdas 被创建的原因之一。

Answer 3

您也可以使用带有 std::priority_queue 的函数。您所做的不同之处在于，您将函数作为函数参数传递给 std::sort，但您尝试将函数定义为队列的模板参数。这显然不起作用，因为第三个参数是错误解释的类型参数。此外，你甚至不能有指针或引用模板参数。

如果你看一下reference，你会发现队列有一个用于传递比较对象的构造函数。那是你必须传递函数的地方。

与std::sort有区别。 Sort 是一个函数，您可以让编译器 deduce 它是模板参数，这样您就不必显式指定它们。队列是一个 class 模板，无法推导出 class 模板的模板参数（至少在这种情况下不能）。

模板参数默认为 std::less<typename Container::value_type>，但您不想使用它。因此，您必须明确指定比较对象的类型。你在你现在试图传递对象的地方指定它。你可能会问如何获取函数的类型pointer/reference。你可以这样做：decltype(&cmp)。如果你有一个不支持 decltype 的过时编译器，那么你需要指定没有它的类型：bool (&)(const int&, const int&).

这是一个示例，说明如何创建一个使用您的函数的队列。

std::priority_queue<int, std::vector<int>, decltype(&cmp)> x(cmp);

为什么函数比较器不能像在排序中那样在优先级队列中工作？

Why function comparator doesn't work in priority queue like it does in sort?

c++

sorting

stl

compare

priority-queue