C++ Basics: Order Sequences by Their First Difference

Compare integer paths with std::lexicographical_compare, including prefix cases.

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 lexicographical-sequence-order-demo.cpp:

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

int main()
{
    const std::vector<int> a{1, 9};
    const std::vector<int> b{2, 0};
    const std::vector<int> prefix{1};
    std::cout << std::boolalpha;
    std::cout << "First difference: " << std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()) << '\n';
    std::cout << "Shorter prefix: " << std::lexicographical_compare(prefix.begin(), prefix.end(), a.begin(), a.end()) << '\n';
    std::cout << "Equal inputs: " << std::lexicographical_compare(a.begin(), a.end(), a.begin(), a.end()) << '\n';
}

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

g++ -std=c++20 -Wall -Wextra -Werror -pedantic lexicographical-sequence-order-demo.cpp -o lexicographical-sequence-order-demo &&
./lexicographical-sequence-order-demo

Observed output:

First difference: true
Shorter prefix: true
Equal inputs: false

Read the result

The first comparison is true because 1 is less than 2; the later 9 does not change that decision. A matching shorter prefix sorts first. Comparing an input with itself returns false because the operation is strict less-than, not less-than-or-equal.

Apply it carefully

Lexicographic ordering does not compare sums, lengths first, or every position independently. For text, character-by-character comparison is not automatically locale-aware collation or natural numeric ordering. Supply an appropriate strict weak ordering for your element type and use it consistently wherever sequences are sorted and searched.

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 -- lexicographical-sequence-order-demo.cpp lexicographical-sequence-order-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.