Module: Standard C++ Library Library: Containers
Does not inherit
A container adapter that behaves like a priority queue. Items popped from the queue are in order with respect to a priority.
#include <queue>
namespace std {
template <class T,
class Container = vector<T>,
class Compare = less<Container::value_type> >
class priority_queue;
}
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 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 supports front(), push_back(), pop_back(), and has a random access iterator. In particular, deque and vector can be used. To instantiate a priority_queue, a comparison function object must be supplied.
namespace std {
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 start,
InputIterator finish,
const Compare& = Compare(),
const Container& = Container());
// Accessors
bool empty() const;
size_type size ) const;
const value_type& top() const;
void push(const value_type&);
void pop();
};
}
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.
template <class InputIterator>
priority_queue(InputIterator start, InputIterator finish,
const Compare& x = Compare(),
const allocator_type& alloc =
allocator_type());
Constructs a new priority queue and places into it every entity in the range [start, finish). The priority queue uses x for determining the priority, and the allocator alloc for all storage management.
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.
//
// p_queue.cpp
//
#include <deque> // for deque
#include <iostream> // for cout, endl
#include <queue> // for priority_queue
#include <string> // for string
#include <vector> // for vector
int main ()
{
// Make a priority queue of int using a vector container.
std::priority_queue<int,
std::vector<int,
std::allocator<int> >,
std::less<int> > pq;
// Push a couple of values.
pq.push (1);
pq.push (2);
// Pop a couple of values and examine the ends.
std::cout << pq.top () << std::endl;
pq.pop ();
std::cout << pq.top () << std::endl;
pq.pop ();
// Make a priority queue of strings.
std::priority_queue<std::string,
std::deque<std::string,
std::allocator<std::string> >,
std::less<std::string> > pqs;
// Push on a few strings then pop them back off.
for (int i = 0; i < 10; i++) {
pqs.push (std::string (i + 1, 'a'));
std::cout << pqs.top () << std::endl;
}
for (int j = 0; j < 10; j++) {
std::cout << pqs.top () << std::endl;
pqs.pop ();
}
// Make a priority queue of strings using greater.
std::priority_queue<std::string,
std::deque<std::string,
std::allocator<std::string> >,
std::greater<std::string> > pgqs;
// Push on a few strings then pop them back off.
for (int k = 0; k < 10; k++) {
pgqs.push (std::string (k + 1, 'a'));
std::cout << pgqs.top () << std::endl;
}
for (int m = 0; m < 10; m++) {
std::cout << pgqs.top () << std::endl;
pgqs.pop ();
}
return 0;
}
Program Output:
2 1 a aa aaa aaaa aaaaa aaaaaa aaaaaaa aaaaaaaa aaaaaaaaa aaaaaaaaaa 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
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 must write:
priority_queue<int, vector<int>, less<typename vector<int>::value_type> > var;
instead of:
priority_queue<int> var;
ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 23.2.3.2
Copyright (c) 1994-2006 Rogue Wave Software, a Quovadx Division.
Licensed under the Apache License, Version 2.0.
Contact Rogue Wave about documentation or support issues. You can also seek help from other developers through the Apache stdcxx community (see below).