v3/algorithm/unstable_remove_if.hpp

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Andrey Diduh 2019
0005 //  Copyright Casey Carter 2019
0006 //
0007 //  Use, modification and distribution is subject to the
0008 //  Boost Software License, Version 1.0. (See accompanying
0009 //  file LICENSE_1_0.txt or copy at
0010 //  http://www.boost.org/LICENSE_1_0.txt)
0011 //
0012 // Project home: https://github.com/ericniebler/range-v3
0013 //
0014 #ifndef RANGES_V3_ALGORITHM_UNSTABLE_REMOVE_IF_HPP
0015 #define RANGES_V3_ALGORITHM_UNSTABLE_REMOVE_IF_HPP
0016
0017 #include <functional>
0018 #include <utility>
0019
0020 #include <concepts/concepts.hpp>
0021
0022 #include <range/v3/range_fwd.hpp>
0023
0024 #include <range/v3/algorithm/find_if.hpp>
0025 #include <range/v3/algorithm/find_if_not.hpp>
0026 #include <range/v3/functional/identity.hpp>
0027 #include <range/v3/iterator/concepts.hpp>
0028 #include <range/v3/iterator/operations.hpp>
0029 #include <range/v3/iterator/reverse_iterator.hpp>
0030 #include <range/v3/range/access.hpp>
0031 #include <range/v3/range/concepts.hpp>
0032 #include <range/v3/utility/move.hpp>
0033 #include <range/v3/utility/static_const.hpp>
0034
0035 #include <range/v3/detail/prologue.hpp>
0036
0037 namespace ranges
0038 {
0039     /// \addtogroup group-algorithms
0040     /// @{
0041
0042     /// unstable_remove have O(1) complexity for each element remove, unlike remove O(n)
0043     /// [for worst case]. Each erased element overwritten (moved in) with last one.
0044     /// unstable_remove_if does not preserve relative element order.
0045     RANGES_FUNC_BEGIN(unstable_remove_if)
0046
0047         /// \brief function template \c unstable_remove_if
0048         template(typename I, typename C, typename P = identity)(
0049             requires bidirectional_iterator<I> AND permutable<I> AND
0050             indirect_unary_predicate<C, projected<I, P>>)
0051         constexpr I RANGES_FUNC(unstable_remove_if)(I first, I last, C pred, P proj = {})
0052         {
0053             while(true)
0054             {
0055                 first = find_if(std::move(first), last, ranges::ref(pred), ranges::ref(proj));
0056                 if(first == last)
0057                     return first;
0058
0059                 last = next(find_if_not(make_reverse_iterator(std::move(last)),
0060                                         make_reverse_iterator(next(first)),
0061                                         ranges::ref(pred),
0062                                         ranges::ref(proj)))
0063                            .base();
0064                 if(first == last)
0065                     return first;
0066
0067                 *first = iter_move(last);
0068
0069                 // discussion here: https://github.com/ericniebler/range-v3/issues/988
0070                 ++first;
0071             }
0072         }
0073
0074         /// \overload
0075         template(typename Rng, typename C, typename P = identity)(
0076             requires bidirectional_range<Rng> AND common_range<Rng> AND
0077             permutable<iterator_t<Rng>> AND
0078             indirect_unary_predicate<C, projected<iterator_t<Rng>, P>>)
0079         constexpr borrowed_iterator_t<Rng> //
0080         RANGES_FUNC(unstable_remove_if)(Rng && rng, C pred, P proj = P{}) //
0081         {
0082             return (*this)(begin(rng), end(rng), std::move(pred), std::move(proj));
0083         }
0084
0085     RANGES_FUNC_END(unstable_remove_if)
0086     /// @}
0087 } // namespace ranges
0088
0089 #include <range/v3/detail/epilogue.hpp>
0090
0091 #endif // RANGES_V3_ALGORITHM_UNSTABLE_REMOVE_IF_HPP