A std::vector is the right answer most of the time, but a std::stack, a std::queue or a std::deque beats it when your access pattern is not "index from the front". The stack and the queue are adaptors, so they are not containers of their own but wrappers around a container that restrict what you can do with it. That restriction is the feature, because it makes the intended use impossible to misuse.
The previous lesson in this module covered "Which Map and Set Variants Fit Which Job?", and the next lesson in this module is about "How Do Iterators Walk Containers?".
stack is last in, first out
A std::stack is the adaptor for a LIFO structure. You push onto the top and you pop from the top. Nothing else is allowed.
#include <iostream>
#include <stack>
#include <string>
int main() {
std::stack<std::string> parcels;
parcels.push("p-001");
parcels.push("p-002");
parcels.push("p-003");
std::cout << "top: " << parcels.top() << '\n';
while (!parcels.empty()) {
std::cout << "processing " << parcels.top() << '\n';
parcels.pop();
}
return 0;
}The output shows the last parcel that was pushed coming out first.
top: p-003
processing p-003
processing p-002
processing p-001And notice what the adaptor does not let you do. There is no square brackets, there is no begin() and there is no erase(). You cannot reach into the middle of a stack, and that is the whole point.
queue is first in, first out
A std::queue is the adaptor for a FIFO structure. You push at the back and you pop from the front.
#include <iostream>
#include <queue>
#include <string>
int main() {
std::queue<std::string> parcels;
parcels.push("p-001");
parcels.push("p-002");
parcels.push("p-003");
while (!parcels.empty()) {
std::cout << "processing " << parcels.front() << '\n';
parcels.pop();
}
return 0;
}The output shows the first parcel that was pushed coming out first.
processing p-001
processing p-002
processing p-003And a queue is the natural structure for the work that has to be handled in the order that it arrived. The print jobs, the incoming requests and the breadth-first search all work this way.
deque is a double-ended queue
A std::deque is a real container and not an adaptor, and it allows the insertion and the removal at both ends as well as the random access in the middle.
#include <iostream>
#include <deque>
#include <string>
int main() {
std::deque<std::string> parcels;
parcels.push_back("p-003");
parcels.push_front("p-001");
parcels.push_back("p-004");
parcels.push_front("p-000");
for (const std::string& parcel : parcels) {
std::cout << parcel << ' ';
}
std::cout << '\n';
std::cout << "front: " << parcels.front() << '\n';
std::cout << "back: " << parcels.back() << '\n';
return 0;
}The output shows the ends being used independently.
p-000 p-001 p-003 p-004
front: p-000
back: p-004And a deque is the structure behind a sliding window, a work-stealing queue and a scheduler that may add the work at either end.
Comparing the four
the operation the vector the deque the stack the queue
------------------------ ---------- --------- --------- ---------
push at the back push_back push_back push push
push at the front slow push_front not there not there
remove from the back pop_back pop_back pop not there
remove from the front slow pop_front not there pop
read the front front front top front
read the back back back top back
index with [i] yes yes no no
When a vector is still the right choice
A vector is faster than a deque for most of the workloads, because its elements are contiguous in the memory while the elements of a deque are in blocks. If you do not actually need to add or to remove at the front, then use a vector. The same applies to a stack and to a queue. If your code only ever pushes and pops at one end, then a std::vector with back() and pop_back() is simpler and it is faster.
And the adaptors earn their place when the discipline matters, which is when a reviewer wants to see that the code cannot reach into the middle of the collection.
The adaptors are built on other containers
A std::stack is a template over an underlying container, and by default that container is a std::deque. You can choose a different one.
#include <iostream>
#include <stack>
#include <string>
#include <vector>
int main() {
std::stack<int, std::vector<int>> parcels;
parcels.push(1);
parcels.push(2);
parcels.push(3);
std::cout << "top: " << parcels.top() << '\n';
std::cout << "size: " << parcels.size() << '\n';
// The underlying container is still reachable through the adaptor.
std::stack<int, std::vector<int>> copy = parcels;
std::cout << "copy size: " << copy.size() << '\n';
return 0;
}The output shows the stack working in the same way with a vector underneath.
top: 3
size: 3
copy size: 3A worked example: a work queue
Here is a queue used for something real, processing the parcel records in order while it collects the results.
#include <iostream>
#include <queue>
#include <string>
struct Parcel {
std::string id;
int weight;
};
int main() {
std::queue<Parcel> incoming;
incoming.push({"p-001", 4});
incoming.push({"p-002", 30});
incoming.push({"p-003", 12});
int total = 0;
int heaviest = 0;
while (!incoming.empty()) {
Parcel parcel = incoming.front();
incoming.pop();
std::cout << "processing " << parcel.id << '\n';
total += parcel.weight;
if (parcel.weight > heaviest) {
heaviest = parcel.weight;
}
}
std::cout << "total weight: " << total << '\n';
std::cout << "heaviest: " << heaviest << '\n';
return 0;
}The output shows the parcels being processed in the order that they arrived.
processing p-001
processing p-002
processing p-003
total weight: 46
heaviest: 30Quick reference
- The
std::stackis LIFO, with the push, the top and the pop. - The
std::queueis FIFO, with the push, the front and the pop. - The
std::dequeallows the insertion and the removal at both ends and it has the random access. - The stack and the queue are adaptors that restrict the interface of an underlying container.
- A vector is faster than a deque for everything except the front insertion and the front removal.
- Use a queue for the work that has to be handled in the order of the arrival.
Try it yourself: push ten parcel records into a std::queue and process them, printing them as they come out. Then convert the queue to a std::stack and repeat, and check that the order reverses. Next, use a std::deque to add the records at both ends and to remove from the front, and compare the behaviour with the vector.