Containers adaptors are class templates that provide a specific interface for the use of standard sequence containers. Unlike normal sequence containers that allow any access to any element through indices or iterators, adaptors restrict the operations of adding, accessing, and removing data. This ensures that the collection strictly works as per a specific logical model of a stack or a queue without any modifications of elements in the middle of the collection. The C++ Standard Library has three container adaptors: stack, queue, and priority queue.
A stack follows Last-In, First-Out operation principle. The element that was last inserted to the stack will be the first element to be removed. Think of it like a pile of dishes: you can put a new dish on the top and remove only the topmost one. The stack template provides three member functions: one for inserting an element to the top, one for removing the topmost element, and one for accessing it without removing it.
#include <iostream>
#include <stack>
int main() {
std::stack<int> numbers;
// Push elements onto the stack
numbers.push(10);
numbers.push(20);
numbers.push(30);
std::cout << "Stack size: " << numbers.size() << "\n";
// Inspect and pop elements until the stack is empty
while (!numbers.empty()) {
std::cout << "Top element: " << numbers.top() << "\n";
numbers.pop(); // Removes the top element
}
return 0;
}A queue follows First-In, First-Out operation principle. The element that was first inserted to the queue will be the first element to be removed. This principle resembles a line of people waiting for a service: a person who arrives first gets his turn served first and others stand in a line behind him. Queues are used for such applications as task scheduling, network packets handling, or data buffering. The queue template provides four functions: one for inserting an element to the back, one for removing the element from the front, one for accessing the oldest element, and one for accessing the newest one.
These types are container adapters: they provide a restricted interface over another container. A stack allows access to the most recent element, a queue allows access to the oldest element, and a priority queue allows access to the highest-priority element according to the comparison rule. They do not provide any general iteration interface.
#include <iostream>
#include <queue>
#include <string>
int main() {
std::queue<std::string> print_jobs;
// Add items to the back of the queue
print_jobs.push("Document1.pdf");
print_jobs.push("Photo.png");
print_jobs.push("Report.docx");
std::cout << "Queue size: " << print_jobs.size() << "\n";
std::cout << "Next job: " << print_jobs.front() << "\n";
std::cout << "Last job in line: " << print_jobs.back() << "\n";
// Process jobs in order
while (!print_jobs.empty()) {
std::cout << "Printing: " << print_jobs.front() << "\n";
print_jobs.pop(); // Removes the front element
}
return 0;
}A priority queue is a variant of a queue when each element has a priority, and the element with the highest priority moves to the front of the collection. Regardless of the insertion order, the next element retrieved will be the largest one by default. Internally, the priority queue keeps elements in a binary heap structure, which allows finding and removing the largest element quickly. A priority queue is used for Dijkstra shortest path algorithm and event-driven simulations with event scheduling. The priority queue template has a member function for inspecting the highest-priority element instead of the function used by a queue template for inspecting its front.
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int> scores;
// Insert elements in arbitrary order
scores.push(45);
scores.push(99);
scores.push(12);
scores.push(78);
// The highest value is always at the top
while (!scores.empty()) {
std::cout << "Processing score: " << scores.top() << "\n";
scores.pop(); // Removes the highest element
}
return 0;
}The top of a default priority queue is the largest element according to its comparison rule. Using the opposite comparison rule creates a minimum-oriented queue. Removing from any adapter does not return the removed value; you should inspect the top or front before removing it. Access to an empty adapter is invalid and should be protected with an emptiness check.
By default, a priority queue sorts its elements in a descending order based on the less-than operator and places the largest element on the top. To reverse this behavior and make the smallest element stay on the top, you can customize the template parameters. The template has three parameters: the element type, the underlying container type, and a comparison function object. To make a minimum-oriented heap where the smallest element has the highest priority, you can provide the greater-than comparison function object from the standard library as the third parameter.
#include <iostream>
#include <queue>
int main() {
// A priority queue where the smallest number is at the top
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
min_heap.push(45);
min_heap.push(99);
min_heap.push(12);
min_heap.push(78);
while (!min_heap.empty()) {
std::cout << "Smallest element: " << min_heap.top() << "\n";
min_heap.pop();
}
return 0;
}As container adaptors are wrappers, they do not allocate or manage memory blocks themselves but pass all responsibilities for memory management to an underlying sequence container. By default, stack and queue use double-ended queue as an underlying container and priority queue uses dynamic array. You can override these defaults by providing a sequence container as a template parameter. For instance, if you need a stack that keeps its elements in a single block of memory to optimize cache locality, you can specify a dynamic array as the underlying container. However, the underlying container must implement required operations for the adaptor. A stack requires operations for accessing, adding, and removing elements at the back, and a queue requires operations for accessing both ends, adding elements at the back, and removing elements from the front. This is why you cannot use a dynamic array as the underlying container for a queue as it does not have an ability to remove an element from the front.
The critical restriction of all three container adaptors is that they do not support iterators. There are no functions for obtaining the beginning or end of the collection, and you cannot use range-based loops for traversing their elements. This design is intended, as otherwise any access to elements in the middle of a stack or queue violates its strict Last-In, First-Out or First-In, First-Out access contract. If you need to access all elements of a collection without destroying it, you have to use standard sequence container, and not adapter over it.
Exercise: std::stack, std::queue, and std::priority_queueStarter code, hints and solutionOpenClose
Practice: std::stack, std::queue, and std::priority_queue
Work through the mission, reveal hints only when needed, and compare your result with the model solution.
Your challenge
Push Notes.txt after the existing print jobs. Predict the size, front, back, and final processing order.
Mission checklist
- Run the starter as a baseline, then predict the change requested in Your challenge.
- Make that change in your editor; use the lesson-specific hints if you need help.
- Compile and run your answer, then compare with the worked solution and explain the result.
Starter program
This is the working baseline, not the completed answer. Compile as C++20, then make the change described above.
#include <iostream>
#include <queue>
#include <string>
int main() {
std::queue<std::string> print_jobs;
// Add items to the back of the queue
print_jobs.push("Document1.pdf");
print_jobs.push("Photo.png");
print_jobs.push("Report.docx");
std::cout << "Queue size: " << print_jobs.size() << "\n";
std::cout << "Next job: " << print_jobs.front() << "\n";
std::cout << "Last job in line: " << print_jobs.back() << "\n";
// Process jobs in order
while (!print_jobs.empty()) {
std::cout << "Printing: " << print_jobs.front() << "\n";
print_jobs.pop(); // Removes the front element
}
return 0;
}Hints
This particular starter uses a queue: the first pushed print job is the first removed. front and back observe different ends without removing either item.
Push one more filename after the existing jobs. The first job remains at front, the new job becomes back, and pop still removes from the front.
Worked solution
Notes.txt is pushed after the three original print jobs. Queue size is now 4, Document1.pdf is still first, and Notes.txt is last and processed last.
#include <iostream>
#include <queue>
#include <string>
int main() {
std::queue<std::string> print_jobs;
// Add items to the back of the queue
print_jobs.push("Document1.pdf");
print_jobs.push("Photo.png");
print_jobs.push("Report.docx");
print_jobs.push("Notes.txt");
std::cout << "Queue size: " << print_jobs.size() << "\n";
std::cout << "Next job: " << print_jobs.front() << "\n";
std::cout << "Last job in line: " << print_jobs.back() << "\n";
// Process jobs in order
while (!print_jobs.empty()) {
std::cout << "Printing: " << print_jobs.front() << "\n";
print_jobs.pop(); // Removes the front element
}
return 0;
}
Example output
Queue size: 4
Next job: Document1.pdf
Last job in line: Notes.txt
Printing: Document1.pdf
Printing: Photo.png
Printing: Report.docx
Printing: Notes.txt
0 comments
No comments yet. Be the first.