priority_queue

     Container Adaptor

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

Contents

• Synopsis
• Description
• Interface
• Constructors
• Allocator
• Member Functions
• Example
• Warning
• See Also

#include <queue>

template <class T,
          class Container = vector<T>,
          class Compare = less<Container::value_type>, 
          class Allocator = allocator>
class priority_queue;

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, list, and vector can be used.

template <class T,
          class Container = vector<T>,
          class Compare = less<typename Container::value_type>,
          class Allocator = allocator>
 class priority_queue {
public:
// typedefs
   typedef typename Container::value_type value_type;
   typedef typename Container::size_type size_type;
   typedef Allocator allocator_type;
//  Construct
   explicit priority_queue (const Compare& = Compare(),
                            const Allocator&=Allocator());
   template <class InputIterator>
     priority_queue (InputIterator first,
                     InputIterator last,
                     const Compare& = Compare(), 
                     const Allocator& = Allocator());
   allocator_type get_allocator() const;
   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 Allocator& alloc = Allocator());

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& alloc = Allocator());

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_type get_allocator () const;

Returns a copy of the allocator used by self for 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 <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>, allocator> 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>, allocator>
      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>,    
     allocator> 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

If your compiler does not support default template parameters, you must always provide a Container template parameter, a Compare template parameter, and an Allocator 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, allocator> var;

Containers, queue