Horizon
Loading...
Searching...
No Matches
equal_range_n.hpp
Go to the documentation of this file.
1
2// Range v3 library
3//
4// Copyright Eric Niebler 2014-present
5//
6// Use, modification and distribution is subject to the
7// Boost Software License, Version 1.0. (See accompanying
8// file LICENSE_1_0.txt or copy at
9// http://www.boost.org/LICENSE_1_0.txt)
10//
11// Project home: https://github.com/ericniebler/range-v3
12//
13#ifndef RANGES_V3_ALGORITHM_AUX_EQUAL_RANGE_N_HPP
14#define RANGES_V3_ALGORITHM_AUX_EQUAL_RANGE_N_HPP
15
16#include <functional>
17
19
30#include <range/v3/utility/static_const.hpp>
32
33#include <range/v3/detail/prologue.hpp>
34
35namespace ranges
36{
37 namespace aux
38 {
40 {
41 template(typename I, typename V, typename R = less, typename P = identity)(
42 requires forward_iterator<I> AND
43 indirect_strict_weak_order<R, V const *, projected<I, P>>)
44 constexpr subrange<I> operator()(I first,
45 iter_difference_t<I> dist,
46 V const & val,
47 R pred = R{},
48 P proj = P{}) const
49 {
50 if(0 < dist)
51 {
52 do
53 {
54 auto half = dist / 2;
55 auto middle = ranges::next(first, half);
56 auto && v = *middle;
57 auto && pv = invoke(proj, (decltype(v) &&)v);
58 if(invoke(pred, pv, val))
59 {
60 first = std::move(++middle);
61 dist -= half + 1;
62 }
63 else if(invoke(pred, val, pv))
64 {
65 dist = half;
66 }
67 else
68 {
69 return {lower_bound_n(std::move(first),
70 half,
71 val,
72 ranges::ref(pred),
73 ranges::ref(proj)),
74 upper_bound_n(ranges::next(middle),
75 dist - (half + 1),
76 val,
77 ranges::ref(pred),
78 ranges::ref(proj))};
79 }
80 } while(0 != dist);
81 }
82 return {first, first};
83 }
84 };
85
86 RANGES_INLINE_VARIABLE(equal_range_n_fn, equal_range_n)
87 } // namespace aux
88} // namespace ranges
89
90#include <range/v3/detail/epilogue.hpp>
91
92#endif
The forward_iterator concept.
The indirect_strict_weak_order concept.
Definition equal_range_n.hpp:40
Definition identity.hpp:25
Definition comparisons.hpp:50
Definition subrange.hpp:196