C++ priority_queue使用示例

发表于 2022-01-05 更新于 2022-05-03 分类于 Coding Interview 评论：阅读次数：

LeetCode Top K Frequent Words 中会用到priority_queue，同时需要定义priority_queue的排序算法。

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

有两种方式实现自定义类型priority_queue的比较函数。

重载算符比较函数

需要定义一个类Cmp，重载()算符：

struct Cmp {
    bool operator()(const pair<string, int> &a, const pair<string, int> &b)
    {
        if (a.second == b.second) return a.first < b.first;
        return a.second > b.second;
    };
};

priority_queue<pair<string, int>, vector<pair<string, int>>, Cmp> pq;

lambda比较函数

使用lambda函数定义比较函数的方法更简洁，可省去引入一个新的辅助类。

auto cmp = [](const pair<string, int> &a, const pair<string, int> &b)
{
    if (a.second == b.second) return a.first < b.first;
    return a.second > b.second;
};
priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp)> pq(cmp);

注意: 此处与重载算符的初始化方法不同，一定要把比较函数cmp也传入构造函数。否则会出现编译错误：

Line 16: Char 85: error: no matching constructor for initialization of 'priority_queue<pair<std::string, int>, vector<pair<std::string, int>>, decltype(cmp)>' (aka 'priority_queue<pair<basic_string, int>, vector<pair<basic_string, int>>, (lambda at solution.cpp:20:20)>') priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp)> pq; ^ /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_queue.h:501:2: note: candidate template ignored: requirement '__and_<std::is_default_constructible<(lambda at prog_joined.cpp:20:20)>, std::is_default_constructible<std::vector<std::pair<std::__cxx11::basic_string<char, std::char_traits, std::allocator>, int>, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits, std::allocator>, int>>>>>::value' was not satisfied [with _Seq = std::vector<std::pair<std::__cxx11::basic_string, int>, std::allocator<std::pair<std::__cxx11::basic_string, int>>>] priority_queue() ^ /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_queue.h:516:2: note: candidate constructor template not viable: requires single argument '__a', but no arguments were provided priority_queue(const _Alloc& __a) ^ /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_queue.h:443:11: note: candidate constructor (the implicit copy constructor) not viable: requires 1 argument, but 0 were provided class priority_queue ^ /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_queue.h:443:11: note: candidate constructor (the implicit move constructor) not viable: requires 1 argument, but 0 were provided /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_queue.h:505:7: note: candidate constructor not viable: requires 2 arguments, but 0 were provided priority_queue(const _Compare& __x, const _Sequence& __s) ^ /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_queue.h:510:7: note: candidate constructor not viable: requires at least argument '__x', but no arguments were provided priority_queue(const _Compare& __x, _Sequence&& __s = _Sequence()) ^ /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_queue.h:520:2: note: candidate constructor template not viable: requires 2 arguments, but 0 were provided priority_queue(const _Compare& __x, const _Alloc& __a) ^ /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_queue.h:537:2: note: candidate constructor template not viable: requires 2 arguments, but 0 were provided priority_queue(const priority_queue& __q, const _Alloc& __a) ^ /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_queue.h:541:2: note: candidate constructor template not viable: requires 2 arguments, but 0 were provided priority_queue(priority_queue&& __q, const _Alloc& __a) ^ /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_queue.h:526:2: note: candidate constructor template not viable: requires 3 arguments, but 0 were provided priority_queue(const _Compare& __x, const _Sequence& __c, ^ /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_queue.h:532:2: note: candidate constructor template not viable: requires 3 arguments, but 0 were provided priority_queue(const _Compare& __x, _Sequence&& __c, const _Alloc& __a) ^ /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_queue.h:573:2: note: candidate constructor template not viable: requires 4 arguments, but 0 were provided priority_queue(_InputIterator __first, _InputIterator __last, ^ /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_queue.h:584:2: note: candidate constructor template not viable: requires at least 2 arguments, but 0 were provided priority_queue(_InputIterator __first, _InputIterator __last, ^ 1 error generated.