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