[gcc(refs/users/ppalka/heads/libstdcxx-constrained-algos)] Improve ranges::copy and implement ranges::move in terms of it
Patrick Palka
ppalka@gcc.gnu.org
Mon Jan 20 15:35:00 GMT 2020
https://gcc.gnu.org/g:994fabdda8fb42ead6c4fb0d205ed3a45867989a
commit 994fabdda8fb42ead6c4fb0d205ed3a45867989a
Author: Patrick Palka <ppalka@gcc.gnu.org>
Date: Sun Jan 19 22:52:45 2020 -0500
Improve ranges::copy and implement ranges::move in terms of it
The ranges::copy implementation now unwraps move_iterators and normal_iterators,
and performs a move instead of a copy when appropriate. This also allows
ranges::move to be defined in terms of ranges::copy.
Diff:
---
libstdc++-v3/include/bits/ranges_algo.h | 102 +++++++++++--
.../testsuite/25_algorithms/copy/constrained.cc | 87 +++++++++++-
.../testsuite/25_algorithms/move/constrained.cc | 157 +++++++++++++++++++++
3 files changed, 333 insertions(+), 13 deletions(-)
diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index ea76cac2..208fdb8 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -812,14 +812,22 @@ namespace ranges
}
};
- template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
+ template<class _Iter, class _Out>
+ using move_result = copy_result<_Iter, _Out>;
+
+ template<bool _IsMove,
+ input_iterator _Iter, sentinel_for<_Iter> _Sent,
weakly_incrementable _Out>
- requires indirectly_copyable<_Iter, _Out>
- constexpr copy_result<_Iter, _Out>
- copy(_Iter __first, _Sent __last, _Out __result)
+ requires (_IsMove
+ ? indirectly_movable<_Iter, _Out>
+ : indirectly_copyable<_Iter, _Out>)
+ constexpr conditional_t<_IsMove,
+ move_result<_Iter, _Out>,
+ copy_result<_Iter, _Out>>
+ __copy_or_move(_Iter __first, _Sent __last, _Out __result)
{
// TODO: implement more specializations to be at least on par with
- // std::copy.
+ // std::copy/std::move.
if constexpr (sized_sentinel_for<_Sent, _Iter>)
{
using _ValueTypeI = iterator_traits<_Iter>::value_type;
@@ -832,24 +840,70 @@ namespace ranges
if constexpr (__use_memmove)
{
- static_assert(is_copy_assignable_v<_ValueTypeI>);
+ static_assert(_IsMove
+ ? is_move_assignable_v<_ValueTypeI>
+ : is_copy_assignable_v<_ValueTypeI>);
auto __num = __last - __first;
if (__num)
- std::__memmove<false>(__result, __first, __num);
+ std::__memmove<_IsMove>(__result, __first, __num);
return {__first + __num, __result + __num};
}
else
{
for (auto __n = __last - __first; __n > 0; --__n)
- *__result++ = *__first++;
- return {__last, __result};
+ {
+ if constexpr (_IsMove)
+ *__result = std::move(*__first);
+ else
+ *__result = *__first;
+ __first++;
+ __result++;
+ }
+ return {__first, __result};
}
}
else
{
while (__first != __last)
- *__result++ = *__first++;
- return {__last, __result};
+ {
+ if constexpr (_IsMove)
+ *__result = std::move(*__first);
+ else
+ *__result = *__first;
+ __first++;
+ __result++;
+ }
+ return {__first, __result};
+ }
+ }
+
+ template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
+ weakly_incrementable _Out>
+ requires indirectly_copyable<_Iter, _Out>
+ constexpr copy_result<_Iter, _Out>
+ copy(_Iter __first, _Sent __last, _Out __result)
+ {
+ constexpr bool __move_iterator_p = __is_move_iterator<_Iter>::__value;
+ if constexpr (__move_iterator_p)
+ {
+ auto __first_base = __first.base();
+ auto __last_base = __last.base();
+ auto [__in,__out]
+ = ranges::__copy_or_move<true>(std::__niter_base(__first_base),
+ std::__niter_base(__last_base),
+ std::__niter_base(__result));
+ auto __wrapped_in = std::__niter_wrap(__first_base, __in);
+ auto __wrapped_out = std::__niter_wrap(__result, __out);
+ return {move_iterator{__wrapped_in}, __wrapped_out};
+ }
+ else
+ {
+ auto [__in,__out]
+ = ranges::__copy_or_move<false>(std::__niter_base(__first),
+ std::__niter_base(__last),
+ std::__niter_base(__result));
+ return {std::__niter_wrap(__first, __in),
+ std::__niter_wrap(__result, __out)};
}
}
@@ -862,6 +916,32 @@ namespace ranges
std::move(__result));
}
+ template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
+ weakly_incrementable _Out>
+ requires indirectly_movable<_Iter, _Out>
+ constexpr move_result<_Iter, _Out>
+ move(_Iter __first, _Sent __last, _Out __result)
+ {
+ if constexpr (__is_move_iterator<_Iter>::__value)
+ return ranges::copy(__first, __last, __result);
+ else
+ {
+ auto [__in, __out]
+ = ranges::copy(move_iterator<_Iter>{__first},
+ move_sentinel<_Sent>{__last}, __result);
+ return {__in.base(), __out};
+ }
+ }
+
+ template<input_range _Range, weakly_incrementable _Out>
+ requires indirectly_movable<iterator_t<_Range>, _Out>
+ constexpr move_result<safe_iterator_t<_Range>, _Out>
+ move(_Range&& __r, _Out __result)
+ {
+ return ranges::move(ranges::begin(__r), ranges::end(__r),
+ std::move(__result));
+ }
+
} // namespace ranges
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/copy/constrained.cc
index 3400d26..f1b94ff 100644
--- a/libstdc++-v3/testsuite/25_algorithms/copy/constrained.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/constrained.cc
@@ -71,9 +71,23 @@ struct X
constexpr X (int a) : i(a) { }
};
-constexpr bool
+void
test02()
{
+ int x[] = { {2}, {2}, {6}, {8}, {10} };
+ X y[] = { {2}, {6}, {8}, {10}, {11}, {2} };
+ int z[] = { {2}, {2}, {6}, {8}, {10} };
+ auto [in, out] = ranges::copy(x, y);
+ VERIFY( ranges::equal(x, x+5, y, y+5, {}, {}, &X::i) );
+ VERIFY( in == x+5 );
+ VERIFY( out == y+5 );
+ VERIFY( y[5].i == 2 );
+ VERIFY( ranges::equal(x, z) );
+}
+
+constexpr bool
+test03()
+{
bool ok = true;
int x[] = { {2}, {2}, {6}, {8}, {10} };
X y[] = { {2}, {6}, {8}, {10}, {11}, {2} };
@@ -87,10 +101,79 @@ test02()
return ok;
}
+struct Y
+{
+ int i;
+ int moved = 0;
+
+ constexpr Y(int a) : i(a) { }
+
+ constexpr Y(const Y&) = delete;
+ constexpr Y& operator=(const Y&) = delete;
+
+ constexpr Y(Y&& other)
+ {
+ *this = std::move(other);
+ }
+
+ constexpr Y&
+ operator=(Y&& other)
+ {
+ other.moved++;
+ i = other.i;
+ return *this;
+ }
+
+ friend constexpr bool
+ operator==(const Y& a, const Y& b)
+ { return a.i == b.i; }
+};
+
+void
+test04()
+{
+ Y x[7] = { 1, 2, 3, 4, 5, 6, 7 };
+ Y y[7] = { 0, 0, 0, 0, 0, 0, 0 };
+ Y z[7] = { 1, 2, 3, 4, 5, 6, 7 };
+ auto [in, out] = ranges::copy(std::move_iterator{ranges::begin(x)},
+ std::move_sentinel{ranges::end(x)},
+ ranges::begin(y));
+ VERIFY( ranges::equal(x, y) && in.base() == x+7 && out == y+7 );
+ VERIFY( ranges::equal(x, z) );
+ for (const auto& v : x)
+ VERIFY( v.moved == 1 );
+ for (const auto& v : y)
+ VERIFY( v.moved == 0 );
+}
+
+constexpr bool
+test05()
+{
+ bool ok = true;
+ Y x[7] = { 1, 2, 3, 4, 5, 6, 7 };
+ Y y[7] = { 0, 0, 0, 0, 0, 0, 0 };
+ Y z[7] = { 1, 2, 3, 4, 5, 6, 7 };
+ auto [in, out] = ranges::copy(std::move_iterator{ranges::begin(x)},
+ std::move_sentinel{ranges::end(x)},
+ ranges::begin(y));
+ ok &= ranges::equal(x, y);
+ ok &= in.base() == x+7;
+ ok &= out == y+7;
+ ok &= ranges::equal(x, z);
+ for (const auto& v : x)
+ ok &= v.moved == 1;
+ for (const auto& v : y)
+ ok &= v.moved == 0;
+ return ok;
+}
+
int
main()
{
test01();
- static_assert(test02());
+ test02();
+ static_assert(test03());
+ test04();
+ static_assert(test05());
}
diff --git a/libstdc++-v3/testsuite/25_algorithms/move/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/move/constrained.cc
new file mode 100644
index 0000000..7ec1e78
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/move/constrained.cc
@@ -0,0 +1,157 @@
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++2a" }
+// { dg-do run { target c++2a } }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::test_range;
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::forward_iterator_wrapper;
+using __gnu_test::bidirectional_iterator_wrapper;
+
+namespace ranges = std::ranges;
+
+struct X
+{
+ int i;
+ int moved = 0;
+
+ constexpr X(int a) : i(a) { }
+
+ constexpr X(const X&) = delete;
+ constexpr X& operator=(const X&) = delete;
+
+ constexpr X(X&& other)
+ {
+ *this = std::move(other);
+ }
+
+ constexpr X&
+ operator=(X&& other)
+ {
+ other.moved++;
+ i = other.i;
+ return *this;
+ }
+
+ friend constexpr bool
+ operator==(const X& a, const X& b)
+ { return a.i == b.i; }
+};
+
+void
+test01()
+{
+ {
+ X x[7] = { 1, 2, 3, 4, 5, 6, 7 };
+ X y[7] = { 0, 0, 0, 0, 0, 0, 0 };
+ X z[7] = { 1, 2, 3, 4, 5, 6, 7 };
+ auto [in, out] = ranges::move(x, y);
+ VERIFY( ranges::equal(x, y) && in == x+7 && out == y+7 );
+ VERIFY( ranges::equal(x, z) );
+ }
+
+ {
+ int x[3] = { 1, 2, 3 };
+ char y[4] = { 0 };
+ int z[3] = { 1, 2, 3 };
+ test_container<int, forward_iterator_wrapper> cx(x);
+ test_container<char, forward_iterator_wrapper> cy(y);
+ auto [in, out] = ranges::move(x, y);
+ VERIFY( ranges::equal(x, x+3, y, y+3) && in == x+3 && out == y+3 );
+ VERIFY( ranges::equal(x, z) );
+ }
+
+ {
+ char x[3] = { 1, 2, 3 };
+ int y[4] = { 0 };
+ int z[3] = { 1, 2, 3 };
+ test_range<char, forward_iterator_wrapper> cx(x);
+ test_range<int, forward_iterator_wrapper> cy(y);
+ auto [in, out] = ranges::move(x, y);
+ VERIFY( ranges::equal(x, x+3, y, y+3) && in == x+3 && out == y+3 );
+ VERIFY( ranges::equal(x, z) );
+ }
+}
+
+void
+test02()
+{
+ X x[] = { {2}, {2}, {6}, {8}, {10} };
+ X y[] = { {2}, {6}, {8}, {10}, {11}, {2} };
+ X z[] = { {2}, {2}, {6}, {8}, {10} };
+ auto [in, out] = ranges::move(x, y);
+ VERIFY( ranges::equal(x, x+5, y, y+5) );
+ VERIFY( in == x+5 );
+ VERIFY( out == y+5 );
+ VERIFY( y[5].i == 2 );
+ VERIFY( ranges::equal(x, z) );
+ VERIFY( ranges::count(x, 1, &X::moved) == 5 );
+ VERIFY( ranges::count(y, 0, &X::moved) == 6 );
+}
+
+constexpr bool
+test03()
+{
+ bool ok = true;
+ X x[] = { {2}, {2}, {6}, {8}, {10} };
+ X y[] = { {2}, {6}, {8}, {10}, {11}, {2} };
+ X z[] = { {2}, {2}, {6}, {8}, {10} };
+ auto [in, out] = ranges::move(x, y);
+ ok &= ranges::equal(x, x+5, y, y+5);
+ ok &= (in == x+5);
+ ok &= (out == y+5);
+ ok &= (y[5].i == 2);
+ ok &= ranges::equal(x, z);
+ ok &= ranges::count(x, 1, &X::moved) == 5;
+ ok &= ranges::count(y, 0, &X::moved) == 6;
+ return ok;
+}
+
+void
+test04()
+{
+ X x[] = { {2}, {2}, {6}, {8}, {10} };
+ X y[] = { {2}, {6}, {8}, {10}, {11}, {2} };
+ X z[] = { {2}, {2}, {6}, {8}, {10} };
+ auto [in, out] = ranges::move(std::move_iterator{ranges::begin(x)},
+ std::move_iterator{ranges::end(x)},
+ ranges::begin(y));
+ VERIFY( ranges::equal(x, x+5, y, y+5) );
+ VERIFY( in.base() == x+5 );
+ VERIFY( out == y+5 );
+ VERIFY( y[5].i == 2 );
+ VERIFY( ranges::equal(x, z) );
+ VERIFY( ranges::count(x, 1, &X::moved) == 5 );
+ VERIFY( ranges::count(y, 0, &X::moved) == 6 );
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ static_assert(test03());
+ test04();
+}
+
+
More information about the Libstdc++-cvs
mailing list