C++ Basics: Preserve Equal-Key Order with stable_sort

Sort records by one key while retaining the input order of records with equivalent keys.

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-sort-equal-keys-demo.cpp:

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

struct Ticket {
    int priority;
    std::string name;
};

int main() {
    std::vector<Ticket> tickets{{2, "Ada"}, {1, "Ben"},
                                {2, "Cora"}, {1, "Dina"}};
    std::stable_sort(tickets.begin(), tickets.end(),
                     [](const Ticket& left, const Ticket& right) {
                         return left.priority < right.priority;
                     });
    for (const Ticket& ticket : tickets) {
        std::cout << ticket.priority << ": " << ticket.name << '\n';
    }
}

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

g++ -std=c++20 -Wall -Wextra -Werror -pedantic stable-sort-equal-keys-demo.cpp -o stable-sort-equal-keys-demo &&
./stable-sort-equal-keys-demo

Observed output:

1: Ben
1: Dina
2: Ada
2: Cora

Read the result

The priority-one tickets move first, but Ben still precedes Dina. Ada still precedes Cora among priority-two tickets. The comparator deliberately ignores names.

Apply it carefully

The comparator must define a strict weak ordering: use less-than, not less-than-or-equal. Stability concerns equivalence under that comparator, not equality of every record field. Ordinary std::sort does not promise this preservation. Sorting mutates the vector; make a copy first if the input order must remain available.

The C++ working draft describes the relevant library rules. This example uses only C++20 facilities, even though the linked draft also documents newer additions.

Clean up

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

rm -- stable-sort-equal-keys-demo.cpp stable-sort-equal-keys-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.