25 Algorithms library [algorithms]

25.4 Sorting and related operations [alg.sorting]

25.4.3 Binary search [alg.binary.search]

25.4.3.3 equal_range [equal.range]

template<class ForwardIterator, class T> pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value); template<class ForwardIterator, class T, class Compare> pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

Requires: The elements e of [first,last) shall be partitioned with respect to the expressions e < value and !(value < e) or comp(e, value) and !comp(value, e). Also, for all elements e of [first, last), e < value shall imply !(value < e) or comp(e, value) shall imply !comp(value, e).

Returns:

make_pair(lower_bound(first, last, value),
          upper_bound(first, last, value))

or

make_pair(lower_bound(first, last, value, comp),
          upper_bound(first, last, value, comp))

Complexity: At most 2 * log2(last - first) + Ο(1) comparisons.