equal_range function template — Finds all occurrences of a value in a sorted range using binary search
template<typename FwdIter, typename T> pair<FwdIter, FwdIter> equal_range(FwdIter first, FwdIter last, const T& value); template<typename FwdIter, typename T, typename Compare> pair<FwdIter, FwdIter> equal_range(FwdIter first, FwdIter last, const T& value, Compare comp);
The equal_range
function
template determines where value
belongs in the sorted range [first
, last
). It returns a pair of iterators that
specify the start and one past the end of the range of items that
are equivalent to value
, or both
iterators in the pair point to where you can insert value
and preserve the sorted nature of
the range.
The first form compares values using the <
operator. The second form calls
comp(*iter
, value)
.
Figure 13-4 shows
how bounds are found with the value 36
. The result of calling equal_range
is pair(lb
, ub)
. Note that for values in the range
[19
, 35
], the upper and lower bound are both
equal to lb
, and for values in
the range [37
, 41
], the upper and lower bound are both
equal to ub
.
Precondition: !(*(i
+ 1)
< *i
) for all i
in [first
, last
- 1).
The equal_range
function
template returns the equivalent of calling the following, although
the actual implementation might be different:
std::make_pair(std::lower_bound(first, last, value), std::upper_bound(first, last, value))
or:
std::make_pair(std::lower_bound(first, last, value, comp), std::upper_bound(first, last, value, comp))
Complexity is logarithmic. The number of comparisons is at
most 2 × log(last
- first
) + 1. Although the iterator can be
a forward iterator, the best performance is obtained with a random
access iterator. With a forward or bidirectional iterator, the
iterator is advanced a linear number of times, even though the
number of comparisons is logarithmic.