CKTIS / C++
std::ranges::equal_range — a range of equivalent elements
std::ranges::equal_range finds the half-open range of elements equivalent to a search value under a comparator. It supports ranges, iterator–sentinel pairs, and projections; it requires appropriately partitioned data, which sorting guarantees.
Version: C++23; repository compiler flag, production runtime not attested
Syntax
std::ranges::equal_range(first, last, value)
std::ranges::equal_range(first, last, value, comp)
std::ranges::equal_range(first, last, value, comp, proj)
std::ranges::equal_range(range, value)
std::ranges::equal_range(range, value, comp)
std::ranges::equal_range(range, value, comp, proj)std::ranges::equal_range, declared in <algorithm>, determines the range [lower_bound, upper_bound) without changing the data. Equivalence means that both comparisons comp(proj(element), value) and comp(value, proj(element)) are false; it need not agree with operator==. If there is no match, the result is an empty range at the value's insertion position.
Calls accept either an iterator–sentinel pair or a whole range. At least forward iterators are required, and comp must satisfy strict weak ordering requirements. The defaults are std::ranges::less and std::identity. The projection transforms elements, not the search value. The data must be partitioned so that the Boolean results of each expression comp(proj(element), value) and !comp(value, proj(element)) form a true prefix followed by a false suffix. Sorting with the same comparator and projection is sufficient; violating the preconditions causes undefined behavior.
The iterator overload returns std::ranges::subrange<I>, while the range overload returns std::ranges::borrowed_subrange_t<R>. For a temporary range that does not model borrowed_range, the latter type is std::ranges::dangling, not a usable subrange. The result does not store element copies: the data must remain alive and its iterators valid.
For N elements, there are at most 2 * log2(N) + O(1) comparisons and projections; without random-access iterators, iterator movement can be linear. The example searches keys through &Item::key: three matches occupy indices [1, 4), while key 3 produces an empty result. This example targets a C++23 build configuration; production runtime compatibility is not attested.
Examples
#include <algorithm>
#include <array>
#include <iostream>
struct Item {
int key;
};
int main() {
const std::array<Item, 5> items{{{1}, {2}, {2}, {2}, {4}}};
const auto matches = std::ranges::equal_range(items, 2, {}, &Item::key);
std::cout << "count=" << matches.size() << '\n';
std::cout << "begin=" << (matches.begin() - items.begin()) << '\n';
std::cout << "end=" << (matches.end() - items.begin()) << '\n';
const auto missing = std::ranges::equal_range(items, 3, {}, &Item::key);
std::cout << "missing=" << missing.empty() << '\n';
}
Result
count=3 begin=1 end=4 missing=1
The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.