C++ priority_queue Example
LeetCode Top K Frequent Words need to use STL priority_queue to solve the problem.
template<
class T,
class Container = std::vector<T>,
class Compare = std::less<typename Container::value_type>
> class priority_queue;
There are two ways to implement the priority_queue compare function of customized type.
Overload Operator
Define a struct Cmp
and overload operator
()
:
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 Function
It would be simpler to implement the compare function using lambda. No extra struct is needed:
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);
Notice: the priority_queue constructor here is different with
overloading operator. The compare function cmp
MUST
be passed into the constructor. Otherwise, compile error
occurs:
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.