This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] libstdc++: P0769R2 Add shift to <algorithm>


This patch adds std::shift_left and std::shift_right.  Alhough these are
STL-style algos, they are nonetheless placed in <bits/ranges_algo.h> because
they make use of some functions in the ranges namespace that are more easily
reachable from <bits/ranges_algo.h> than from <bits/stl_algo.h>, namely
ranges::next and ranges::swap_ranges.

This implementation of std::shift_right for non-bidirectional iterators deviates
from the reference implementation a bit.  The main difference is that this
implementation is significantly simpler, and yet saves around n/2 additional
iterator increments and n/2 iter_moves at the cost of around n/2 additional
iter_swaps (where n is the shift amount).

libstdc++-v3/ChangeLog:

	P0769R2 Add shift to <algorithm>
	* include/bits/ranges_algo.h (shift_left, shift_right): New.
	* testsuite/25_algorithms/shift_left/1.cc: New test.
	* testsuite/25_algorithms/shift_right/1.cc: New test.
---
 libstdc++-v3/include/bits/ranges_algo.h       | 48 +++++++++++++
 .../testsuite/25_algorithms/shift_left/1.cc   | 67 +++++++++++++++++++
 .../testsuite/25_algorithms/shift_right/1.cc  | 67 +++++++++++++++++++
 3 files changed, 182 insertions(+)
 create mode 100644 libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc
 create mode 100644 libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc

diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 7de1072abf0..c36afc6e19b 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -3683,6 +3683,54 @@ namespace ranges
   inline constexpr __prev_permutation_fn prev_permutation{};
 
 } // namespace ranges
+
+  template<class ForwardIterator>
+    constexpr ForwardIterator
+    shift_left(ForwardIterator __first, ForwardIterator __last,
+	       typename iterator_traits<ForwardIterator>::difference_type __n)
+    {
+      __glibcxx_assert(__n >= 0);
+      if (__n == 0)
+	return __last;
+
+      auto __mid = ranges::next(__first, __n, __last);
+      if (__mid == __last)
+	return __first;
+      return std::move(std::move(__mid), std::move(__last), std::move(__first));
+    }
+
+  template<class ForwardIterator>
+    constexpr ForwardIterator
+    shift_right(ForwardIterator __first, ForwardIterator __last,
+		typename iterator_traits<ForwardIterator>::difference_type __n)
+    {
+      __glibcxx_assert(__n >= 0);
+      if (__n == 0)
+	return __first;
+
+      using _Cat = iterator_traits<ForwardIterator>::iterator_category;
+      if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
+	{
+	  auto __mid = ranges::next(__last, -__n, __first);
+	  if (__mid == __first)
+	    return __last;
+	  return std::move_backward(std::move(__first), std::move(__mid),
+				    std::move(__last));
+	}
+      else
+	{
+	  auto __result = ranges::next(__first, __n, __last);
+	  if (__result == __last)
+	    return __last;
+	  auto __dest = __result;
+	  do
+	    __dest = ranges::swap_ranges(__first, __result,
+					 std::move(__dest), __last).in2;
+	  while (__dest != __last);
+	  return __result;
+	}
+    }
+
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace std
 #endif // concepts
diff --git a/libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc b/libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc
new file mode 100644
index 00000000000..9bdb843adbc
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/shift_left/1.cc
@@ -0,0 +1,67 @@
+// 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::forward_iterator_wrapper;
+using __gnu_test::bidirectional_iterator_wrapper;
+using __gnu_test::random_access_iterator_wrapper;
+
+template<int K, template<typename> typename Wrapper>
+void
+test01()
+{
+  static_assert(K == 10 || K == 11);
+  for (int i = 0; i < 15; i++)
+    {
+      int x[K];
+      for (int t = 0; t < K; t++)
+	x[t] = t;
+      test_container<int, Wrapper> cx(x);
+      auto out = std::shift_left(cx.begin(), cx.end(), i);
+      if (i < K)
+	{
+	  VERIFY( out.ptr == x+(K-i) );
+	  for (int j = i; j < K-i; j++)
+	    VERIFY( x[j] == i+j );
+	}
+      else
+	{
+	  VERIFY( out.ptr == x );
+	  for (int j = 0; j < K; j++)
+	    VERIFY( x[j] == j );
+	}
+    }
+}
+
+int
+main()
+{
+  test01<10, forward_iterator_wrapper>();
+  test01<10, bidirectional_iterator_wrapper>();
+  test01<10, random_access_iterator_wrapper>();
+
+  test01<11, forward_iterator_wrapper>();
+  test01<11, bidirectional_iterator_wrapper>();
+  test01<11, random_access_iterator_wrapper>();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc b/libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc
new file mode 100644
index 00000000000..3ce05ed287b
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/shift_right/1.cc
@@ -0,0 +1,67 @@
+// 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::forward_iterator_wrapper;
+using __gnu_test::bidirectional_iterator_wrapper;
+using __gnu_test::random_access_iterator_wrapper;
+
+template<int K, template<typename> typename Wrapper>
+void
+test01()
+{
+  static_assert(K == 10 || K == 11);
+  for (int i = 0; i < 15; i++)
+    {
+      int x[K];
+      for (int t = 0; t < K; t++)
+	x[t] = t;
+      test_container<int, Wrapper> cx(x);
+      auto out = std::shift_right(cx.begin(), cx.end(), i);
+      if (i < K)
+	{
+	  VERIFY( out.ptr == x+i );
+	  for (int j = i; j < K; j++)
+	    VERIFY( x[j] == j-i );
+	}
+      else
+	{
+	  VERIFY( out.ptr == x+K );
+	  for (int j = 0; j < K; j++)
+	    VERIFY( x[j] == j );
+	}
+    }
+}
+
+int
+main()
+{
+  test01<10, forward_iterator_wrapper>();
+  test01<10, bidirectional_iterator_wrapper>();
+  test01<10, random_access_iterator_wrapper>();
+
+  test01<11, forward_iterator_wrapper>();
+  test01<11, bidirectional_iterator_wrapper>();
+  test01<11, random_access_iterator_wrapper>();
+}
-- 
2.25.1.291.ge68e29171c


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]