Standard C++ LibraryCopyright 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



privacy and legal statement