Horizon
equal_range.hpp
Go to the documentation of this file.
1 // 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 
17 #include <range/v3/range_fwd.hpp>
18 
29 #include <range/v3/utility/static_const.hpp>
31 
32 #include <range/v3/detail/prologue.hpp>
33 
34 namespace 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
CPP_concept indirect_strict_weak_order
\concept indirect_strict_weak_order
Definition: concepts.hpp:689
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