CKTIS / C++
std::equal_range: boundaries of elements equivalent to a key
std::equal_range returns a pair of iterators enclosing every element equivalent to a searched value in an ordered range.
Version: C++23
Syntax
template<class ForwardIterator, class T, class Compare>
constexpr std::pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);std::equal_range(first, last, value, comp) from <algorithm> returns {lower_bound(...), upper_bound(...)}. The first iterator marks the beginning of the equivalence class and the second is just past it; when no match exists, both equal the insertion position.
The range must be partitioned for both comp(element, value) and !comp(value, element), and comp(element, value) must imply !comp(value, element) for every element. Violating either partition requirement or that implication causes undefined behavior. Full sorting by the same strict weak ordering is a safe sufficient condition, not a separate requirement.
The algorithm requires a forward iterator and performs at most 2 * log2(N) + O(1) comparisons. Random-access iterators give logarithmic traversal steps, but other forward iterators can require linear steps. The comparator must match the ordering used to prepare the range.
Examples
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
const std::vector<int> values{1, 2, 2, 2, 4};
const auto [first, last] = std::equal_range(values.begin(), values.end(), 2);
std::cout << (first - values.begin()) << ' ' << (last - first) << '\n';
}
Result
1 3
std::equal_range → 1 3