[libc++][ranges] Implement `ranges::remove_copy{, _if}`.
Co-authored-by: Hui Xie <hui.xie1990@gmail.com>
Differential Revision: https://reviews.llvm.org/D130599
NOKEYCHECK=True
GitOrigin-RevId: 760d2b462c04537d119d76d3cc37d2cb53774a05
diff --git a/include/__algorithm/ranges_remove_copy.h b/include/__algorithm/ranges_remove_copy.h
index 16e9009..a8144ce 100644
--- a/include/__algorithm/ranges_remove_copy.h
+++ b/include/__algorithm/ranges_remove_copy.h
@@ -10,19 +10,16 @@
#define _LIBCPP___ALGORITHM_RANGES_REMOVE_COPY_H
#include <__algorithm/in_out_result.h>
-#include <__algorithm/make_projected.h>
-#include <__algorithm/remove_copy.h>
+#include <__algorithm/ranges_remove_copy_if.h>
#include <__config>
#include <__functional/identity.h>
#include <__functional/invoke.h>
#include <__functional/ranges_operations.h>
#include <__iterator/concepts.h>
-#include <__iterator/iterator_traits.h>
#include <__iterator/projected.h>
#include <__ranges/access.h>
#include <__ranges/concepts.h>
#include <__ranges/dangling.h>
-#include <__utility/forward.h>
#include <__utility/move.h>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -40,32 +37,30 @@
namespace __remove_copy {
-struct __fn {
+ struct __fn {
+ template <input_iterator _InIter,
+ sentinel_for<_InIter> _Sent,
+ weakly_incrementable _OutIter,
+ class _Type,
+ class _Proj = identity>
+ requires indirectly_copyable<_InIter, _OutIter> &&
+ indirect_binary_predicate<ranges::equal_to, projected<_InIter, _Proj>, const _Type*>
+ _LIBCPP_HIDE_FROM_ABI constexpr remove_copy_result<_InIter, _OutIter>
+ operator()(_InIter __first, _Sent __last, _OutIter __result, const _Type& __value, _Proj __proj = {}) const {
+ auto __pred = [&](auto&& __val) { return __value == __val; };
+ return ranges::__remove_copy_if_impl(std::move(__first), std::move(__last), std::move(__result), __pred, __proj);
+ }
- template <input_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter, class _Type,
- class _Proj = identity>
- requires indirectly_copyable<_InIter, _OutIter> &&
- indirect_binary_predicate<ranges::equal_to, projected<_InIter, _Proj>, const _Type*>
- _LIBCPP_HIDE_FROM_ABI constexpr
- remove_copy_result<_InIter, _OutIter>
- operator()(_InIter __first, _Sent __last, _OutIter __result, const _Type& __value, _Proj __proj = {}) const {
- // TODO: implement
- (void)__first; (void)__last; (void)__result; (void)__value; (void)__proj;
- return {};
- }
-
- template <input_range _Range, weakly_incrementable _OutIter, class _Type, class _Proj = identity>
- requires indirectly_copyable<iterator_t<_Range>, _OutIter> &&
- indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Type*>
- _LIBCPP_HIDE_FROM_ABI constexpr
- remove_copy_result<borrowed_iterator_t<_Range>, _OutIter>
- operator()(_Range&& __range, _OutIter __result, const _Type& __value, _Proj __proj = {}) const {
- // TODO: implement
- (void)__range; (void)__result; (void)__value; (void)__proj;
- return {};
- }
-
-};
+ template <input_range _Range, weakly_incrementable _OutIter, class _Type, class _Proj = identity>
+ requires indirectly_copyable<iterator_t<_Range>, _OutIter> &&
+ indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Type*>
+ _LIBCPP_HIDE_FROM_ABI constexpr remove_copy_result<borrowed_iterator_t<_Range>, _OutIter>
+ operator()(_Range&& __range, _OutIter __result, const _Type& __value, _Proj __proj = {}) const {
+ auto __pred = [&](auto&& __val) { return __value == __val; };
+ return ranges::__remove_copy_if_impl(
+ ranges::begin(__range), ranges::end(__range), std::move(__result), __pred, __proj);
+ }
+ };
} // namespace __remove_copy
diff --git a/include/__algorithm/ranges_remove_copy_if.h b/include/__algorithm/ranges_remove_copy_if.h
index 4eafe42..3f56693 100644
--- a/include/__algorithm/ranges_remove_copy_if.h
+++ b/include/__algorithm/ranges_remove_copy_if.h
@@ -38,33 +38,43 @@
template <class _InIter, class _OutIter>
using remove_copy_if_result = in_out_result<_InIter, _OutIter>;
+template <class _InIter, class _Sent, class _OutIter, class _Proj, class _Pred>
+_LIBCPP_HIDE_FROM_ABI constexpr in_out_result<_InIter, _OutIter>
+__remove_copy_if_impl(_InIter __first, _Sent __last, _OutIter __result, _Pred& __pred, _Proj& __proj) {
+ for (; __first != __last; ++__first) {
+ if (!std::invoke(__pred, std::invoke(__proj, *__first))) {
+ *__result = *__first;
+ ++__result;
+ }
+ }
+ return {std::move(__first), std::move(__result)};
+}
+
namespace __remove_copy_if {
-struct __fn {
+ struct __fn {
+ template <input_iterator _InIter,
+ sentinel_for<_InIter> _Sent,
+ weakly_incrementable _OutIter,
+ class _Proj = identity,
+ indirect_unary_predicate<projected<_InIter, _Proj>> _Pred>
+ requires indirectly_copyable<_InIter, _OutIter>
+ _LIBCPP_HIDE_FROM_ABI constexpr remove_copy_if_result<_InIter, _OutIter>
+ operator()(_InIter __first, _Sent __last, _OutIter __result, _Pred __pred, _Proj __proj = {}) const {
+ return ranges::__remove_copy_if_impl(std::move(__first), std::move(__last), std::move(__result), __pred, __proj);
+ }
- template <input_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter,
- class _Proj = identity, indirect_unary_predicate<projected<_InIter, _Proj>> _Pred>
- requires indirectly_copyable<_InIter, _OutIter>
- _LIBCPP_HIDE_FROM_ABI constexpr
- remove_copy_if_result<_InIter, _OutIter>
- operator()(_InIter __first, _Sent __last, _OutIter __result, _Pred __pred, _Proj __proj = {}) const {
- // TODO: implement
- (void)__first; (void)__last; (void)__result; (void)__pred; (void)__proj;
- return {};
- }
-
- template <input_range _Range, weakly_incrementable _OutIter, class _Proj = identity,
- indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
- requires indirectly_copyable<iterator_t<_Range>, _OutIter>
- _LIBCPP_HIDE_FROM_ABI constexpr
- remove_copy_if_result<borrowed_iterator_t<_Range>, _OutIter>
- operator()(_Range&& __range, _OutIter __result, _Pred __pred, _Proj __proj = {}) const {
- // TODO: implement
- (void)__range; (void)__result; (void)__pred; (void)__proj;
- return {};
- }
-
-};
+ template <input_range _Range,
+ weakly_incrementable _OutIter,
+ class _Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
+ requires indirectly_copyable<iterator_t<_Range>, _OutIter>
+ _LIBCPP_HIDE_FROM_ABI constexpr remove_copy_if_result<borrowed_iterator_t<_Range>, _OutIter>
+ operator()(_Range&& __range, _OutIter __result, _Pred __pred, _Proj __proj = {}) const {
+ return ranges::__remove_copy_if_impl(
+ ranges::begin(__range), ranges::end(__range), std::move(__result), __pred, __proj);
+ }
+ };
} // namespace __remove_copy_if
diff --git a/include/algorithm b/include/algorithm
index 92e9327..b4e1b82 100644
--- a/include/algorithm
+++ b/include/algorithm
@@ -912,6 +912,38 @@
indirectly_copyable_storable<iterator_t<R>, O>)
constexpr unique_copy_result<borrowed_iterator_t<R>, O>
unique_copy(R&& r, O result, C comp = {}, Proj proj = {}); // Since C++20
+
+ template<class I, class O>
+ using remove_copy_result = in_out_result<I, O>; // Since C++20
+
+ template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class T,
+ class Proj = identity>
+ indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
+ constexpr remove_copy_result<I, O>
+ remove_copy(I first, S last, O result, const T& value, Proj proj = {}); // Since C++20
+
+ template<input_range R, weakly_incrementable O, class T, class Proj = identity>
+ requires indirectly_copyable<iterator_t<R>, O> &&
+ indirect_binary_predicate<ranges::equal_to,
+ projected<iterator_t<R>, Proj>, const T*>
+ constexpr remove_copy_result<borrowed_iterator_t<R>, O>
+ remove_copy(R&& r, O result, const T& value, Proj proj = {}); // Since C++20
+
+ template<class I, class O>
+ using remove_copy_if_result = in_out_result<I, O>; // Since C++20
+
+ template<input_iterator I, sentinel_for<I> S, weakly_incrementable O,
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
+ requires indirectly_copyable<I, O>
+ constexpr remove_copy_if_result<I, O>
+ remove_copy_if(I first, S last, O result, Pred pred, Proj proj = {}); // Since C++20
+
+ template<input_range R, weakly_incrementable O, class Proj = identity,
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+ requires indirectly_copyable<iterator_t<R>, O>
+ constexpr remove_copy_if_result<borrowed_iterator_t<R>, O>
+ remove_copy_if(R&& r, O result, Pred pred, Proj proj = {}); // Since C++20
+
}
constexpr bool // constexpr in C++20
@@ -1694,6 +1726,8 @@
#include <__algorithm/ranges_pop_heap.h>
#include <__algorithm/ranges_push_heap.h>
#include <__algorithm/ranges_remove.h>
+#include <__algorithm/ranges_remove_copy.h>
+#include <__algorithm/ranges_remove_copy_if.h>
#include <__algorithm/ranges_remove_if.h>
#include <__algorithm/ranges_replace.h>
#include <__algorithm/ranges_replace_if.h>