C++ / STANDARD CONTAINERS
Stacks, queues, and priority queues as adaptors
Use std::stack, std::queue, and std::priority_queue as thin wrappers over a real container, and control their comparator and underlying storage.
What you will learn
- Read with top() or front(), remove with pop(); pop() never returns the element.
- Swap the storage with the second template argument: std::stack<int, std::vector<int>>.
- Make a min-heap with std::priority_queue<int, std::vector<int>, std::greater<int>>.
- Write a heap comparator whose true means the first argument is served later.
Understanding Stacks, queues, and priority queues as adaptors
A stack, a queue, and a priority queue are not containers; each one holds a container as a member and exposes only the handful of operations its discipline allows. std::stack<T> and std::queue<T> default to std::deque<T> because a deque adds and removes at both ends without reallocating or invalidating references to the other elements, while std::priority_queue<T> defaults to std::vector<T> because the heap algorithms underneath it need random access. The subtraction is the point: there is no begin(), no end(), no operator[], so nothing in your code can reach into the middle and break the invariant the adaptor exists to enforce.
Every adaptor splits reading from removing. top() on a stack or priority queue and front()/back() on a queue hand back a reference; pop() returns void. That split is there for exception safety: a pop() that returned the element by value would have to erase it and then copy or move it out to the caller, and if that copy threw, the element would already be gone with no way to recover it. Calling top() or pop() on an empty adaptor is undefined behaviour rather than an exception, so testing empty() first is not politeness, it is the only check you get.
std::priority_queue is a binary heap, and its comparator answers one question: does a have lower priority than b. With the default std::less<T> the element that no other element compares greater than sits at the top, so std::priority_queue<int> pops the largest first; passing std::greater<T> as the third template argument turns it into a min-heap. Only top() is ordered, because the underlying vector is heap-ordered and not sorted, and push and pop cost O(log n) while top() is O(1). Constructing from an iterator pair heapifies the whole range once in O(n), which beats n separate pushes.
<iostream>
<queue>
<stack>
<string>
int main() {
std::stack<std::string> undo; // LIFO, deque underneath
undo.push("type");
undo.push("bold");
undo.push("indent");
std::queue<std::string> jobs; // FIFO, deque underneath
jobs.push("resize");
jobs.push("compress");
jobs.push("upload");
std::priority_queue<int> best; // max-heap, vector underneath
for (int score : {41, 97, 63, 12}) best.push(score);
std::cout << "stack top " << undo.top() << ", size " << undo.size() << "\n";
undo.pop();
std::cout << "after pop " << undo.top() << "\n";
std::cout << "queue front " << jobs.front() << ", back " << jobs.back() << "\n";
jobs.pop();
std::cout << "after pop " << jobs.front() << "\n";
std::cout << "drain heap:";
while (!best.empty()) {
std::cout << ' ' << best.top();
best.pop();
}
std::cout << "\n";
}
A stack, queue, or priority queue is not new storage but a wrapper that hides an existing container's interface down to the operations its discipline permits.
Worked examples
Min-heap and O(n) heapify
Builds a smallest-first priority queue from an existing range without disturbing the source vector.
<functional>
<iostream>
<queue>
<vector>
int main() {
std::vector<int> data{5, 1, 9, 3, 7};
std::priority_queue<int, std::vector<int>, std::greater<int>>
mins(data.begin(), data.end());
std::cout << "smallest first:";
while (!mins.empty()) {
std::cout << ' ' << mins.top();
mins.pop();
}
std::cout << "\nsource untouched:";
for (int v : data) std::cout << ' ' << v;
std::cout << '\n';
}
Example explained
Line 1std::greater<int> as the third template argument flips the comparison so top() is the minimum, and it forces you to name the container type explicitly as the second argument.
Line 2The iterator-pair constructor copies the range into its own vector and then heapifies once in O(n), instead of five separate O(log n) pushes.
Line 3data still prints in its original order because the adaptor owns a copy, not a view of the vector.
Line 4The drain loop must call top() before pop(), since pop() gives back nothing.
Custom priority with a comparator type
Orders task objects by an urgency field, showing what a heap comparator's return value means.
<iostream>
<queue>
<string>
<utility>
<vector>
struct Task {
std::string name;
int urgency;
Task(std::string n, int u) : name(std::move(n)), urgency(u) {}
};
struct ByUrgency {
bool operator()(const Task& a, const Task& b) const {
return a.urgency < b.urgency; // a is less urgent, so it leaves later
}
};
int main() {
std::priority_queue<Task, std::vector<Task>, ByUrgency> q;
q.push({"log rotate", 1});
q.push({"page oncall", 9});
q.push({"send email", 4});
q.emplace("restart pod", 7);
while (!q.empty()) {
std::cout << q.top().urgency << ' ' << q.top().name << '\n';
q.pop();
}
}
Example explained
Line 1ByUrgency::operator() returns true when a should be served after b, which is why a plain < on urgency yields highest-urgency-first.
Line 2The comparator must be a const member function, because the heap compares elements through a const object.
Line 3emplace forwards its arguments straight to the Task constructor inside the vector, so no temporary Task is built and copied.
Line 4top() returns a const reference, so the element cannot be edited in place; two tasks with equal urgency come out in an unspecified relative order because heaps are not stable.
Choosing the storage, and living without iterators
Backs a stack with std::vector instead of the default deque and reverses a string by draining it.
<iostream>
<stack>
<string>
<vector>
int main() {
std::stack<char, std::vector<char>> s;
for (char c : std::string("stack")) s.push(c);
std::string reversed;
while (!s.empty()) {
reversed += s.top();
s.pop();
}
std::cout << reversed << '\n';
std::cout << "empty now: " << std::boolalpha << s.empty() << '\n';
}
Example explained
Line 1The second template argument accepts any container offering back(), push_back(), and pop_back(), so vector works and makes the stack contiguous.
Line 2A range-based for loop over s would not compile: adaptors publish no begin() or end(), so draining is the only way to visit the elements.
Line 3reversed grows in pop order, which is why the last character pushed appears first.
Line 4There is no clear() member; the loop above empties the stack, and s = {} would do it in one line.
Important notes
No adaptor has clear() or size-shrinking members, so empty one with c = {} or a pop loop; swap(c, other) also works.
You cannot lower or raise the priority of an element already inside a std::priority_queue, since top() is const; the usual fix is to push an updated copy and discard stale entries as they surface.
Common mistakes
Writing int x = s.pop(); which fails to compile because pop() returns void, then patching it by calling top() after pop() and silently reading the next element down, or reading past the end when the adaptor is now empty.
Assuming std::priority_queue<int> serves the smallest value first; a Dijkstra or scheduler loop then expands the worst candidate every iteration and produces wrong answers, because std::less puts the maximum at top().
Calling top() or front() one time too many after a drain loop; there is no exception and no bounds check, just undefined behaviour that shows up as a garbage value or a crash far from the real bug.
Try it yourself
Change, predict, then run
Fill a std::priority_queue<int, std::vector<int>, std::greater<int>> with 8, 3, 11, 3 and 7, then pop everything and print each value on its own line. Change only the third template argument to std::less<int> and confirm the order reverses.
Open the C++ workspaceCheck your understanding
Why does pop() on std::stack, std::queue, and std::priority_queue return void instead of the element being removed?
- A value-returning pop could lose the element if the copy or move out to the caller threw after the element was erased.
- The underlying deque and vector provide no way to hand back the element that is being erased.
- Copying the element out to the caller would make pop linear in the number of elements.
- pop() is permitted to remove more than one element, so there is no single value it could return.
Show answer
Splitting inspection from removal lets pop() be a plain no-throw erase while top() or front() gives you a reference you may copy or move from at your own risk; a combined operation would have to erase and then hand the value out, and a throw in between would destroy the element with no way to recover it. Option 2 is tempting but wrong on complexity grounds: copying one element is a constant-time step, and pop() stays O(1) or O(log n) either way, so cost is not the reason.