priority_queue

A priority_queue is an adapter that can use any sequential container with a random access iterator to maintain a sorted collection of items. Using priority_queue , you can specify a comparator to sort the items. This section provides an overview of priority_queue .

Iterator Type

Because adapters do not support iteration, a priority_queue has no associated iterator.

Implementation

A priority_queue is implemented as a class comprised of inline functions converting push() and pop() messages into calls to push_back() , pop_back() , and heap algorithms. The only sequential containers with random access iterators supporting these functions are vector and deque . Of these two containers, deque generally yields better performance.

Common Uses

A priority_queue is useful for implementing sorted collections.

Interface

A priority_queue does not introduce any new functions, but an additional parameter is required if you are using an older compiler and its implementation of pop() operates differently from those of stack and queue .

The following example uses a priority_queue to order a set of integers into descending order.

Example <ospace/osstd/examples/pqueue1.cpp>


  #include <iostream>
#include <vector>
#include <functional>
#include <queue>

void
main()
  {
  priority_queue< int, vector< int >, less< int > > q;
  q.push( 42 );
  q.push( 101 );
  q.push( 69 );
  while ( !q.empty() )
    {
    cout << q.top() << "\n";
    q.pop();
    }
  }

101
69
42

The following example uses a priority_queue to sort a set of strings in ascending order. It uses the greater_s comparator from Helper<ToolKit> to order the character strings.

Example <ospace/osstd/examples/pqueue2.cpp>


  #include <iostream>
#include <vector>
#include <queue>
#include <ospace/helper.h>

void
main()
  {
  priority_queue< char*, vector< char* >, greater_s > q;
  q.push( (char*) "cat" );
  q.push( (char*) "dog" );
  q.push( (char*) "ape" );
  while ( !q.empty() )
    {
    cout << q.top() << "\n";
    q.pop();
    }
  }

ape
cat
dog