C++ Basics: Find the Whole Run of a Repeated Sorted Key

Use std::equal_range to locate all occurrences of a key in a sorted vector.

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 equal-range-count-demo.cpp:

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

int main()
{
    const std::vector<int> keys{1, 2, 2, 2, 4};
    for (int key : {2, 3}) {
        const auto [first, last] = std::equal_range(keys.begin(), keys.end(), key);
        std::cout << key << ": start=" << std::distance(keys.begin(), first)
                  << " count=" << std::distance(first, last) << '\n';
    }
}

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

g++ -std=c++20 -Wall -Wextra -Werror -pedantic equal-range-count-demo.cpp -o equal-range-count-demo &&
./equal-range-count-demo

Observed output:

2: start=1 count=3
3: start=4 count=0

Read the result

The half-open range for 2 begins at index 1 and contains three values. The missing key 3 produces an empty range at index 4, its insertion position. No dereference is needed to count either result.

Apply it carefully

A vector sorted with the same comparison satisfies the partitioning requirements. Do not run this search on arbitrarily ordered data. With custom comparisons, equivalence means neither value compares less than the other, which can differ from operator==. Iterator subtraction is convenient for vectors; std::distance also expresses the count for other iterator categories, where traversal can cost more.

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 -- equal-range-count-demo.cpp equal-range-count-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.