在std :: sort和std :: priority_queue中如何使用自定义比较函数的困惑

Question

我试图弄清楚为什么您为std::sort和定义了不同的自定义比较功能的原因std::priority_queue。

例如，因为std::sort我可以做这样的事情：

bool compare(const vector<int>& a, const vector<int>& b)
{
    return a[0] < b[0];
}
class foo
{
public:
    vector<vector<int>> f(vector<vector<int>> list)
    {
        std::sort(list.begin(), list.end(), compare);
        return list;
    }
};


int main()
{
    vector<vector<int>> t = { {2,1},{1,0},{3,7} };
    foo n;

    auto ans = n.f(t);
    for (vector<int> x : ans)
    {
        printf("x[0]: %d , x[1]: %d \n", x[0], x[1]);
    }
    return 0;
}

运行代码后，结果为：

x [0]：1，x [1]：0

x [0]：2，x [1]：1

x [0]：3，x [1]：7

但是，如果我这样定义另一个函数foo：

vector<vector<int>> f1(vector<vector<int>> list)
{
    std::priority_queue<vector<int>, vector<vector<int>>, compare> pq;
}

编译器不允许我这样做。解决这个问题的简单方法是在类内部创建一个结构，如下所示：

struct Compare
{
    bool operator()(const vector<int>& a, const vector<int>& b)
    {
        return a[0] < b[0];
    }
};

这是到目前为止我所拥有的：从en.cppreference.com，std::sort传入一个比较函数对象，但是priority_queue传入一个Compare类型。我认为这可能就是为什么我不能对优先级队列使用相同的比较功能的原因。

另一个想法是，因为std::sort是函数，而priority_queue是容器，所以我们需要使其与众不同吗？

这就是我现在所拥有的。

我对此最担心的是为什么他们的行为方式如此不同？造成这种差异的主要原因是什么？为什么我们需要与众不同？

ps任何人都有很好的书本建议，可以深入地解释STL，并且更专注于解释STL的代码，为什么他们这样做呢？

Answer 1

您指定compare的第三个模板参数为std::priority_queue，这不是正确的类型名称。您需要将其指定为函数指针类型（并将函数指针作为函数参数传递）。例如

std::priority_queue<vector<int>, vector<vector<int>>, decltype(compare)*> pq(compare);

要么

std::priority_queue<vector<int>, vector<vector<int>>, bool (*)(const vector<int>&, const vector<int>&)> pq(compare);

std::sort是一个函数模板，所以当你可以通过compare作为函数参数和模板参数可推导出自动地（作为函数指针型）; std::priority_queue是一个类模板，因此您必须显式指定template参数，只需正确指定类型（作为函数指针类型，就像自动推导其模板参数类型的类型一样std::sort）。

编辑

从C ++ 17开始，我们有了类模板参数推导，那么您可以将其用作

vector<vector<int>> f1(vector<vector<int>> list)
{
    // deduced T=vector<int>, Container=vector<vector<int>>, Compare=bool (*)(const vector<int>&, const vector<int>&)
    std::priority_queue pq(compare, list);
    return ...
}

那么我们不需要指定模板参数。