c++ - 混淆如何在 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 传入的是一个比较类型。我想这可能就是为什么我不能对优先级队列使用相同的比较函数的原因。

另一个想法是，因为std::sort是一个函数，而priority_queue是一个容器，所以我们需要让它有所不同？

这就是我目前所拥有的一切。

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

附注有没有深入讲解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 作为函数参数 传递时，模板参数 可以是deduced自动(作为函数指针类型)； std::priority_queue是一个类模板，所以你必须显式指定模板参数，你只需要正确指定类型(作为函数指针类型，就像模板参数的类型一样) em> std::sort 自动推导的类型。

编辑

从 C++17 开始我们有 class template argument deduction , 然后你可以将它用作

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 ...
}

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