diff options
| author | David Krauss <potswa@mac.com> | 2009-11-03 18:16:34 +0000 |
|---|---|---|
| committer | Paolo Carlini <paolo@gcc.gnu.org> | 2009-11-03 18:16:34 +0000 |
| commit | 6e924e079b7f329afe359e91aa4db7856a387bc9 (patch) | |
| tree | 9822080e8f3630b0d1fe1d0283391c82cd2ce99b /libstdc++-v3 | |
| parent | 156e423608fd6c71fde8910c664a066aa23dd2c9 (diff) | |
| download | gcc-6e924e079b7f329afe359e91aa4db7856a387bc9.zip gcc-6e924e079b7f329afe359e91aa4db7856a387bc9.tar.gz gcc-6e924e079b7f329afe359e91aa4db7856a387bc9.tar.bz2 | |
re PR libstdc++/41351 (std::rotate on RAI does not conform to ISO complexity requirement)
2009-11-03 David Krauss <potswa@mac.com>
Paolo Carlini <paolo.carlini@oracle.com>
PR libstdc++/41351
* include/bits/stl_algo.h (__rotate(_RandomAccessIterator,
_RandomAccessIterator, _RandomAccessIterator,
random_access_iterator_tag)): Rewrite to use only std::swap in
general and std::copy/std::copy_backward when safe.
Co-Authored-By: Paolo Carlini <paolo.carlini@oracle.com>
From-SVN: r153860
Diffstat (limited to 'libstdc++-v3')
| -rw-r--r-- | libstdc++-v3/ChangeLog | 9 | ||||
| -rw-r--r-- | libstdc++-v3/include/bits/stl_algo.h | 71 |
2 files changed, 50 insertions, 30 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 589671b..494e24e 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,12 @@ +2009-11-03 David Krauss <potswa@mac.com> + Paolo Carlini <paolo.carlini@oracle.com> + + PR libstdc++/41351 + * include/bits/stl_algo.h (__rotate(_RandomAccessIterator, + _RandomAccessIterator, _RandomAccessIterator, + random_access_iterator_tag)): Rewrite to use only std::swap in + general and std::copy/std::copy_backward when safe. + 2009-11-02 Benjamin Kosnik <bkoz@redhat.com> * include/std/future: Use base class with nested types. diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index 70cde1a..9b6f2af 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -1647,53 +1647,64 @@ _GLIBCXX_BEGIN_NAMESPACE(std) typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType; - const _Distance __n = __last - __first; - const _Distance __k = __middle - __first; - const _Distance __l = __n - __k; + _Distance __n = __last - __first; + _Distance __k = __middle - __first; - if (__k == __l) + if (__k == __n - __k) { std::swap_ranges(__first, __middle, __middle); return; } - const _Distance __d = std::__gcd(__n, __k); + _RandomAccessIterator __p = __first; - for (_Distance __i = 0; __i < __d; __i++) + for (;;) { - _ValueType __tmp = _GLIBCXX_MOVE(*__first); - _RandomAccessIterator __p = __first; - - if (__k < __l) + if (__k < __n - __k) { - for (_Distance __j = 0; __j < __l / __d; __j++) + if (__is_pod(_ValueType) && __k == 1) + { + _ValueType __t = _GLIBCXX_MOVE(*__p); + _GLIBCXX_MOVE3(__p + 1, __p + __n, __p); + *(__p + __n - 1) = _GLIBCXX_MOVE(__t); + return; + } + _RandomAccessIterator __q = __p + __k; + for (_Distance __i = 0; __i < __n - __k; ++ __i) { - if (__p > __first + __l) - { - *__p = _GLIBCXX_MOVE(*(__p - __l)); - __p -= __l; - } - - *__p = _GLIBCXX_MOVE(*(__p + __k)); - __p += __k; + std::iter_swap(__p, __q); + ++__p; + ++__q; } + __n %= __k; + if (__n == 0) + return; + std::swap(__n, __k); + __k = __n - __k; } else { - for (_Distance __j = 0; __j < __k / __d - 1; __j ++) + __k = __n - __k; + if (__is_pod(_ValueType) && __k == 1) { - if (__p < __last - __k) - { - *__p = _GLIBCXX_MOVE(*(__p + __k)); - __p += __k; - } - *__p = _GLIBCXX_MOVE(*(__p - __l)); - __p -= __l; + _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1)); + _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n); + *__p = _GLIBCXX_MOVE(__t); + return; } + _RandomAccessIterator __q = __p + __n; + __p = __q - __k; + for (_Distance __i = 0; __i < __n - __k; ++ __i) + { + --__p; + --__q; + std::iter_swap(__p, __q); + } + __n %= __k; + if (__n == 0) + return; + std::swap(__n, __k); } - - *__p = _GLIBCXX_MOVE(__tmp); - ++__first; } } |