Standard C++ Library
Copyright 1998, Rogue Wave Software, Inc.

 

NAME

 
priority_queue
 
 - A container adapter that behaves like a priority queue. Items popped from the queue are in order with respect to a "priority."
 
 
 

SYNOPSIS

 
 

#include <queue>
template <class T,

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

class priority_queue;
 
 
 

DESCRIPTION

 
 
priority_queue is a container adaptor that allows a container to act as a priority queue. This means that the item with the highest priority, as determined by either the default comparison operator (operator <) or the comparison Compare, is brought to the front of the queue whenever anything is pushed onto or popped off the queue. 
 
priority_queue adapts any container that gives front(), push_back(), and pop_back(). In particular, deque and vector can be used. 
 
 
 

INTERFACE

 
 
template <class T, class Container = vector<T>,

class Compare = less<typename

Container::value_type> >

class priority_queue {
public:
 
// typedefs

typedef typename Container::value_type value_type;
typedef typename Container::size_type size_type;
typedef Container container_type;

 
//  Construct

explicit priority_queue (const Compare& = Compare(),

const Container& = Container());

template <class InputIterator>

priority_queue (InputIterator first,

InputIterator last,
const Compare& = Compare(),
const Container& = Container());

bool empty () const;
size_type size () const;
const value_type& top () const;
void push (const value_type&);
void pop();

};
 
 
 

CONSTRUCTORS

 
 
 
explicit priority_queue (const Compare& x = Compare(),

const Container& = Container());

 
 
Constructs a priority queue that uses Container for its underlying implementation, x as its standard for determining priority, and the allocator Allocator() for all storage management. 
 

 
 

template <class InputIterator>
priority_queue (InputIterator first, InputIterator last,

const Compare& x = Compare(),
const allocator_type& alloc =
allocator_type());

 
 
Constructs a new priority queue and places into it every entity in the range [first, last). The priority_queue uses x for determining the priority, and the allocator alloc for all storage management. 
 

 
 
 

MEMBER FUNCTIONS

 
 
 

bool
empty () const;

 
 
Returns true if the priority_queue is empty, false otherwise. 
 

 
 
void
pop();

 
 
Removes the item with the highest priority from the queue.
 

 
 
void
push (const value_type& x);

 
 
Adds x to the queue. 
 

 
 
size_type
size () const;

 
 
Returns the number of elements in the priority_queue.
 

 
 
const value_type&
top () const;

 
 
Returns a constant reference to the element in the queue with the highest priority.
 

 
 
 

EXAMPLE

 
 
 
//
// p_queue.cpp
//

#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <iostream>

using namespace std;
 
int main(void)

{

// Make a priority queue of int using a vector container
priority_queue<int, vector<int>, less<int> > pq;

 

// Push a couple of values

pq.push(1);
pq.push(2);

 

// Pop a couple of values and examine the ends

cout << pq.top() << endl;
pq.pop();
cout << pq.top() << endl;
pq.pop();

 

// Make a priority queue of strings using
// a deque container
priority_queue<string, deque<string>, less<string> >

pqs;

 

// Push on a few strings then pop them back off

int i;
for (i = 0; i < 10; i++)

{

pqs.push(string(i+1,’a’));
cout << pqs.top() << endl;

}

for (i = 0; i < 10; i++)

{

cout << pqs.top() << endl;
pqs.pop();

}

 

// Make a priority queue of strings using a deque
// container, and greater as the compare operation
priority_queue<string,deque<string>, greater<string> >

pgqs;

 

// Push on a few strings then pop them back off

for (i = 0; i < 10; i++)

{

pgqs.push(string(i+1,’a’));
cout << pgqs.top() << endl;

}

 

for (i = 0; i < 10; i++)

{

cout << pgqs.top() << endl;
pgqs.pop();

}

 

return 0;

}
 

Program Output
 
 
 

 
2
1
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaa
aaaaaaaaa
aaaaaaaaaa
aaaaaaaaa
aaaaaaaa
aaaaaaa
aaaaaa
aaaaa
aaaa
aaa
aa
a
a
a
a
a
a
a
a
a
a
a
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaa
aaaaaaaaa
aaaaaaaaaa
 
 
 

WARNINGS

 
 
If your compiler does not support default template parameters, you must always include a Container template parameter and a Compare template parameter when declaring an instance of priority_queue. For example, you would not be able to write:
 
 
priority_queue<int> var;
 
Instead, you would have to write:
 
 
priority_queue<int, vector<int>,
  less<typename vector<int>::value_type> > var;
 
If your compiler does not support namespaces, then you do not need the using declaration for std. 
 
 
 

SEE ALSO

 
 
Containers, queue
 

Rogue Wave Software  —  Last change: 02 Apr 1998