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