priority_queue

Container Adaptor

• Summary
• Data Type and Member Function Indexes
• Synopsis
• Description
• Interface
• Constructors
• Allocator
• Member Functions
• Example
• Warning
• See Also

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

Member Functions

empty() get_allocator() pop() push() size() top()

#include <queue>

template <class T,
          class Container = vector<T>,
          class Compare = less<Container::value_type> >
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 and vector can be used.

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();
};

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_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> > 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

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;

Containers, queue

©Copyright 1996, Rogue Wave Software, Inc.