Horizon
Loading...
Searching...
No Matches
equal_range.hpp
Go to the documentation of this file.
1
2// Range v3 library
3//
4// Copyright Eric Niebler 2014-present
5// Copyright Casey Carter 2016
6//
7// Use, modification and distribution is subject to the
8// Boost Software License, Version 1.0. (See accompanying
9// file LICENSE_1_0.txt or copy at
10// http://www.boost.org/LICENSE_1_0.txt)
11//
12// Project home: https://github.com/ericniebler/range-v3
13//
14#ifndef RANGES_V3_ALGORITHM_EQUAL_RANGE_HPP
15#define RANGES_V3_ALGORITHM_EQUAL_RANGE_HPP
16
18
29#include <range/v3/utility/static_const.hpp>
31
32#include <range/v3/detail/prologue.hpp>
33
34namespace ranges
35{
38 RANGES_FUNC_BEGIN(equal_range)
39
40
41 template(typename I,
42 typename S,
43 typename V,
44 typename C = less,
45 typename P = identity)(
46 requires forward_iterator<I> AND sentinel_for<S, I> AND
47 indirect_strict_weak_order<C, V const *, projected<I, P>>)
48 constexpr subrange<I> RANGES_FUNC(equal_range)(
49 I first, S last, V const & val, C pred = C{}, P proj = P{})
50 {
51 if(RANGES_CONSTEXPR_IF(sized_sentinel_for<S, I>))
52 {
53 auto const len = distance(first, last);
54 return aux::equal_range_n(
55 std::move(first), len, val, std::move(pred), std::move(proj));
56 }
57
58 // Probe exponentially for either end-of-range, an iterator that
59 // is past the equal range (i.e., denotes an element greater
60 // than val), or is in the equal range (denotes an element equal
61 // to val).
62 auto dist = iter_difference_t<I>{1};
63 while(true)
64 {
65 auto mid = first;
66 auto d = advance(mid, dist, last);
67 if(d || mid == last)
68 {
69 // at the end of the input range
70 dist -= d;
71 return aux::equal_range_n(
72 std::move(first), dist, val, ranges::ref(pred), ranges::ref(proj));
73 }
74 // if val < *mid, mid is after the target range.
75 auto && v = *mid;
76 auto && pv = invoke(proj, (decltype(v) &&)v);
77 if(invoke(pred, val, pv))
78 {
79 return aux::equal_range_n(
80 std::move(first), dist, val, ranges::ref(pred), ranges::ref(proj));
81 }
82 else if(!invoke(pred, pv, val))
83 {
84 // *mid == val: the lower bound is <= mid, and the upper bound is >
85 // mid.
86 return {
87 aux::lower_bound_n(
88 std::move(first), dist, val, ranges::ref(pred), ranges::ref(proj)),
89 upper_bound(std::move(mid),
90 std::move(last),
91 val,
92 ranges::ref(pred),
93 ranges::ref(proj))};
94 }
95 // *mid < val, mid is before the target range.
96 first = std::move(mid);
97 ++first;
98 dist *= 2;
99 }
100 }
101
103 template(typename Rng, typename V, typename C = less, typename P = identity)(
104 requires forward_range<Rng> AND
105 indirect_strict_weak_order<C, V const *, projected<iterator_t<Rng>, P>>)
106 constexpr borrowed_subrange_t<Rng> //
107 RANGES_FUNC(equal_range)(Rng && rng, V const & val, C pred = C{}, P proj = P{}) //
108 {
109 if(RANGES_CONSTEXPR_IF(sized_range<Rng>))
110 {
111 auto const len = distance(rng);
112 return aux::equal_range_n(
113 begin(rng), len, val, std::move(pred), std::move(proj));
114 }
115
116 return (*this)(begin(rng), end(rng), val, std::move(pred), std::move(proj));
117 }
118
119 RANGES_FUNC_END(equal_range)
120
121 namespace cpp20
122 {
123 using ranges::equal_range;
124 }
126} // namespace ranges
127
128#include <range/v3/detail/epilogue.hpp>
129
130#endif
typename Fn::template invoke< Args... > invoke
Evaluate the invocable Fn with the arguments Args.
Definition meta.hpp:541
front< Pair > first
Retrieve the first element of the pair Pair.
Definition meta.hpp:2251
bool_<(T::type::value< U::type::value)> less
A Boolean integral constant wrapper around true if T::type::value is less than U::type::value; false,...
Definition meta.hpp:255