C++

Reference

<queue>

priority_queue

public member function
<queue>

std::priority_queue::priority_queue

initialize (1)
explicit priority_queue (const Compare& comp = Compare(),                         const Container& ctnr = Container());
range (2)
template <class InputIterator>         priority_queue (InputIterator first, InputIterator last,                         const Compare& comp = Compare(),                         const Container& ctnr = Container());
initialize (1)
priority_queue (const Compare& comp, const Container& ctnr);
range (2)
template <class InputIterator>  priority_queue (InputIterator first, InputIterator last,                  const Compare& comp, const Container& ctnr);
move-initialize (3)
explicit priority_queue (const Compare& comp = Compare(),                         Container&& ctnr = Container());
move-range (4)
template <class InputIterator>  priority_queue (InputIterator first, InputIterator last,                  const Compare& comp, Container&& ctnr = Container());
allocator versions (5)
template <class Alloc> explicit priority_queue (const Alloc& alloc);template <class Alloc> priority_queue (const Compare& comp, const Alloc& alloc);template <class Alloc> priority_queue (const Compare& comp, const Container& ctnr,                                       const Alloc& alloc);template <class Alloc> priority_queue (const Compare& comp, Container&& ctnr,                                       const Alloc& alloc);template <class Alloc> priority_queue (const priority_queue& x, const Alloc& alloc);template <class Alloc> priority_queue (priority_queue&& x, const Alloc& alloc);
Construct priority queue
Constructs a priority_queue container adaptor object.

A priority_queue keeps internally a comparing function and a container object as data, which are copies of comp and ctnr respectively.

The range version (2), on top that, inserts the elements between first and last (before the container is converted into a heap).
A priority_queue keeps internally a comparing function and a container object as data. The comparing function is a copy of comp and the underlying container depends on the constructor used:

(1) initialization constructor
The underlying container is a copy of ctnr, sorted by the make_heap algorithm.
(2) range initialization constructor
The underlying container is a copy of ctnr, with the insertion of the elements in the range [first,last), and then sorted by make_heap.
(3) move-initialization constructor
The underlying container acquires the value of ctnr by move-constructing it. The elements are sorted by make_heap.
(4) move-range initialization constructor
The underlying container acquires the value of ctnr by move-constructing. It also inserts the elements in the range [first,last) and then sorts them with make_heap.
(5) allocator constructors
Constructs a priority_queue using a specific allocator value.

The constructor effectively initializes the comparison and container objects and then calls algorithm make_heap on the range that includes all its elements before returning.

Parameters

comp
Comparison object to be used to order the heap.
This may be a function pointer or function object able to perform a strict weak ordering by comparing its two arguments.
Compare is the third class template paramete ( by default: less<T>).
ctnr
Container object.
Container is the second class template parameter (the type of the underlying container for the priority_queue; by default: vector<T>).
first,last
Input iterators to the initial and final positions in a sequence. The elements in this sequence are inserted into the underlying container before sorting it.
The range used is [first,last), which includes all the elements between first and last, including the element pointed by first but not the element pointed by last.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
// constructing priority queues
#include <iostream>       // std::cout
#include <queue>          // std::priority_queue
#include <vector>         // std::vector
#include <functional>     // std::greater

class mycomparison
{
  bool reverse;
public:
  mycomparison(const bool& revparam=false)
    {reverse=revparam;}
  bool operator() (const int& lhs, const int&rhs) const
  {
    if (reverse) return (lhs>rhs);
    else return (lhs<rhs);
  }
};

int main ()
{
  int myints[]= {10,60,50,20};

  std::priority_queue<int> first;
  std::priority_queue<int> second (myints,myints+4);
  std::priority_queue<int, std::vector<int>, std::greater<int> >
                            third (myints,myints+4);
  // using mycomparison:
  typedef std::priority_queue<int,std::vector<int>,mycomparison> mypq_type;

  mypq_type fourth;                       // less-than comparison
  mypq_type fifth (mycomparison(true));   // greater-than comparison

  return 0;
}
The example does not produce any output, but it constructs different priority_queue objects:
- First is empty.
- Second contains the four ints defined for myints, with 60 (the highest) at its top.
- Third has the same four ints, but because it uses greater instead of the default (which is less), it has 10 as its top element.
- Fourth and fifth are very similar to first: they are both empty, except that these use mycomparison for comparisons, which is a special stateful comparison function that behaves differently depending on a flag set on construction.

Complexity

One container construction, and one call to make_heap, plus linear in the number of elements in the range [first,last) (if specified).

Iterator validity

Moving constructors may invalidate all iterators, pointers and references related to their moved argument.

Data races

All copied elements are accessed.
The moving constructors may modify their rvalue reference argument.

Exception safety

Provides the same level of guarantees as the operation performed on the container.

See also

priority_queue::push
Insert element (public member function)