std::equal_range() algorithm
- since C++20
- until C++20
// (1)
template< class ForwardIt, class T >
constexpr std::pair<ForwardIt, ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value );
// (2)
template< class ForwardIt, class T, class Compare >
constexpr std::pair<ForwardIt, ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value, Compare comp );
// (1)
template< class ForwardIt, class T >
std::pair<ForwardIt, ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value );
// (2)
template< class ForwardIt, class T, class Compare >
std::pair<ForwardIt, ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value, Compare comp );
Returns a range containing all elements equivalent to value in the range [first
; last
).
The range [first
; last
) must be at least partially ordered with respect to value
, i.e. it must satisfy all of the following requirements:
- Partitioned with respect to
element < value
orcomp(element, value)
(that is, all elements for which the expression istrue
precedes all elements for which the expression isfalse
) - Partitioned with respect to
!(value < element)
or!comp(value, element)
- For all elements, if
element < value
orcomp(element, value)
istrue
then!(value < element)
or!comp(value, element)
is alsotrue
A fully-sorted range meets these criteria.
The returned view is constructed from two iterators:
- Pointing to the first element that is not less than
value
. - Pointing to the first element greater than
value
.
The first iterator may be alternatively obtained with std::ranges::lower_bound()
, the second - with std::ranges::upper_bound()
.
- (1) Uses
operator<
to compare the elements. - (2) Uses the given comparison function
comp
.
Parameters
first last | The partially-ordered range to examine. |
value | The value to compare the elements to. |
comp | Comparison function object (i.e. an object that satisfies the requirements of Compare). The signature of the comparison function should be equivalent to the following:
|
Type requirements
ForwardIt | LegacyForwardIterator |
Compare | BinaryPredicate |
Compare
is not required to satisfy Compare.
Return value
A std::pair
containing a pair of iterators defining the wanted range:
- Pointing to the first element that is not less than
value
. - Pointing to the first element greater than
value
.
If there are no elements not less than value
, last
is returned as the first element.
Similarly if there are no elements greater than value
, last
is returned as the second element.
Complexity
The number of comparisons performed is logarithmic in the distance between first
and last
(at most `log^2(last - first) + O(1) comparisons).
However, for non-LegacyRandomAccessIterators, the number of iterator increments is linear.
Notably, std::map
, std::multimap
,
std::set
, and std::multiset
iterators are not random access,
and so their member equal_range()
functions should be preferred.
Exceptions
(none)
Possible implementation
equal_range (1)
template<class ForwardIt, class T>
std::pair<ForwardIt, ForwardIt>
equal_range(ForwardIt first, ForwardIt last, const T& value)
{
return std::make_pair(std::lower_bound(first, last, value),
std::upper_bound(first, last, value));
}
equal_range (2)
template<class ForwardIt, class T, class Compare>
std::pair<ForwardIt, ForwardIt>
equal_range(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
return std::make_pair(std::lower_bound(first, last, value, comp),
std::upper_bound(first, last, value, comp));
}
Examples
#include <algorithm>
#include <iostream>
#include <vector>
struct S
{
int number;
char name;
// note: name is ignored by this comparison operator
bool operator<(const S& s) const { return number < s.number; }
};
struct Comp
{
bool operator()(const S& s, int i) const { return s.number < i; }
bool operator()(int i, const S& s) const { return i < s.number; }
};
int main()
{
// note: not ordered, only partitioned w.r.t. S defined below
const std::vector<S> vec {{1, 'A'}, {2, 'B'}, {2, 'C'},
{2, 'D'}, {4, 'G'}, {3, 'F'}};
const S value {2, '?'};
std::cout << "Compare using S::operator<(): ";
const auto p = std::equal_range(vec.begin(), vec.end(), value);
for (auto i = p.first; i != p.second; ++i)
std::cout << i->name << ' ';
std::cout << "\n" "Using heterogeneous comparison: ";
const auto p2 = std::equal_range(vec.begin(), vec.end(), 2, Comp{});
for (auto i = p2.first; i != p2.second; ++i)
std::cout << i->name << ' ';
}
Compare using S::operator<(): B C D
Using heterogeneous comparison: B C D
Hover to see the original license.