1 /// \file
2 // 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 
24 #include <range/v3/algorithm/find_if.hpp>
25 #include <range/v3/algorithm/find_if_not.hpp>
26 #include <range/v3/functional/identity.hpp>
27 #include <range/v3/iterator/concepts.hpp>
28 #include <range/v3/iterator/reverse_iterator.hpp>
29 #include <range/v3/range/access.hpp>
30 #include <range/v3/range/concepts.hpp>
31 #include <range/v3/utility/move.hpp>
32 #include <range/v3/utility/static_const.hpp>
33 
34 #include <range/v3/detail/prologue.hpp>
35 
36 namespace ranges
37 {
38     /// \addtogroup group-algorithms
39     /// @{
40 
41     /// unstable_remove have O(1) complexity for each element remove, unlike remove O(n)
42     /// [for worst case]. Each erased element overwritten (moved in) with last one.
43     /// unstable_remove_if does not preserve relative element order.
44     RANGES_FUNC_BEGIN(unstable_remove_if)
45 
46         /// \brief function template \c unstable_remove_if
47         template(typename I, typename C, typename P = identity)(
48             /// \pre
49             requires bidirectional_iterator<I> AND permutable<I> AND
50             indirect_unary_predicate<C, projected<I, P>>)
51         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, std::ref(pred), std::ref(proj));
56                 last = find_if_not(make_reverse_iterator(std::move(last)),
57                                    make_reverse_iterator(first),
58                                    std::ref(pred),
59                                    std::ref(proj))
60                            .base();
61                 if(first == last)
62                     return first;
63                 *first = iter_move(--last);
64 
65                 // discussion here: https://github.com/ericniebler/range-v3/issues/988
66                 ++first;
67             }
68         }
69 
70         /// \overload
71         template(typename Rng, typename C, typename P = identity)(
72             /// \pre
73             requires bidirectional_range<Rng> AND common_range<Rng> AND
74             permutable<iterator_t<Rng>> AND
75             indirect_unary_predicate<C, projected<iterator_t<Rng>, P>>)
76         borrowed_iterator_t<Rng> //
77         RANGES_FUNC(unstable_remove_if)(Rng && rng, C pred, P proj = P{}) //
78         {
79             return (*this)(begin(rng), end(rng), std::move(pred), std::move(proj));
80         }
81 
82     RANGES_FUNC_END(unstable_remove_if)
83     /// @}
84 } // namespace ranges
85 
86 #include <range/v3/detail/epilogue.hpp>
87 
88 #endif // RANGES_V3_ALGORITHM_UNSTABLE_REMOVE_IF_HPP
89