C++ priority_queue Example

Posted on Edited on In 评论: Views:

LeetCode Top K Frequent Words need to use STL priority_queue to solve the problem.

priority_queue definition:

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.