All of the algorithms in this section are versions of binary search and assume that the sequence being searched is partitioned with respect to an expression formed by binding the search key to an argument of the comparison function and projection. They work on non-random access iterators minimizing the number of comparisons, which will be logarithmic for all types of iterators. They are especially appropriate for random access iterators, because these algorithms do a logarithmic number of steps through the data structure. For non-random access iterators they execute a linear number of steps.
template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<I, Proj>> Comp = less<>>
I
lower_bound(I first, S last, const T& value, Comp comp = Comp{},
Proj proj = Proj{});
template <ForwardRange Rng, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<iterator_t<Rng>, Proj>> Comp = less<>>
safe_iterator_t<Rng>
lower_bound(Rng&& rng, const T& value, Comp comp = Comp{}, Proj proj = Proj{});
Requires: The elements e of [first,last) shall be partitioned with respect to the expression invoke(comp, invoke(proj, e), value).
Returns: The furthermost iterator i in the range [first,last] such that for every iterator j in the range [first,i) the following corresponding condition holds: invoke(comp, invoke(proj, *j), value) != false.
Complexity: At most log2(last - first) + Ο(1) applications of the comparison function and projection.
template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<I, Proj>> Comp = less<>>
I
upper_bound(I first, S last, const T& value, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardRange Rng, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<iterator_t<Rng>, Proj>> Comp = less<>>
safe_iterator_t<Rng>
upper_bound(Rng&& rng, const T& value, Comp comp = Comp{}, Proj proj = Proj{});
Requires: The elements e of [first,last) shall be partitioned with respect to the expression !invoke(comp, value, invoke(proj, e)).
Returns: The furthermost iterator i in the range [first,last] such that for every iterator j in the range [first,i) the following corresponding condition holds: invoke(comp, value, invoke(proj, *j)) == false.
Complexity: At most log2(last - first) + Ο(1) applications of the comparison function and projection.
template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<I, Proj>> Comp = less<>>
tagged_pair<tag::begin(I), tag::end(I)>
equal_range(I first, S last, const T& value, Comp comp = Comp{}, Proj proj = Proj{});
template <ForwardRange Rng, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<iterator_t<Rng>, Proj>> Comp = less<>>
tagged_pair<tag::begin(safe_iterator_t<Rng>),
tag::end(safe_iterator_t<Rng>)>
equal_range(Rng&& rng, const T& value, Comp comp = Comp{}, Proj proj = Proj{});
Requires:
The elements
e
of
[first,last)
shall be partitioned with respect to the expressions
invoke(comp, invoke(proj, e), value)
and
!invoke(comp, value, invoke(proj, e)).
Also, for all elements
e
of
[first, last),
invoke(comp, invoke(proj, e), value)
shall imply
!invoke(comp, value, invoke(proj, e)).
Returns:
Complexity: At most 2 * log2(last - first) + Ο(1) applications of the comparison function and projection.
template <ForwardIterator I, Sentinel<I> S, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<I, Proj>> Comp = less<>>
bool
binary_search(I first, S last, const T& value, Comp comp = Comp{},
Proj proj = Proj{});
template <ForwardRange Rng, class T, class Proj = identity,
IndirectStrictWeakOrder<const T*, projected<iterator_t<Rng>, Proj>> Comp = less<>>
bool
binary_search(Rng&& rng, const T& value, Comp comp = Comp{},
Proj proj = Proj{});
Requires: The elements e of [first,last) are partitioned with respect to the expressions invoke(comp, invoke(proj, e), value) and !invoke(comp, value, invoke(proj, e)). Also, for all elements e of [first, last), invoke(comp, invoke(proj, e), value) shall imply !invoke(comp, value, invoke(proj, e)).
Returns: true if there is an iterator i in the range [first,last) that satisfies the corresponding conditions: invoke(comp, invoke(proj, *i), value) == false && invoke(comp, value, invoke(proj, *i)) == false.
Complexity: At most log2(last - first) + Ο(1) applications of the comparison function and projection.