Container Adapter in C++
The container adapters are a part of the C++ standard library that gives us a way to modify or adapt existing container classes to suit specific needs or requirements. In this article, we will learn about container adapters in C++.
What is a Container Adapter in C++?
In C++, container adapters are specialized interfaces created on top of other sequential containers like deque
, vector
, or list
by limiting functionality in a pre-existing container and providing more specific functionalities. It is done so as to avoid defining a completely new interface for containers that can be built on top of the already existing containers.
The Standard Template Library (STL) has three main container adapters:
- Stack
- Queue
- Priority Queue
1. Stack in C++
The stack adapter follows the Last In, First Out (LIFO) principle, and the insertion and removal of elements can be done only from the top of the queue container.
The following are the key operations of the stack:
push(elm)
: Insert the element elm at the top.pop()
: Removes the top element.top()
: Returns a reference to the top element.empty()
: Checks whether the stack is empty.size()
: Returns the number of elements.
Example of Stack
The below example demonstrates the usage of key operations in stack adapter in C++.
C++
// C++ program to demonstrate the usage of key operations in // stack adapter in C++. #include <iostream> #include <stack> using namespace std; int main() { // Declaring an instance of the stack adapter with stack< int > myStack; // Push elements onto the stack myStack.push(10); myStack.push(20); myStack.push(30); // print size of stack cout << "Size of stack is: " << myStack.size() << endl; // Pop elements from the stack until it's empty cout << "Elements in a stack are: " ; while (!myStack.empty()) { // Display the top element cout << myStack.top() << " " ; // Remove the top element myStack.pop(); } return 0; } |
Size of stack is: 3 Elements in a stack are: 30 20 10
Time Complexity: O(n)
Auxilliary Space: O(1)
2. Queue in C++
The queue adapter follows the First In First Out (FIFO) principle, means the element are inserted at the back and removed from the front of the queue. It is by default implemented using deque container.
The following are the key operations of the queue:
push(elm)
: Inserts the element elm at the back.pop()
: Removes the front element.front()
: Access the front element.back()
: Access the last element.empty()
: Checks whether the queue is empty.size()
: Returns the number of elements in a queue.
Example of Queue
The below example demonstrates the usage of key operations in queue adapter in C++.
C++
// C++ program to demonstrate the usage of key operations in // queue adapter in C++. #include <iostream> #include <queue> using namespace std; int main() { // Create a queue of integers queue< int > myQueue; // Add elements to the queue myQueue.push(10); myQueue.push(20); myQueue.push(30); // Print the size of the queue cout << "Size of queue is: " << myQueue.size() << endl; // Print the elements in the queue cout << "Elements in a queue are: " ; while (!myQueue.empty()) { // Print the front element of the queue cout << myQueue.front() << " " ; // Remove the front element from the queue myQueue.pop(); } return 0; } |
Size of queue is: 3 Elements in a queue are: 10 20 30
Time Complexity: O(n)
Auxilliary Space: O(1)
3. Priority Queue in C++
The priority queue adapter does not follow any of the FIFO or LIFO principle, in this ordering of elements is done on the basis of priority (using max-heap) so the element with the highest is always present at the front. By default, it uses vector as underlying container.
The following are the key operations of priority queue:
push(elm)
: Inserts the element elm.pop()
: Removes the top element.top()
: Returns a reference to the top element.empty()
: Checks whether the priority queue is empty.size()
: Returns the number of elements.
Example of Priority Queue
The below example demonstrates the usage of key operations in priority queue adapter in C++.
C++
// C++ program to demonstrate the usage of key operations in // priority queue adapter in C++. #include <iostream> #include <queue> using namespace std; int main() { // Create a priority queue of integers (default is a // max-heap) priority_queue< int > myPriorityQueue; // Add elements to the priority queue myPriorityQueue.push(30); myPriorityQueue.push(10); myPriorityQueue.push(20); // Print the size of the priority queue cout << "Size of priority queue is: " << myPriorityQueue.size() << endl; // Print the elements in the priority queue cout << "Elements in a priority queue are: " ; while (!myPriorityQueue.empty()) { // Print the top (maximum) element of the priority // queue cout << myPriorityQueue.top() << " " ; // Remove the top element from the priority queue myPriorityQueue.pop(); } return 0; } |
Size of priority queue is: 3 Elements in a priority queue are: 30 20 10
Time Complexity: O(n log n)
Auxilliary Space: O(n)
Conclusion
In conclusion, container adapters in C++ offer a convenient way to tailor the functionality of the already existing containers to precise desires whether we are operating with stacks, queues, or priority queues, understanding the underlying container and the adapter’s interface is crucial.
Contact Us