Horizon
unstable_remove_if.hpp
Go to the documentation of this file.
1 // Range v3 library
3 //
4 // Copyright Andrey Diduh 2019
5 // Copyright Casey Carter 2019
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_UNSTABLE_REMOVE_IF_HPP
15 #define RANGES_V3_ALGORITHM_UNSTABLE_REMOVE_IF_HPP
16 
17 #include <functional>
18 #include <utility>
19 
20 #include <concepts/concepts.hpp>
21 
22 #include <range/v3/range_fwd.hpp>
23 
33 #include <range/v3/utility/static_const.hpp>
34 
35 #include <range/v3/detail/prologue.hpp>
36 
37 namespace ranges
38 {
41 
45  RANGES_FUNC_BEGIN(unstable_remove_if)
46 
47 
48  template(typename I, typename C, typename P = identity)(
49  requires bidirectional_iterator<I> AND permutable<I> AND
50  indirect_unary_predicate<C, projected<I, P>>)
51  constexpr I RANGES_FUNC(unstable_remove_if)(I first, I last, C pred, P proj = {})
52  {
53  while(true)
54  {
55  first = find_if(std::move(first), last, ranges::ref(pred), ranges::ref(proj));
56  if(first == last)
57  return first;
58 
59  last = next(find_if_not(make_reverse_iterator(std::move(last)),
60  make_reverse_iterator(next(first)),
61  ranges::ref(pred),
62  ranges::ref(proj)))
63  .base();
64  if(first == last)
65  return first;
66 
67  *first = iter_move(last);
68 
69  // discussion here: https://github.com/ericniebler/range-v3/issues/988
70  ++first;
71  }
72  }
73 
75  template(typename Rng, typename C, typename P = identity)(
76  requires bidirectional_range<Rng> AND common_range<Rng> AND
77  permutable<iterator_t<Rng>> AND
78  indirect_unary_predicate<C, projected<iterator_t<Rng>, P>>)
79  constexpr borrowed_iterator_t<Rng> //
80  RANGES_FUNC(unstable_remove_if)(Rng && rng, C pred, P proj = P{}) //
81  {
82  return (*this)(begin(rng), end(rng), std::move(pred), std::move(proj));
83  }
84 
85  RANGES_FUNC_END(unstable_remove_if)
87 } // namespace ranges
88 
89 #include <range/v3/detail/epilogue.hpp>
90 
91 #endif // RANGES_V3_ALGORITHM_UNSTABLE_REMOVE_IF_HPP
template(typename I, typename C, typename P=identity)(requires bidirectional_iterator< I > AND permutable< I > AND indirect_unary_predicate< C
unstable_remove have O(1) complexity for each element remove, unlike remove O(n) [for worst case].
CPP_concept permutable
\concept permutable
Definition: concepts.hpp:840
CPP_concept indirect_unary_predicate
\concept indirect_unary_predicate
Definition: concepts.hpp:632
CPP_concept bidirectional_iterator
\concept bidirectional_iterator
Definition: concepts.hpp:390
front< Pair > first
Retrieve the first element of the pair Pair.
Definition: meta.hpp:2251
_t< detail::find_if_< L, Fn > > find_if
Return the tail of the list L starting at the first element A such that invoke<Fn,...
Definition: meta.hpp:2506
Definition: identity.hpp:25