This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] libstdc++/58357 DR 488 std::rotate should return an iterator
- From: Jonathan Wakely <jwakely at redhat dot com>
- To: libstdc++ at gcc dot gnu dot org, gcc-patches at gcc dot gnu dot org
- Date: Sat, 17 Jan 2015 03:16:07 +0000
- Subject: [patch] libstdc++/58357 DR 488 std::rotate should return an iterator
- Authentication-results: sourceware.org; auth=none
http://cplusplus.github.io/LWG/lwg-defects.html#488
Tested x86_64-linux, committed to trunk.
commit a5ae94562335d47358186f76ca71cc6cf0560ed8
Author: Jonathan Wakely <jwakely@redhat.com>
Date: Tue Sep 23 00:11:26 2014 +0100
DR 488
PR libstdc++/58357
* include/bits/algorithmfwd.h (rotate): Return an iterator.
* include/bits/stl_algo.h (rotate, __rotate): Likewise.
* testsuite/25_algorithms/rotate/dr488.cc: New.
* testsuite/25_algorithms/rotate/check_type.cc: Adjust function type.
* testsuite/25_algorithms/rotate/requirements/explicit_instantiation/
2.cc: Likewise.
* testsuite/25_algorithms/rotate/requirements/explicit_instantiation/
pod.cc: Likewise.
diff --git a/libstdc++-v3/include/bits/algorithmfwd.h b/libstdc++-v3/include/bits/algorithmfwd.h
index 283c5e6..11361bb 100644
--- a/libstdc++-v3/include/bits/algorithmfwd.h
+++ b/libstdc++-v3/include/bits/algorithmfwd.h
@@ -531,7 +531,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
reverse_copy(_BIter, _BIter, _OIter);
template<typename _FIter>
- void
+ _FIter
rotate(_FIter, _FIter, _FIter);
template<typename _FIter, typename _OIter>
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index da642e6..3325b94 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -1239,14 +1239,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
/// This is a helper function for the rotate algorithm.
template<typename _ForwardIterator>
- void
+ _ForwardIterator
__rotate(_ForwardIterator __first,
_ForwardIterator __middle,
_ForwardIterator __last,
forward_iterator_tag)
{
- if (__first == __middle || __last == __middle)
- return;
+ if (__first == __middle)
+ return __last;
+ else if (__last == __middle)
+ return __first;
_ForwardIterator __first2 = __middle;
do
@@ -1259,6 +1261,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
while (__first2 != __last);
+ _ForwardIterator __ret = __first;
+
__first2 = __middle;
while (__first2 != __last)
@@ -1271,11 +1275,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
else if (__first2 == __last)
__first2 = __middle;
}
+ return __ret;
}
/// This is a helper function for the rotate algorithm.
template<typename _BidirectionalIterator>
- void
+ _BidirectionalIterator
__rotate(_BidirectionalIterator __first,
_BidirectionalIterator __middle,
_BidirectionalIterator __last,
@@ -1285,8 +1290,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
_BidirectionalIterator>)
- if (__first == __middle || __last == __middle)
- return;
+ if (__first == __middle)
+ return __last;
+ else if (__last == __middle)
+ return __first;
std::__reverse(__first, __middle, bidirectional_iterator_tag());
std::__reverse(__middle, __last, bidirectional_iterator_tag());
@@ -1298,14 +1305,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
if (__first == __middle)
- std::__reverse(__middle, __last, bidirectional_iterator_tag());
+ {
+ std::__reverse(__middle, __last, bidirectional_iterator_tag());
+ return __last;
+ }
else
- std::__reverse(__first, __middle, bidirectional_iterator_tag());
+ {
+ std::__reverse(__first, __middle, bidirectional_iterator_tag());
+ return __first;
+ }
}
/// This is a helper function for the rotate algorithm.
template<typename _RandomAccessIterator>
- void
+ _RandomAccessIterator
__rotate(_RandomAccessIterator __first,
_RandomAccessIterator __middle,
_RandomAccessIterator __last,
@@ -1315,8 +1328,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
- if (__first == __middle || __last == __middle)
- return;
+ if (__first == __middle)
+ return __last;
+ else if (__last == __middle)
+ return __first;
typedef typename iterator_traits<_RandomAccessIterator>::difference_type
_Distance;
@@ -1329,10 +1344,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__k == __n - __k)
{
std::swap_ranges(__first, __middle, __middle);
- return;
+ return __middle;
}
_RandomAccessIterator __p = __first;
+ _RandomAccessIterator __ret = __first + (__last - __middle);
for (;;)
{
@@ -1343,7 +1359,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_ValueType __t = _GLIBCXX_MOVE(*__p);
_GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
*(__p + __n - 1) = _GLIBCXX_MOVE(__t);
- return;
+ return __ret;
}
_RandomAccessIterator __q = __p + __k;
for (_Distance __i = 0; __i < __n - __k; ++ __i)
@@ -1354,7 +1370,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
__n %= __k;
if (__n == 0)
- return;
+ return __ret;
std::swap(__n, __k);
__k = __n - __k;
}
@@ -1366,7 +1382,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
_GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
*__p = _GLIBCXX_MOVE(__t);
- return;
+ return __ret;
}
_RandomAccessIterator __q = __p + __n;
__p = __q - __k;
@@ -1378,19 +1394,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
__n %= __k;
if (__n == 0)
- return;
+ return __ret;
std::swap(__n, __k);
}
}
}
+ // _GLIBCXX_RESOLVE_LIB_DEFECTS
+ // DR 488. rotate throws away useful information
/**
* @brief Rotate the elements of a sequence.
* @ingroup mutating_algorithms
* @param __first A forward iterator.
* @param __middle A forward iterator.
* @param __last A forward iterator.
- * @return Nothing.
+ * @return first + (last - middle).
*
* Rotates the elements of the range @p [__first,__last) by
* @p (__middle - __first) positions so that the element at @p __middle
@@ -1406,7 +1424,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
* for each @p n in the range @p [0,__last-__first).
*/
template<typename _ForwardIterator>
- inline void
+ inline _ForwardIterator
rotate(_ForwardIterator __first, _ForwardIterator __middle,
_ForwardIterator __last)
{
@@ -1416,8 +1434,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_valid_range(__first, __middle);
__glibcxx_requires_valid_range(__middle, __last);
- std::__rotate(__first, __middle, __last,
- std::__iterator_category(__first));
+ return std::__rotate(__first, __middle, __last,
+ std::__iterator_category(__first));
}
/**
diff --git a/libstdc++-v3/testsuite/25_algorithms/rotate/check_type.cc b/libstdc++-v3/testsuite/25_algorithms/rotate/check_type.cc
index f464364..9d4c382 100644
--- a/libstdc++-v3/testsuite/25_algorithms/rotate/check_type.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/rotate/check_type.cc
@@ -26,19 +26,19 @@ struct X { };
bool operator<(X,X) { return true;}
-void
+__gnu_test::forward_iterator_wrapper<X>
test1(__gnu_test::forward_iterator_wrapper<X>& begin,
__gnu_test::forward_iterator_wrapper<X>& middle,
__gnu_test::forward_iterator_wrapper<X>& end)
{ return std::rotate(begin,middle,end); }
-void
+__gnu_test::bidirectional_iterator_wrapper<X>
test1(__gnu_test::bidirectional_iterator_wrapper<X>& begin,
__gnu_test::bidirectional_iterator_wrapper<X>& middle,
__gnu_test::bidirectional_iterator_wrapper<X>& end)
{ return std::rotate(begin,middle,end); }
-void
+__gnu_test::random_access_iterator_wrapper<X>
test1(__gnu_test::random_access_iterator_wrapper<X>& begin,
__gnu_test::random_access_iterator_wrapper<X>& middle,
__gnu_test::random_access_iterator_wrapper<X>& end)
diff --git a/libstdc++-v3/testsuite/25_algorithms/rotate/dr488.cc b/libstdc++-v3/testsuite/25_algorithms/rotate/dr488.cc
new file mode 100644
index 0000000..60bd033
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/rotate/dr488.cc
@@ -0,0 +1,77 @@
+// Copyright (C) 2015 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++11" }
+
+#include <algorithm>
+#include <iterator>
+#include <forward_list>
+#include <list>
+#include <vector>
+#include <testsuite_hooks.h>
+
+template<typename Container>
+void
+test(Container& c)
+{
+ int size = std::distance(c.begin(), c.end());
+ for (int i=0; i < size; ++i)
+ {
+ auto first = c.begin(), middle = std::next(first, i), last = c.end();
+ auto r = std::rotate(first, middle, last);
+ auto expected = std::next(first, std::distance(middle, last));
+ VERIFY( r == expected );
+ }
+}
+
+void
+test01()
+{
+ // test random access iterators
+ std::vector<int> v{ 0, 1, 2, 3, 4 };
+ test(v);
+ v.push_back(5);
+ test(v);
+}
+
+void
+test02()
+{
+ // test bidirectional iterators
+ std::list<int> l{ 0, 1, 2, 3, 4 };
+ test(l);
+ l.push_back(5);
+ test(l);
+}
+
+void
+test03()
+{
+ // test forward iterators
+ std::forward_list<int> l{ 0, 1, 2, 3, 4 };
+ test(l);
+ l.push_front(5);
+ test(l);
+}
+
+int
+main()
+{
+ test01();
+ test02();
+ test03();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/2.cc b/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/2.cc
index d48e653..ec8c917 100644
--- a/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/2.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/2.cc
@@ -30,5 +30,5 @@ namespace std
typedef NonDefaultConstructible value_type;
typedef value_type* iterator_type;
- template void rotate(iterator_type, iterator_type, iterator_type);
+ template iterator_type rotate(iterator_type, iterator_type, iterator_type);
}
diff --git a/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/pod.cc b/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/pod.cc
index 5804c63..c24ee70 100644
--- a/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/pod.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/rotate/requirements/explicit_instantiation/pod.cc
@@ -30,5 +30,5 @@ namespace std
typedef pod_int value_type;
typedef value_type* iterator_type;
- template void rotate(iterator_type, iterator_type, iterator_type);
+ template iterator_type rotate(iterator_type, iterator_type, iterator_type);
}