The Standard Template Library priority _queue<T> class implements, by default, a max heap storing objects of type T. It contains the following member functions:

bool empty() const	Is the queue empty?
size_type size() const	The number of objects in the queue.
T const & top() const	The maximum element in the queue.
void push( T const &obj )	Push the argument obj onto the queue.
void pop()	Pop the top element from the queue.
void swap( priority_queue& other ) const	Swap the content of this queue and the other queue.

It also has an additional member function void emplace( Args&&... args ) which allows you to insert a new object into the priority queue by passing the arguments of the constructor, as opposed to passing the object itself. Essentially, it is equivalent to

	priority_queue<T> pq;

	// The following two are equivalent, only the
	// first does not create a new object that is
	// immediately discarded.
	pq.emplace( a, b, c );
	pq.emplace( T( a, b, c ) );

Changing the storage

The STL allows you to change the underlying data structure used to store the priority queue. By default, it uses the vector<T> class. You can specify an alternate class by passing a second argument to the template; however, any such class must implement the interface for a random access iterator.

Changing the order (min heaps)

By default, the priority queue allows you to use any type T so long as the member function operator< is defined. For example, if you look at the string_default.cpp source, you will see that the strings, when taken out of the priority queue, are taken out in reverse alphabetical order; after all, it is a max heap. The declaration of the local variable is

	priority_queue< std::string > greater_than_queue;

Normally, however, you would want to sort strings in alphabetical order. In this case, the STL defines a default class std::greater<T> which compares two objects using operator>. Take a look at string_alphabetical.cpp in the source directory.

In this case, the declaration of the class is:

        priority_queue< std::string,
                        vector< std::string >,
                        std::greater< std::string > > less_than_queue;

Incidentally, this the default declaration is equivalent to

        priority_queue< std::string,
                        vector< std::string >,
                        std::less< std::string > > greater_than_queue;

User-defined orders

Suppose, however, that you have records where you may want to sort based on specific fields in the record. For example, as a person of interest, you may be stored in a database according to the following record:

      class Record {
          private:
              std::string first_name;
              std::string last_name;
              int id_number;
              int user_id;
              // ...

          public:
              // ...
};

Suppose, for example, you want to sort based on last name and then on the first name, or perhaps you want to sort on the ID number. In this case, we cannot define just a singe operator< or operator>. Instead, the STL allows you to declare an additional comparison class. that allow us to compare objects in this class. This Compare class must have the output bool operator()( Record const &, Record const & ) which can therefore be called on any pair of records. The return value should return true if the first argument strictly precedes the other, and false otherwise.

For example, the record class in the example given has three nested classes that are friends:

• Record::Alphabetical_sort
• Record::ID_number_sort
• Record::User_id_sort

In the first case, we want the last names appearing near the front of the alphabetical order. Thus, as "Baker" > "Pertwee" ("Baker" comes first) in this order, then operator()( "Pertwee", "Baker" ) had better return true; and if the last names are identical, we should compare the first names. Thus, we get the implementation:

bool Record::Alphabetical_sort::operator() ( Record const &a, Record const &b ) {
	return ( a.last_name > b.last_name ) || (a.last_name == b.last_name && a.first_name > b.first_name );
}

The next two sort on the ID number and on the user ID, respectively:

bool Record::ID_number_sort::operator() ( Record const &a, Record const &b ) {
	return a.id_number > b.id_number;
}

bool Record::User_id_sort::operator() ( Record const &a, Record const &b ) {
	return a.user_id > b.user_id;
}

You can look at record.cpp (in the source directory) to see this example.