Container Adaptors
Explore the role and implementation of container adaptors in C++ such as stack, queue, and priority_queue. Understand how priority queues enable efficient partial sorting and when to use them over other data structures depending on iterator types and sorting needs.
We'll cover the following...
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 ...