Difference between revisions of "cpp/container/priority queue"

#include <functional>
#include <queue>
#include <vector>
#include <iostream>
 
template<typename T>
void print(T q, std::string name) {
    std::cout << name << ": \t";
    for (auto n : q)
        std::cout << n << ' ';
    std::cout << '\n';
}
 
template<typename T>
void print_queue(T q, std::string name) { // NB: pass by value so the print uses a copy
    std::vector<typename T::value_type> content;
    while(!q.empty()) {
        content.push_back(q.top());
        q.pop();
    }
    print(content, name);
}
 
int main() {
    const auto data = {1,8,5,6,3,4,0,9,7,2};
    print(data, "data");
 
    std::priority_queue<int> q1; // Max priority queue
    for(int n : data)
        q1.push(n);
 
    print_queue(q1, "q1");
 
    // Min priority queue
    // std::greater<int> makes the max priority queue act as a min priority queue
    std::priority_queue<int, std::vector<int>, std::greater<int>>
        minq1(data.begin(), data.end());
 
    print_queue(minq1, "minq1");
 
    // Second way to define a min priority queue
    std::priority_queue minq2(begin(data), end(data), std::greater<int>());
 
    print_queue(minq2, "minq2");
 
    // Using a custom function object to compare elements.
    struct {
        bool operator() (const int l, const int r) const { return l > r; }
    } customLess;
    std::priority_queue minq3(begin(data), end(data), customLess);
 
    print_queue(minq3, "minq3");
 
    // Using lambda to compare elements.
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> q5(cmp);
 
    for(int n : data)
        q5.push(n);
 
    print_queue(q5, "q5");
}