C++ Basics: Find the End of a Ready Prefix
Use std::partition_point to locate the boundary in a range that already places every matching element before every nonmatching element.
Prepare a scratch directory
Tested on Linux x86_64 with GCC 14.2.0. You need a C++20-capable compiler and standard-library development headers, with g++ on PATH, plus 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 1Run the example
Save this as partition-point-ready-prefix-demo.cpp:
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> status{1, 1, 1, 0, 0};
auto ready = [](int value) { return value == 1; };
if (!std::is_partitioned(status.begin(), status.end(), ready)) return 1;
auto boundary = std::partition_point(status.begin(), status.end(), ready);
std::cout << "ready prefix: " << boundary - status.begin() << '\n';
std::vector<int> none{0, 0};
auto first = std::partition_point(none.begin(), none.end(), ready);
std::cout << "none ready: " << first - none.begin() << '\n';
}Compile and run it. The program runs only after compilation succeeds:
g++ -std=c++20 -Wall -Wextra -Werror -pedantic partition-point-ready-prefix-demo.cpp -o partition-point-ready-prefix-demo &&
./partition-point-ready-prefix-demoObserved output:
ready prefix: 3
none ready: 0Read the result
The first boundary is index 3. When no element satisfies the predicate, the boundary equals begin.
Apply it carefully
The partitioned ordering is a precondition, not something partition_point creates or checks. An input such as 1, 0, 1 violates it. The example checks the precondition first; that linear validation removes the speed advantage of a binary boundary search. Skip that check only when your data structure already guarantees the ordering. An all-matching range returns end, which cannot be dereferenced.
The C++ working draft describes the relevant rules. This example uses C++20; the current working draft also includes later additions.
Clean up
Remove only the source and executable created here, then return to the starting directory:
rm -- partition-point-ready-prefix-demo.cpp partition-point-ready-prefix-demo
cd -- "$start_directory" || exit 1
rmdir -- "$work_directory"
unset start_directory work_directoryIf the directory is not empty, inspect its remaining contents before removing anything else.
Acknowledgements
This post was created with assistance from AI.