priority_queue

Container Adaptor

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

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

Member Functions

empty() 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 that 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 gives 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 Container container_type;

//  Construct
   explicit priority_queue (const Compare& = Compare(),
                            const Container& = Container());
   template <class InputIterator>
     priority_queue (InputIterator first,
                     InputIterator last,
                     const Compare& = Compare(), 
                     const Container& = Container());
   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, and the allocator Allocator() 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 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 <queue>
 #include <deque>
 #include <vector>
 #include <string>
 #include <iostream>
 using namespace std;

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

Program 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 include 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;

If your compiler does not support namespaces, then you do not need the using declaration for std.

Containers, queue