std::ranges::equal_range
From cppreference.com
| Defined in header <algorithm>
|
||
| Call signature |
||
template< std::forward_iterator I, std::sentinel_for<I> S,
class T, class Proj = std::identity,
std::indirect_strict_weak_order
<const T*, std::projected<I, Proj>> Comp = ranges::less >
constexpr ranges::subrange<I> equal_range( I first, S last, const T& value,
Comp comp = {}, Proj proj = {} );
|
(1) | (since C++20) (until C++26) |
template< std::forward_iterator I, std::sentinel_for<I> S,
class Proj = std::identity,
class T = std::projected_value_t<I, Proj>,
std::indirect_strict_weak_order
<const T*, std::projected<I, Proj>> Comp = ranges::less >
constexpr ranges::subrange<I> equal_range( I first, S last, const T& value,
Comp comp = {}, Proj proj = {} );
|
(since C++26) | |
template< ranges::forward_range R,
class T, class Proj = std::identity,
std::indirect_strict_weak_order
<const T*, std::projected<ranges::iterator_t<R>,
Proj>> Comp = ranges::less >
constexpr ranges::borrowed_subrange_t<R>
equal_range( R&& r, const T& value, Comp comp = {}, Proj proj = {} );
|
(2) | (since C++20) (until C++26) |
template< ranges::forward_range R,
class Proj = std::identity,
class T = std::projected_value_t<ranges::iterator_t<R>, Proj>,
std::indirect_strict_weak_order
<const T*, std::projected<ranges::iterator_t<R>,
Proj>> Comp = ranges::less >
constexpr ranges::borrowed_subrange_t<R>
equal_range( R&& r, const T& value, Comp comp = {}, Proj proj = {} );
|
(since C++26) | |
Searches for the range containing all elements (projected by proj) equivalent to value in the partitioned source range [first, last) or r. An element is considered equivalent to value if its projected value neither orders before nor orders after value with the comparator comp.
If the elements e of the source range are not partitioned with respect the following expressions at the same time, the behavior is undefined:
bool(std::invoke(comp, std::invoke(proj, e), value))!bool(std::invoke(comp, value, std::invoke(proj, e)))
The function-like entities described on this page are algorithm function objects (informally known as niebloids), that is:
- Explicit template argument lists cannot be specified when calling any of them.
- None of them are visible to argument-dependent lookup.
- When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited.
Parameters
| first, last | - | the iterator-sentinel pair defining the source range |
| r | - | the source range |
| value | - | the value to be compared with the (projected) elements |
| comp | - | the comparator to be applied to the (projected) elements |
| proj | - | the projection to be applied to the elements |
Return value
A subrange of the source range containing exactly all elements equivalent to value; the subrange is empty if no such element is found.
Complexity
Given N as ranges::distance(first, last) or ranges::distance(r):
1,2) At most 2log2(N)+𝓞(1) applications of
comp and proj.Notes
| Feature-test macro | Value | Std | Feature |
|---|---|---|---|
__cpp_lib_algorithm_default_value_type |
202403 |
(C++26) | List-initialization for algorithms (1,2) |
Possible implementation
struct equal_range_fn
{
template<std::forward_iterator I, std::sentinel_for<I> S,
class Proj = std::identity, class T = std::projected_value_t<I, Proj>,
std::indirect_strict_weak_order
<const T*, std::projected<I, Proj>> Comp = ranges::less>
constexpr ranges::subrange<I>
operator()(I first, S last, const T& value, Comp comp = {}, Proj proj = {}) const
{
return ranges::subrange
(
ranges::lower_bound(first, last, value, std::ref(comp), std::ref(proj)),
ranges::upper_bound(first, last, value, std::ref(comp), std::ref(proj))
);
}
template<ranges::forward_range R, class Proj = std::identity,
class T = std::projected_value_t<ranges::iterator_t<R>, Proj>,
std::indirect_strict_weak_order
<const T*, std::projected<ranges::iterator_t<R>,
Proj>> Comp = ranges::less>
constexpr ranges::borrowed_subrange_t<R>
operator()(R&& r, const T& value, Comp comp = {}, Proj proj = {}) const
{
return (*this)(ranges::begin(r),
ranges::next(ranges::begin(r), ranges::end(r)),
value, std::ref(comp), std::ref(proj));
}
};
inline constexpr equal_range_fn equal_range;
|
Example
Run this code
#include <algorithm>
#include <compare>
#include <print>
#include <vector>
#include <utility>
struct S
{
int number{};
char name{};
// note: name is ignored by these comparison operators
friend bool operator== (const S s1, const S s2) { return s1.number == s2.number; }
friend auto operator<=>(const S s1, const S s2) { return s1.number <=> s2.number; }
};
template<>
struct std::formatter<S>
{
constexpr auto parse(auto& ctx) { return ctx.begin(); }
template<class Context>
Context::iterator format(const S& s, Context& ctx) const
{
return std::format_to(ctx.out(), "{{{}, '{}'}}", s.number, s.name);
}
};
int main()
{
// Note: not ordered, only partitioned w.r.t. S defined below
std::vector<S> vec{{1,'A'}, {2,'B'}, {2,'C'}, {2,'D'}, {4, 'D'}, {4,'G'}, {3,'F'}};
const S value{2, '?'};
namespace ranges = std::ranges;
auto a = ranges::equal_range(vec, value);
std::println("1. {}", a);
auto b = ranges::equal_range(vec.begin(), vec.end(), value);
std::println("2. {}", b);
auto c = ranges::equal_range(vec, 'D', ranges::less {}, &S::name);
std::println("3. {}", c);
auto d = ranges::equal_range(vec.begin(), vec.end(), 'D', ranges::less {}, &S::name);
std::println("4. {}", d);
using PairIntInt = std::pair<int, int>;
std::vector<PairIntInt> nums{{1, 0}, {2, 2}, {2, 1}, {3, 0}, {3, 1}};
auto cmp1 = [](PairIntInt x, PairIntInt y) { return x.first < y.first; };
#ifdef __cpp_lib_algorithm_default_value_type
auto p3 = ranges::equal_range(nums, {2, 0}, cmp1);
#else
auto p3 = ranges::equal_range(nums, PairIntInt{2, 0}, cmp1);
#endif
std::println("5. {}", p3);
}
Output:
1. [{2, 'B'}, {2, 'C'}, {2, 'D'}]
2. [{2, 'B'}, {2, 'C'}, {2, 'D'}]
3. [{2, 'D'}, {4, 'D'}]
4. [{2, 'D'}, {4, 'D'}]
5. [(2, 2), (2, 1)]