Personal tools
priority_queue
Click on the banner to return to the class reference home page.
priority_queue
Container Adaptor
- Summary
- Data Type and Member Function Indexes
- Synopsis
- Description
- Interface
- Constructors
- Allocator
- Member Functions
- Example
- Warning
- See Also
Summary
A container adapter which behaves like a priority queue. Items are popped from the queue are in order with respect to a "priority."
Data Type and Member Function Indexes
(exclusive of constructors and destructors)
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 which 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 provides 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 typename allocator_type allocator_type; // Construct explicit priority_queue (const Compare& = Compare(), const allocator_type&=allocator_type()); template <class InputIterator> priority_queue (InputIterator first, InputIterator last, const Compare& = Compare(), const allocator_type& = allocator_type()); allocator_type get_allocator() const; 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 allocator_type& alloc = allocator_type());
Default constructor. Constructs a priority queue that uses Container for its underlying implementation, x as its standard for determining priority, and the allocator alloc 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 will use x for determining the priority, and the allocator alloc for all storage management.
Allocator
allocator_type get_allocator () const;
Returns a copy of the allocator used by self for 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.h> 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; } 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
Warning
If your compiler does not support default template parameters, you must always provide 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;
See Also
©Copyright 1996, Rogue Wave Software, Inc.