C++ Basics: Group Priority Tasks While Preserving Arrival Order

Use std::stable_partition to put urgent work first without reordering either group.

Prepare a scratch directory

Tested on Linux x86_64 with GCC 14.2.0. Install a C++20-capable compiler and standard-library development headers, with g++ on PATH. You also need Bash, a text editor, and the mktemp, rm, and rmdir utilities. 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 stable-partition-priority-demo.cpp:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main()
{
    struct Task { int id; bool urgent; };
    std::vector<Task> tasks{{1, false}, {2, true}, {3, false}, {4, true}};
    const auto normal = std::stable_partition(tasks.begin(), tasks.end(),
        [](const Task& task) { return task.urgent; });
    std::cout << "Order:";
    for (const auto& task : tasks) std::cout << ' ' << task.id;
    std::cout << "\nUrgent count: " << std::distance(tasks.begin(), normal) << '\n';
}

Compile and run it. The program runs only after compilation succeeds:

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

Observed output:

Order: 2 4 1 3
Urgent count: 2

Read the result

Urgent tasks 2 and 4 come first in their original relative order. Normal tasks 1 and 3 follow, also in arrival order. The returned boundary points to the first false-predicate element, giving an urgent count of two.

Apply it carefully

The vector is rearranged in place. An iterator to a position may now refer to a different logical task. std::partition offers grouping without the stability promise; use stable_partition when order within groups matters. The stable algorithm can use temporary storage and has different movement costs depending on available memory. If every item is urgent, the returned boundary is end().

The C++ working draft describes the relevant rules. This example builds in C++20 mode; the current working draft also documents later additions.

Clean up

Remove only the source and executable created here, then return to the starting directory:

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

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

Acknowledgements

This post was created with assistance from AI.