C++ Basics: Define a Deterministic Priority Queue Order

A priority queue is useful when the next job should be chosen by priority instead of arrival order. Supply a comparator and an explicit tie-break rule.

Prepare a scratch directory

Tested on Linux x86_64 with GCC 14.2.0. Install a C++20-capable compiler and its standard-library headers, and make g++ available on PATH. You also need Bash, a text editor, and mktemp, rm, and rmdir. No third-party library is required.

Keep the same terminal open. Stop if setup fails, before saving the source:

start_directory="$PWD"
work_directory="$(mktemp -d)" || exit 1
cd -- "$work_directory" || exit 1

Run the example

Save this as priority-queue-comparator-demo.cpp:

#include <iostream>
#include <queue>
#include <string>
#include <vector>

struct Job {
    int urgency;
    int sequence;
    std::string name;
};

struct LowerPriority {
    bool operator()(const Job& left, const Job& right) const {
        if (left.urgency != right.urgency) {
            return left.urgency < right.urgency;
        }
        return left.sequence > right.sequence;
    }
};

int main() {
    std::priority_queue<Job, std::vector<Job>, LowerPriority> jobs;
    jobs.push({2, 1, "report"});
    jobs.push({5, 3, "backup"});
    jobs.push({5, 2, "restore"});
    while (!jobs.empty()) {
        const Job next = jobs.top();
        jobs.pop();
        std::cout << next.name << ": urgency=" << next.urgency
                  << "; sequence=" << next.sequence << '\n';
    }
}

Compile and run it. The && prevents execution if compilation fails:

g++ -std=c++20 -Wall -Wextra -Werror -pedantic priority-queue-comparator-demo.cpp -o priority-queue-comparator-demo &&
./priority-queue-comparator-demo

Observed output:

restore: urgency=5; sequence=2
backup: urgency=5; sequence=3
report: urgency=2; sequence=1

Read the result

The comparator returns true when its left job has lower priority. Larger urgency wins; for equal urgency, the smaller sequence number wins. Restore therefore precedes backup even though backup was pushed first. Copying top() before pop() keeps a valid job value after removal.

Apply it carefully

The comparator must define a strict weak ordering: never use <= for the priority comparison. A priority_queue does not guarantee FIFO order for equivalent values, so supply unique sequence numbers when that tie behavior matters. Check empty() before top() or pop(), and do not mutate ordering fields inside the queue.

The C++ working draft documents the relevant container behavior. The example uses only features available in C++20, even though the linked draft may include later additions.

Clean up

Remove only the source and executable created here, then remove the empty practice directory:

rm -- priority-queue-comparator-demo.cpp priority-queue-comparator-demo
cd -- "$start_directory" || exit 1
rmdir -- "$work_directory"
unset start_directory work_directory

If the directory is not empty, inspect the remaining contents before removing anything else.

Acknowledgements

This post was created with assistance from AI.