Standard C++	Library
 		 Copyright 1996, Rogue Wave Software, Inc.

 NAME

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

 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

   Containers, queue

 STANDARDS CONFORMANCE
   ANSI X3J16/ISO WG21 Joint C++	Committee