Container Adaptors

The containers that we've seen until now are built from scratch. In this section, we'll look at the containers that are built on top of other containers. There are multiple reasons to provide a wrapper over existing containers, such as providing more semantic meaning to the code, restricting someone from accidentally using unintended functions just because they are available, and to provide specific interfaces.

One such specific use case is the stack data structure. The stack follows the LIFO (Last In First Out) structure for accessing and processing data. In terms of functions, it can insert and delete only at one end of the container and can't update or even access any element except at the mutating end. This end is called the top of the stack. We can easily use any other container, such as a vector or deque too, since it can meet these requirements by default. However, there are some fundamental problems in doing that.

The following example shows two implementations of the stack:

std::deque<int> stk;

stk.push_back(1);  // Pushes 1 on the stack = {1}

stk.push_back(2);  // Pushes 2 on the stack = {1, 2}

stk.pop_back();    // Pops the top element off the stack = {1}

stk.push_front(0); // This operation should not be allowed for a stack

std::stack<int> stk;

stk.push(1);       // Pushes 1 on the stack = {1}

stk.push(2);       // Pushes 2 on the stack = {1, 2}

stk.pop();         // Pops the top element off the stack = {1}

stk.push_front(0); // Compilation error

As we can see in this example, the first block of the stack using deque provides a semantic meaning only by the name of the variable. The functions operating on the data still don't force the programmer to add code that shouldn't be allowed, such as push_front. Also, the push_back and pop_back functions expose unnecessary details, which should be known by default since it is a stack.

In comparison to this, if we look at the second version, it looks much more accurate in indicating what it does. And, most importantly, it doesn't allow anyone to do anything that was unintended, even accidentally.

The second version of the stack is nothing but a wrapper over the previous container, deque, by providing a nice and restricted interface to the user. This is called a container adaptor. There are three container adaptors provided by C++: std::stack, std::queue, and std::priority_queue. Let's now take a brief look at each of them.

std::stack

As explained earlier, adaptors simply reuse other containers, such as deque, vector, or any other container for that matter. std::stack, by default, adapts std::deque as its underlying container. It provides an interface that is only relevant to the stack – empty, size, top, push, pop, and emplace. Here, push simply calls the push_back function for the underlying container, and pop simply calls the pop_back function. top calls the back function from the underlying container to get the last element, which is the top of the stack. Thus, it restricts the user operations to LIFO since it only allows us to update values at one end of the underlying container.

Here, we are using deque as an underlying container, and not a vector. The reason behind it is that deque doesn't require you to shift all the elements during reallocation, unlike vector. Hence, it is more efficient to use deque compared to vector. However, if, for some scenario, any other container is more likely to give better performance, stack gives us the facility to provide a container as a template parameter. So, we can build a stack using a vector or list as well, as shown here:

std::stack<int, std::vector<int>> stk;

std::stack<int, std::list<int>> stk;

All the operations of a stack have a time complexity of O(1). There is usually no overhead of forwarding the call to the underlying container as everything can be inlined by the compiler with optimizations.

std::queue

Just like std::stack, we have another container adapter to deal with the frequent scenario of FIFO (First In First Out) in many applications, and this structure is provided by an adaptor called std::queue. It almost has the same set of functions as a stack, but the meaning and behavior are different in order to follow FIFO instead of LIFO. For std::queue, push means push_back, just like a stack, but pop is pop_front. Instead of pop, since queue should be exposing both the ends for reading, it has front and back functions.

Here's a small example of the usage of std::queue:

std::queue<int> q;

q.push(1);  // queue becomes {1}

q.push(2);  // queue becomes {1, 2}

q.push(3);  // queue becomes {1, 2, 3}

q.pop();    // queue becomes {2, 3}

q.push(4);  // queue becomes {2, 3, 4}

As shown in this example, first, we are inserting 1, 2, and 3 in that order. After that, we are popping one element off the queue. Since 1 was pushed first, it is removed from the queue first. Then, the next push inserts 4 at the back of the queue.

std::queue also uses std::deque as an underlying container for the same reason as stack, and it also has a time complexity of O(1) for all the methods shown here.

std::priority_queue

Priority queue provides a very useful structure called heap via its interface. A heap data structure is known for fast access to the minimum (or maximum) element from the container. Getting the min/max element is an operation with a time complexity of O(1). Insertion has O(log n) time complexity, while deletion can only be performed for the min/max element, which always stays on the top.

An important thing to note here is that we can only have either the min or max function made available quickly, and not both of them. This is decided by the comparator provided to the container. Unlike stack and queue, a priority queue is based on a vector by default, but we can change it if required. Also, by default, the comparator is std::less. Since this is a heap, the resultant container is a max heap. This means that the maximum element will be on top by default.

Here, since insertion needs to make sure that we can access the top element (min or max depending on the comparator) instantly, it is not simply forwarding the call to the underlying container. Instead, it is implementing the algorithm for heapifying the data by bubbling it up to the top as required using the comparator. This operation takes a time duration that is logarithmic in proportion to the size of the container, hence the time complexity of O(log n). The invariant also needs to be maintained while initializing it with multiple elements. Here, however, the priority_queue constructor does not simply call the insertion function for each element; instead, it applies different heapification algorithms to do it faster in O(n).

Iterators for Adaptors

All the adaptors that we have seen so far expose functionality only as required to fulfill its semantic meaning. Logically thinking, traversing through stack, queue, and priority queue doesn't make sense. At any point, we should only be able to see the front element. Hence, STL doesn't provide iterators for that.