Namespaces
Variants
Views
Actions

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

From cppreference.com
< cpp‎ | container
(Add example of using lambda with priority queue.)
(→‎Template parameters: LWG2566)
Line 17: Line 17:
 
===Template parameters===
 
===Template parameters===
 
{{par begin}}
 
{{par begin}}
−
{{par | T | The type of the stored elements.}}
+
{{par | T | The type of the stored elements. {{rev inl|since=c++17|The behavior is undefined if {{tt|T}} is not the same type as {{tt|Container::value_type}}.}} }}
 
{{par | Container | The type of the underlying container to use to store the elements. The container must satisfy the requirements of {{concept|SequenceContainer}}, and its iterators must satisfy the requirements of {{concept|RandomAccessIterator}}. Additionally, it must provide the following functions with the usual semantics:
 
{{par | Container | The type of the underlying container to use to store the elements. The container must satisfy the requirements of {{concept|SequenceContainer}}, and its iterators must satisfy the requirements of {{concept|RandomAccessIterator}}. Additionally, it must provide the following functions with the usual semantics:
  

Revision as of 21:08, 5 March 2016

 
C++
 
Containers library
 
std::priority_queue
 
Defined in header <queue>
template<

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

> class priority_queue;

A priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.

A user-provided Compare can be supplied to change the ordering, e.g. using std::greater<T> would cause the smallest element to appear as the top().

Working with a priority_queue is similar to managing a heap in some random access container, with the benefit of not being able to accidentally invalidate the heap.

Contents

Template parameters

T - The type of the stored elements. The behavior is undefined if T is not the same type as Container::value_type.(since C++17)
Container - The type of the underlying container to use to store the elements. The container must satisfy the requirements of Template:concept, and its iterators must satisfy the requirements of Template:concept. Additionally, it must provide the following functions with the usual semantics:
  • front()
  • push_back()
  • pop_back()

The standard containers std::vector and std::deque satisfy these requirements.

Compare - A Template:concept type providing a strict weak ordering.

Member types

Member type Definition
container_type Container[edit]
value_type Container::value_type[edit]
size_type Container::size_type[edit]
reference Container::reference[edit]
const_reference Container::const_reference[edit]

Member functions

 constructs the priority_queue
(public member function) [edit]
destructs the priority_queue
(public member function) [edit]
assigns values to the container adaptor
(public member function) [edit]
Element access
accesses the top element
(public member function) [edit]
Capacity
checks whether the container adaptor is empty
(public member function) [edit]
returns the number of elements
(public member function) [edit]
Modifiers
inserts element and sorts the underlying container
(public member function) [edit]
(C++11)
 constructs element in-place and sorts the underlying container
(public member function) [edit]
removes the top element
(public member function) [edit]
(C++11)
 swaps the contents
(public member function) [edit]

Member objects

Container c
 the underlying container
(protected member object) [edit]
Compare comp
 the comparison function object
(protected member object)

Non-member functions

(C++11)
 specializes the std::swap algorithm
(function template) [edit]

Helper classes

(C++11)
 specializes the std::uses_allocator type trait
(class template specialization) [edit]

Example

Run this code
#include <functional>
#include <queue>
#include <vector>
#include <iostream>
 
template<typename T> void print_queue(T& q) {
    while(!q.empty()) {
        std::cout << q.top() << " ";
        q.pop();
    }
    std::cout << '\n';
}
 
int main() {
    std::priority_queue<int> q;
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q.push(n);
 
    print_queue(q);
 
    std::priority_queue<int, std::vector<int>, std::greater<int> > q2;
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q2.push(n);
 
    print_queue(q2);
 
    // 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)> q3(cmp);
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q3.push(n);
 
    print_queue(q3);
 
}

Output: 

9 8 7 6 5 4 3 2 1 0 
0 1 2 3 4 5 6 7 8 9 
8 9 6 7 4 5 2 3 0 1
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/container/priority_queue&oldid=83652"