An Introduction to Container Adapters in C++

Overview

The C++ Standard Library offers a host of implementations on common data structures and algorithms. The collection of container classes provides a set of data structure to store a list of objects as its element. The container classes are templatized to make it generic in the sense that it can store objects of any data type.

Types of Containers

According to the style of functioning, these container classes can be categorized into A Sequential container, which represents a linear data structure such as arrays, vectors, and linked lists. Associative containers represent a nonlinear data structure with the capability to quickly locate elements stored in the container. These containers can store values as key-value pairs. The keys are immutable and forms the basis for quick search of container elements. Examples of associative containers are map, multimap, set, and so forth..

The Sequential and Associative container classes form the group called first-class containers. But, there is another type of container class in the Standard Library, called the container adapter.

Container Adapter

The Sequential and Associative containers would have been adequate if container classes had to address the simple problem of efficiently storing and retrieving objects as needed at runtime generically. But, understand that we also need another type of container which can not only store elements efficiently but also put some constraints in the storage and retrieval process of the elements. These types of containers are called container adapters. The C++ Standard Library implements class templates such as stack, queue, and priority_queue as a container that puts constraints on the process of storage and retrieval of elements.

The typical characteristic of a container adapter is that it is not a first-class, container-like sequence and associative containers, which means that it does not provide actual data structure implementation where elements are stored simply for storage and retrieval. It does not support iterators. Adapter container classes provide functions like push and pop that insert and retrieve an element into the storage, respectively.

The stack Adapter

The class called stack is an implementation of the stack data structure where insertion and retrieval of elements occurs according to the LIFO (last-in-first-out) manner. Imagine the container to be a stack of elements where the first element inserted is at the bottom and the last element inserted is at the top of the stack. The bottom element is always retrieved first from the stack. A stack can be implemented with a sequence container such as vector, list, or deque. But, a stack is implemented as deque in C++ by default. The primary operations as push to insert element at the top of the stack and pop to remove from the top element. There is another method, called top, which simply gets the reference of the top element in the stack. The operation empty determines whether or not the stack is empty and size gets the number of elements in the stack.

A Quick Example

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main()
{

   stack<string> weekdays;
   weekdays.push("Saturday");
   weekdays.push("Friday");
   weekdays.push("Thursday");
   weekdays.push("Wednesday");
   weekdays.push("Tuesday");
   weekdays.push("Monday");
   weekdays.push("Sunday");

   cout<<"Size of the stack: "<<weekdays.size()<<endl;

   while(!weekdays.empty()) {
      cout<<weekdays.top()<<endl;
      weekdays.pop();
   }

   return 0;
}

The queue Adapter

The storage and retrieval constraint of the queue class is similar to people standing in a queue for, say, buying a movie ticket. It is an implementation of the FIFO (first-in-first-out) data structure where the element that comes first is the first one that is removed from the queue. It enables insertion of elements at the back of the storage and removal from the front. A queue can store elements in the sequence container list or deque data structure. The primary operations are push to insert elements at the back of the queue and pop to remove elements from the front of the queue. Unlike stack, the queue uses methods like front to get a reference of the first elements and back to get a reference of the last element of the queue, respectively. The method empty determines whether or not the queue is empty, and size gets the number of elements in the queue.

A Quick Example

#include <iostream>
#include <queue>
#include <string>

using namespace std;

int main()
{

   queue<string> weekdays;

   weekdays.push("Saturday");
   weekdays.push("Friday");
   weekdays.push("Thursday");
   weekdays.push("Wednesday");
   weekdays.push("Tuesday");
   weekdays.push("Monday");
   weekdays.push("Sunday");

   cout<<"Size of the stack: "<<weekdays.size()<<endl;

   while(!weekdays.empty()) {
      cout<<weekdays.front()<<endl;
      weekdays.pop();
   }

   return 0;
}

The priority_queue Adapter

The priority_queue adapter class is a little bit different in the sense that it enables the insertion of elements in sorted order into the data structure and removal of elements occurs from the front of the waiting line. The priority_queue uses a vector as its underlying data structure by default. As the name suggests, the elements are inserted according to the priority order. For example, the highest priority, say, the largest number will be the first element to be removed from the queue. The ordering of elements is done using a heap-sort algorithm where typically the largest element is at the top of the waiting line. A custom object also can be stored in the queue with the customized comparator function object because, by default, it uses one for all comparison and ordering of elements.

The primary operations are push to insert elements at the appropriate location on the basis of priority order, and pop to remove the highest priority elements from the priority_queue. The methods like top are used to get a reference of the top. The method empty determines whether or not the queue is empty and size gets the number of elements in the queue.

A Quick Example

#include <iostream>
#include <queue>
#include <string>

using namespace std;

int main()
{

   priority_queue<int> nums;

   nums.push(9);
   nums.push(2);
   nums.push(7);
   nums.push(1);
   nums.push(4);

   cout<<"Size of the stack: "<<nums.size()<<endl;

   while(!nums.empty()) {
      cout<<nums.top()<<endl;
      nums.pop();
   }

   return 0;
}

Conclusion

Unlike sequence and adapter containers, container adapters—such as stack, queue, and priority_queue—apply some sort of constraints in the storage and retrieval process of elements in the underlying data structure. They are not like the first-class containers, although the underlying data structure used by them are from first-class containers only. Container adapter classes are typically convenient classes provided by the library for everyday programming. One can always ignore them and reinvent the wheel, but experience says it is better to adapt one that already exists unless, of course, there is a very good reason to start from scratch.

Manoj Debnath
Manoj Debnath
A teacher(Professor), actively involved in publishing, research and programming for almost two decades. Authored several articles for reputed sites like CodeGuru, Developer, DevX, Database Journal etc. Some of his research interest lies in the area of programming languages, database, compiler, web/enterprise development etc.

More by Author

Get the Free Newsletter!

Subscribe to Developer Insider for top news, trends & analysis

Must Read