Container Adaptors

Container adaptors in C++

There are three container adaptors in the standard library: std::stack, std::queue, and std::priority_queue. Container adaptors are quite different from sequence containers and associative containers because they represent abstract data types that can be implemented by the underlying sequence container. For example, the stack, which is a last in, first out (LIFO) data structure supporting push and pop on the top of the stack, can be implemented by using a vector, list, deque, or any other custom sequence container that supports back(), push_back(), and pop_back(). The same goes for queue, which is a first in, first out (FIFO) data structure, and priortiy_queue.

We will focus on std::priority_queue, which is a pretty useful data structure that is easy to forget.

Priority queues

A priority queue offers a constant-time lookup of the element with the highest priority. The priority is defined using the less than operator of the elements. Insert and delete both runs in logarithmic time. A priority queue is a partially ordered data structure, and it might not be obvious when to use one instead of a completely sorted data structure, for example, a tree or a sorted vector. However, in some cases, a priority queue can offer us the functionality we need, and for a lower cost than a completely sorted container.

The standard library already provides a partial sort algorithm, so we don't need to write our own. But let's look at how we can implement a partial sort algorithm using a priority queue. Suppose that we are writing a program for searching documents given a query. The matching documents (search hits) should be ordered by rank, and we are only interested in finding the first 10 search hits with the highest rank.

A document is represented by the following class: