Container adapters: stack, queue, and heap priority

A restricted interface is a design choice

stack exposes only LIFO top, push, and pop. queue expresses FIFO front, back, push, and pop. The default underlying container for both is deque. A stack may also use vector. A queue needs pop_front, so it cannot sit directly on vector. Adapters have no public iterator interface like ordinary containers. That restriction is the access discipline, not a missing feature.

Operation cost follows the underlying container and cannot be judged in isolation. Read or pop only when the adapter is not empty. pop returns void and does not return the removed value. Copy or move top or front into a local first, then call pop, so you do not keep using a reference to an element after it has been removed.

A heap guarantees only the top, not a fully ordered sequence

priority_queue defaults to vector and maintains the highest-priority element with heap algorithms. top is constant time. Heap adjustment on push and pop needs a logarithmic number of comparisons, but vector growth can make a particular push pay an extra linear move cost. Building a heap in bulk has linear comparison complexity; you need not insert an existing batch one element at a time.

The heap interior is not a fully sorted sequence. You cannot infer the second- or third-highest priority from storage position. The adapter also has no interface to update an arbitrary element's priority directly. If task priority can change, the usual approaches are to reinsert versioned information and filter stale versions on pop, or to choose a data structure that offers handle-based updates—not to mutate external state the comparator secretly reads.

Comparator direction and deterministic ties

comp(a,b) being true means a comes before b in comparison order. The heap top is the largest item in that order. Default less therefore puts the numerically largest item on top; greater puts the smallest on top. The comparator must still be a strict weak ordering and must not return true merely because two priorities are equal.

The example wants earlier deadlines to run first, and for the same deadline a smaller id to run first. The comparator therefore treats a later task, or a same-time larger id, as "before," so the earlier one appears on top. Without a tie field, the pop order of equivalent tasks is not guaranteed to be stable. For a reproducible execution order, fold a monotonic sequence number or another stable key into the comparison.

Pitfalls

• A priority_queue with less is a max-heap, not an ascending pop order. The comparator's "comes before" is the opposite of the business sense of "runs first."
• top returns a const reference, and after the container is modified you must not rely on an old reference still naming the same task. Take the values you need, then pop.

Minimum C++11 · complete program · Download .cpp

#include <cassert>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

struct Job { int deadline; int id; };
struct Later {
    bool operator()(const Job& a, const Job& b) const {
        if (a.deadline != b.deadline) return a.deadline > b.deadline;
        return a.id > b.id;
    }
};

int main() {
    std::stack<int> undo;
    undo.push(1);
    undo.push(2);
    assert(undo.top() == 2);
    undo.pop();
    assert(undo.top() == 1);

    std::queue<int> fifo;
    fifo.push(1);
    fifo.push(2);
    assert(fifo.front() == 1);
    fifo.pop();
    assert(fifo.front() == 2);

    std::priority_queue<Job, std::vector<Job>, Later> ready;
    ready.push(Job{5, 1});
    ready.push(Job{2, 3});
    ready.push(Job{2, 2});
    std::vector<int> order;
    while (!ready.empty()) {
        Job current = ready.top();
        ready.pop();
        order.push_back(current.id);
    }
    assert((order == std::vector<int>{2, 3, 1}));
    std::cout << order[0] << ' ' << order[1] << ' ' << order[2] << '\n';
}

Compile locally

g++ -std=c++11 -Wall -Wextra -Wpedantic -pthread stl-adapters.cpp -o example && ./example

Expected result

2 3 1

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

You need to take the minimum value repeatedly from a set of integers. How do you declare the priority_queue? If equal values must keep task arrival order, what else is required?

Check the sources

• Working draft [priority.queue]: underlying requirements, comparators, and heap operations

Drafts and official chapters change. The version mark is only the example’s minimum.