After completing this work and running more tests I realized that the
declaration of algos was still not ideal.
So here is another version where algos are not re-declare in
stl_deque.h, I rather include stl_algobase.h in deque.tcc. The problem
was spotted but another patch I am going to submit afterward.
Note that this patch is based after this one:
https://gcc.gnu.org/ml/libstdc++/2019-10/msg00072.html
François
On 9/25/19 6:44 AM, François Dumont wrote:
Ping ?
On 9/9/19 8:34 PM, François Dumont wrote:
Hi
This patch improves stl_algobase.h
copy/copy_backward/fill/fill_n/equal implementations. The
improvements are:
- activation of algo specialization for __gnu_debug::_Safe_iterator
(w/o _GLIBCXX_DEBUG mode)
- activation of algo specialization for _Deque_iterator even if mixed
with another kind of iterator.
- activation of algo specializations __copy_move_a2 for something
else than pointers. For example this code:
std::vector<char> v { 'a', 'b', .... };
ostreambuf_iterator out(std::cout);
std::copy(v.begin(), v.end(), out);
is not calling the specialization __copy_move_a2(const char*, const
char*, ostreambuf_iterator<>);
It also fix a _GLIBCXX_DEBUG issue where the __niter_base
specialization was wrongly removing the _Safe_iterator<> layer. The
testsuite/25_algorithms/copy/debug/1_neg.cc test case was failing on
a debug assertion because _after_ the copy we were trying to
increment the vector iterator after past-the-end. Of course the
problem is the _after_, Debug mode should detect this _before_ it
takes place which it does now.
Note that std::fill_n is now making use of std::fill for some
optimizations dealing with random access iterators.
Performances are very good:
Before:
copy_backward_deque_iterators.cc deque 2 deque 1084r 1084u
0s 0mem 0pf
copy_backward_deque_iterators.cc deque 2 vector 3373r 3372u
0s 0mem 0pf
copy_backward_deque_iterators.cc vector 2 deque 3316r 3316u
0s 0mem 0pf
copy_backward_deque_iterators.cc int deque 2 char vector 3610r
3609u 0s 0mem 0pf
copy_backward_deque_iterators.cc char vector 2 int deque 3552r
3552u 0s 0mem 0pf
copy_backward_deque_iterators.cc deque 2 list 10528r 10528u
0s 0mem 0pf
copy_backward_deque_iterators.cc list 2 deque 2161r 2162u
0s 0mem 0pf
copy_deque_iterators.cc deque 2 deque 752r
751u 0s 0mem 0pf
copy_deque_iterators.cc deque 2 vector 3300r
3299u 0s 0mem 0pf
copy_deque_iterators.cc vector 2 deque 3144r
3140u 0s 0mem 0pf
copy_deque_iterators.cc int deque 2 char vector 3340r
3338u 1s 0mem 0pf
copy_deque_iterators.cc char vector 2 int deque 3132r
3132u 0s 0mem 0pf
copy_deque_iterators.cc deque 2 list 10013r
10012u 0s 0mem 0pf
copy_deque_iterators.cc list 2 deque 2274r
2275u 0s 0mem 0pf
equal_deque_iterators.cc deque vs deque 8676r
8675u 0s 0mem 0pf
equal_deque_iterators.cc deque vs vector 5870r
5870u 0s 0mem 0pf
equal_deque_iterators.cc vector vs deque 3163r
3163u 0s 0mem 0pf
equal_deque_iterators.cc int deque vs char vector 5845r
5845u 0s 0mem 0pf
equal_deque_iterators.cc char vector vs int deque 3307r
3307u 0s 0mem 0pf
After:
copy_backward_deque_iterators.cc deque 2 deque 697r 697u
0s 0mem 0pf
copy_backward_deque_iterators.cc deque 2 vector 219r 218u
0s 0mem 0pf
copy_backward_deque_iterators.cc vector 2 deque 453r 453u
0s 0mem 0pf
copy_backward_deque_iterators.cc int deque 2 char vector 1914r
1915u 0s 0mem 0pf
copy_backward_deque_iterators.cc char vector 2 int deque 2112r
2111u 0s 0mem 0pf
copy_backward_deque_iterators.cc deque 2 list 7770r 7771u
0s 0mem 0pf
copy_backward_deque_iterators.cc list 2 deque 2194r 2193u
0s 0mem 0pf
copy_deque_iterators.cc deque 2 deque 505r
504u 0s 0mem 0pf
copy_deque_iterators.cc deque 2 vector 221r
221u 0s 0mem 0pf
copy_deque_iterators.cc vector 2 deque 398r
397u 0s 0mem 0pf
copy_deque_iterators.cc int deque 2 char vector 1770r
1767u 0s 0mem 0pf
copy_deque_iterators.cc char vector 2 int deque 1995r
1993u 0s 0mem 0pf
copy_deque_iterators.cc deque 2 list 7650r
7641u 2s 0mem 0pf
copy_deque_iterators.cc list 2 deque 2270r
2270u 0s 0mem 0pf
equal_deque_iterators.cc deque vs deque 769r
768u 0s 0mem 0pf
equal_deque_iterators.cc deque vs vector 231r
230u 0s 0mem 0pf
equal_deque_iterators.cc vector vs deque 397r
397u 0s 0mem 0pf
equal_deque_iterators.cc int deque vs char vector 1541r
1541u 0s 0mem 0pf
equal_deque_iterators.cc char vector vs int deque 1623r
1623u 0s 0mem 0pf
In Debug Mode it is of course even better. I haven't had the patience
to run the benches before the patch, it just takes hours to run. So
here is just the After part:
copy_backward_deque_iterators.cc deque 2 deque 1128r 1128u
0s 0mem 0pf
copy_backward_deque_iterators.cc deque 2 vector 616r 616u
0s 0mem 0pf
copy_backward_deque_iterators.cc vector 2 deque 856r 855u
0s 0mem 0pf
copy_backward_deque_iterators.cc int deque 2 char vector 2277r
2277u 0s 0mem 0pf
copy_backward_deque_iterators.cc char vector 2 int deque 2518r
2519u 0s 0mem 0pf
copy_backward_deque_iterators.cc deque 2 list 8029r 8028u
0s 0mem 0pf
copy_backward_deque_iterators.cc list 2 deque 10418r 10416u
0s 0mem 0pf
copy_deque_iterators.cc deque 2 deque 931r
930u 0s 0mem 0pf
copy_deque_iterators.cc deque 2 vector 613r
613u 0s 0mem 0pf
copy_deque_iterators.cc vector 2 deque 794r
795u 0s 0mem 0pf
copy_deque_iterators.cc int deque 2 char vector 2192r
2192u 0s 0mem 0pf
copy_deque_iterators.cc char vector 2 int deque 2365r
2364u 0s 0mem 0pf
copy_deque_iterators.cc deque 2 list 8009r
8010u 0s 0mem 0pf
copy_deque_iterators.cc list 2 deque 10979r
10970u 1s 0mem 0pf
equal_deque_iterators.cc deque vs deque 1034r
1032u 0s 0mem 0pf
equal_deque_iterators.cc deque vs vector 481r
482u 0s 0mem 0pf
equal_deque_iterators.cc vector vs deque 646r
646u 0s 0mem 0pf
equal_deque_iterators.cc int deque vs char vector 1802r
1802u 0s 0mem 0pf
equal_deque_iterators.cc char vector vs int deque 1867r
1865u 0s 0mem 0pf
Note that copy/copy_backward 'list 2 deque' is still much slower
because for the moment we can't remove the debug layer. I plan to do
a refinement to also cover this use case.
In Debug implementations I have duplicated the Debug checks because
those algo specialization will also be used when users are directly
using <debug/vector> for instance without defining _GLIBCXX_DEBUG.
All algos tests passed except the constexpr ones in Debug mode, I've
put this on my todo list.
Ok to commit once I completed all the other tests ?
François
diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
index 3f77b4f079c..ae5366d6208 100644
--- a/libstdc++-v3/include/bits/deque.tcc
+++ b/libstdc++-v3/include/bits/deque.tcc
@@ -56,6 +56,8 @@
#ifndef _DEQUE_TCC
#define _DEQUE_TCC 1
+#include <bits/stl_algobase.h>
+
namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
@@ -967,155 +969,247 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
}
+_GLIBCXX_END_NAMESPACE_CONTAINER
+
// Overload for deque::iterators, exploiting the "segmented-iterator
// optimization".
- template<typename _Tp>
+ template<typename _Tp, typename _VTp>
void
- fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
- const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
+ __fill_a1(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __last,
+ const _VTp& __value)
{
- typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
+ if (__first._M_node != __last._M_node)
+ {
+ std::__fill_a1(__first._M_cur, __first._M_last, __value);
- for (typename _Self::_Map_pointer __node = __first._M_node + 1;
- __node < __last._M_node; ++__node)
- std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
+ for (typename _Iter::_Map_pointer __node = __first._M_node + 1;
+ __node < __last._M_node; ++__node)
+ std::__fill_a1(*__node, *__node + _Iter::_S_buffer_size(), __value);
+ std::__fill_a1(__last._M_first, __last._M_cur, __value);
+ }
+ else
+ std::__fill_a1(__first._M_cur, __last._M_cur, __value);
+ }
+
+ template<bool _IsMove,
+ typename _Tp, typename _Ref, typename _Ptr, typename _OI>
+ _OI
+ __copy_move_dit(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
+ _OI __result)
+ {
+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
if (__first._M_node != __last._M_node)
{
- std::fill(__first._M_cur, __first._M_last, __value);
- std::fill(__last._M_first, __last._M_cur, __value);
+ __result
+ = std::__copy_move_a1<_IsMove>(__first._M_cur, __first._M_last,
+ __result);
+
+ for (typename _Iter::_Map_pointer __node = __first._M_node + 1;
+ __node != __last._M_node; ++__node)
+ __result
+ = std::__copy_move_a1<_IsMove>(*__node,
+ *__node + _Iter::_S_buffer_size(),
+ __result);
+
+ return std::__copy_move_a1<_IsMove>(__last._M_first, __last._M_cur,
+ __result);
}
- else
- std::fill(__first._M_cur, __last._M_cur, __value);
+
+ return std::__copy_move_a1<_IsMove>(__first._M_cur, __last._M_cur,
+ __result);
}
- template<typename _Tp>
- _Deque_iterator<_Tp, _Tp&, _Tp*>
- copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
- _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
- _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
+ template<bool _IsMove,
+ typename _Tp, typename _Ref, typename _Ptr, typename _OI>
+ _OI
+ __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
+ _OI __result)
+ { return __copy_move_dit<_IsMove>(__first, __last, __result); }
+
+ template<bool _IsMove,
+ typename _ITp, typename _IRef, typename _IPtr, typename _OTp>
+ _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
+ __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last,
+ _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result)
+ { return __copy_move_dit<_IsMove>(__first, __last, __result); }
+
+ template<bool _IsMove, typename _II, typename _Tp>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II>::__value,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
+ __copy_move_a1(_II __first, _II __last,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
{
- typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
- typedef typename _Self::difference_type difference_type;
+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
+ typedef typename _Iter::difference_type difference_type;
difference_type __len = __last - __first;
while (__len > 0)
{
const difference_type __clen
- = std::min(__len, std::min(__first._M_last - __first._M_cur,
- __result._M_last - __result._M_cur));
- std::copy(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
+ = std::min(__len, __result._M_last - __result._M_cur);
+ std::__copy_move_a1<_IsMove>(__first, __first + __clen,
+ __result._M_cur);
+
__first += __clen;
__result += __clen;
__len -= __clen;
}
+
return __result;
}
- template<typename _Tp>
- _Deque_iterator<_Tp, _Tp&, _Tp*>
- copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
- _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
- _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
+ template<bool _IsMove,
+ typename _Tp, typename _Ref, typename _Ptr, typename _OI>
+ _OI
+ __copy_move_backward_dit(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
+ _OI __result)
+ {
+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
+ if (__first._M_node != __last._M_node)
+ {
+ __result = std::__copy_move_backward_a1<_IsMove>(
+ __last._M_first, __last._M_cur, __result);
+
+ for (typename _Iter::_Map_pointer __node = __last._M_node - 1;
+ __node != __first._M_node; --__node)
+ __result = std::__copy_move_backward_a1<_IsMove>(
+ *__node, *__node + _Iter::_S_buffer_size(), __result);
+
+ return std::__copy_move_backward_a1<_IsMove>(
+ __first._M_cur, __first._M_last, __result);
+ }
+
+ return std::__copy_move_backward_a1<_IsMove>(
+ __first._M_cur, __last._M_cur, __result);
+ }
+
+ template<bool _IsMove,
+ typename _Tp, typename _Ref, typename _Ptr, typename _OI>
+ _OI
+ __copy_move_backward_a1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
+ _OI __result)
+ { return __copy_move_backward_dit<_IsMove>(__first, __last, __result); }
+
+ template<bool _IsMove,
+ typename _ITp, typename _IRef, typename _IPtr, typename _OTp>
+ _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
+ __copy_move_backward_a1(
+ _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last,
+ _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result)
+ { return __copy_move_backward_dit<_IsMove>(__first, __last, __result); }
+
+ template<bool _IsMove, typename _II, typename _Tp>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II>::__value,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
+ __copy_move_backward_a1(_II __first, _II __last,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
{
- typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
- typedef typename _Self::difference_type difference_type;
+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
+ typedef typename _Iter::difference_type difference_type;
difference_type __len = __last - __first;
while (__len > 0)
{
- difference_type __llen = __last._M_cur - __last._M_first;
- _Tp* __lend = __last._M_cur;
-
difference_type __rlen = __result._M_cur - __result._M_first;
_Tp* __rend = __result._M_cur;
-
- if (!__llen)
- {
- __llen = _Self::_S_buffer_size();
- __lend = *(__last._M_node - 1) + __llen;
- }
if (!__rlen)
{
- __rlen = _Self::_S_buffer_size();
+ __rlen = _Iter::_S_buffer_size();
__rend = *(__result._M_node - 1) + __rlen;
}
- const difference_type __clen = std::min(__len,
- std::min(__llen, __rlen));
- std::copy_backward(__lend - __clen, __lend, __rend);
+ const difference_type __clen = std::min(__len, __rlen);
+ std::__copy_move_backward_a1<_IsMove>(__last - __clen, __last, __rend);
+
__last -= __clen;
__result -= __clen;
__len -= __clen;
}
+
return __result;
}
-#if __cplusplus >= 201103L
- template<typename _Tp>
- _Deque_iterator<_Tp, _Tp&, _Tp*>
- move(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
- _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
- _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
+ template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
+ bool
+ __equal_dit(
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __first1,
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __last1,
+ _II __first2)
{
- typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
- typedef typename _Self::difference_type difference_type;
-
- difference_type __len = __last - __first;
- while (__len > 0)
+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
+ if (__first1._M_node != __last1._M_node)
{
- const difference_type __clen
- = std::min(__len, std::min(__first._M_last - __first._M_cur,
- __result._M_last - __result._M_cur));
- std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
- __first += __clen;
- __result += __clen;
- __len -= __clen;
+ if (!std::__equal_aux1(__first1._M_cur, __first1._M_last, __first2))
+ return false;
+
+ __first2 += __first1._M_last - __first1._M_cur;
+ for (typename _Iter::_Map_pointer __node = __first1._M_node + 1;
+ __node != __last1._M_node;
+ __first2 += _Iter::_S_buffer_size(), ++__node)
+ if (!std::__equal_aux1(*__node, *__node + _Iter::_S_buffer_size(),
+ __first2))
+ return false;
+
+ return std::__equal_aux1(__last1._M_first, __last1._M_cur, __first2);
}
- return __result;
+
+ return std::__equal_aux1(__first1._M_cur, __last1._M_cur, __first2);
}
- template<typename _Tp>
- _Deque_iterator<_Tp, _Tp&, _Tp*>
- move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
- _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
- _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
+ template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II>::__value, bool>::__type
+ __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last1,
+ _II __first2)
+ { return std::__equal_dit(__first1, __last1, __first2); }
+
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ bool
+ __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2)
+ { return std::__equal_dit(__first1, __last1, __first2); }
+
+ template<typename _II, typename _Tp, typename _Ref, typename _Ptr>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II>::__value, bool>::__type
+ __equal_aux1(_II __first1, _II __last1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first2)
{
- typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
- typedef typename _Self::difference_type difference_type;
+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
+ typedef typename _Iter::difference_type difference_type;
- difference_type __len = __last - __first;
+ difference_type __len = __last1 - __first1;
while (__len > 0)
{
- difference_type __llen = __last._M_cur - __last._M_first;
- _Tp* __lend = __last._M_cur;
-
- difference_type __rlen = __result._M_cur - __result._M_first;
- _Tp* __rend = __result._M_cur;
-
- if (!__llen)
- {
- __llen = _Self::_S_buffer_size();
- __lend = *(__last._M_node - 1) + __llen;
- }
- if (!__rlen)
- {
- __rlen = _Self::_S_buffer_size();
- __rend = *(__result._M_node - 1) + __rlen;
- }
+ const difference_type __clen
+ = std::min(__len, __first2._M_last - __first2._M_cur);
+ if (!std::__equal_aux1(__first1, __first1 + __clen, __first2._M_cur))
+ return false;
- const difference_type __clen = std::min(__len,
- std::min(__llen, __rlen));
- std::move_backward(__lend - __clen, __lend, __rend);
- __last -= __clen;
- __result -= __clen;
+ __first1 += __clen;
__len -= __clen;
+ __first2 += __clen;
}
- return __result;
+
+ return true;
}
-#endif
-_GLIBCXX_END_NAMESPACE_CONTAINER
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 48fa5b6919c..1548afcad4d 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -484,22 +484,6 @@ namespace __detail
}
};
- template<bool _IsMove, typename _II, typename _OI>
- _GLIBCXX20_CONSTEXPR
- inline _OI
- __copy_move_a(_II __first, _II __last, _OI __result)
- {
- typedef typename iterator_traits<_II>::value_type _ValueTypeI;
- typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
- typedef typename iterator_traits<_II>::iterator_category _Category;
- const bool __simple = (__is_trivially_copyable(_ValueTypeI)
- && __is_pointer<_II>::__value
- && __is_pointer<_OI>::__value
- && __are_same<_ValueTypeI, _ValueTypeO>::__value);
- return std::__copy_move<_IsMove, __simple,
- _Category>::__copy_m(__first, __last, __result);
- }
-
// Helpers for streambuf iterators (either istream or ostream).
// NB: avoid including <iosfwd>, relatively large.
template<typename _CharT>
@@ -533,13 +517,83 @@ namespace __detail
_GLIBCXX20_CONSTEXPR
inline _OI
__copy_move_a2(_II __first, _II __last, _OI __result)
+ {
+ typedef typename iterator_traits<_II>::value_type _ValueTypeI;
+ typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
+ typedef typename iterator_traits<_II>::iterator_category _Category;
+ const bool __simple = (__is_trivially_copyable(_ValueTypeI)
+ && __is_pointer<_II>::__value
+ && __is_pointer<_OI>::__value
+ && __are_same<_ValueTypeI, _ValueTypeO>::__value);
+ return std::__copy_move<_IsMove, __simple,
+ _Category>::__copy_m(__first, __last, __result);
+ }
+
+_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
+
+ template<typename _Tp, typename _Ref, typename _Ptr>
+ struct _Deque_iterator;
+
+_GLIBCXX_END_NAMESPACE_CONTAINER
+
+ template<bool _IsMove,
+ typename _Tp, typename _Ref, typename _Ptr, typename _OI>
+ _OI
+ __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
+ _OI);
+
+ template<bool _IsMove,
+ typename _ITp, typename _IRef, typename _IPtr, typename _OTp>
+ _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
+ __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
+ _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
+ _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>);
+
+ template<bool _IsMove, typename _II, typename _Tp>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II>::__value,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
+ __copy_move_a1(_II, _II, _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
+
+ template<bool _IsMove, typename _II, typename _OI>
+ _GLIBCXX20_CONSTEXPR
+ inline _OI
+ __copy_move_a1(_II __first, _II __last, _OI __result)
+ { return std::__copy_move_a2<_IsMove>(__first, __last, __result); }
+
+ template<bool _IsMove, typename _II, typename _OI>
+ _GLIBCXX20_CONSTEXPR
+ inline _OI
+ __copy_move_a(_II __first, _II __last, _OI __result)
{
return std::__niter_wrap(__result,
- std::__copy_move_a<_IsMove>(std::__niter_base(__first),
- std::__niter_base(__last),
- std::__niter_base(__result)));
+ std::__copy_move_a1<_IsMove>(std::__niter_base(__first),
+ std::__niter_base(__last),
+ std::__niter_base(__result)));
}
+ template<bool _IsMove,
+ typename _Ite, typename _Seq, typename _Cat, typename _OI>
+ _OI
+ __copy_move_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
+ const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
+ _OI);
+
+ template<bool _IsMove,
+ typename _II, typename _Ite, typename _Seq, typename _Cat>
+ __gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
+ __copy_move_a(_II, _II,
+ const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&);
+
+ template<bool _IsMove,
+ typename _IIte, typename _ISeq, typename _ICat,
+ typename _OIte, typename _OSeq, typename _OCat>
+ ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>
+ __copy_move_a(const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
+ const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
+ const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&);
+
/**
* @brief Copies the range [first,last) into result.
* @ingroup mutating_algorithms
@@ -568,7 +622,7 @@ namespace __detail
typename iterator_traits<_II>::value_type>)
__glibcxx_requires_can_increment_range(__first, __last, __result);
- return std::__copy_move_a2<__is_move_iterator<_II>::__value>
+ return std::__copy_move_a<__is_move_iterator<_II>::__value>
(std::__miter_base(__first), std::__miter_base(__last), __result);
}
@@ -601,8 +655,8 @@ namespace __detail
typename iterator_traits<_II>::value_type>)
__glibcxx_requires_can_increment_range(__first, __last, __result);
- return std::__copy_move_a2<true>(std::__miter_base(__first),
- std::__miter_base(__last), __result);
+ return std::__copy_move_a<true>(std::__miter_base(__first),
+ std::__miter_base(__last), __result);
}
#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
@@ -610,7 +664,7 @@ namespace __detail
#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp)
#endif
- template<bool, bool, typename>
+ template<bool _IsMove, bool _IsSimple, typename _Category>
struct __copy_move_backward
{
template<typename _BI1, typename _BI2>
@@ -700,7 +754,7 @@ namespace __detail
template<bool _IsMove, typename _BI1, typename _BI2>
_GLIBCXX20_CONSTEXPR
inline _BI2
- __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result)
+ __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
{
typedef typename iterator_traits<_BI1>::value_type _ValueType1;
typedef typename iterator_traits<_BI2>::value_type _ValueType2;
@@ -719,14 +773,65 @@ namespace __detail
template<bool _IsMove, typename _BI1, typename _BI2>
_GLIBCXX20_CONSTEXPR
inline _BI2
- __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
+ __copy_move_backward_a1(_BI1 __first, _BI1 __last, _BI2 __result)
+ { return std::__copy_move_backward_a2<_IsMove>(__first, __last, __result); }
+
+ template<bool _IsMove,
+ typename _Tp, typename _Ref, typename _Ptr, typename _OI>
+ _OI
+ __copy_move_backward_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
+ _OI);
+
+ template<bool _IsMove,
+ typename _ITp, typename _IRef, typename _IPtr, typename _OTp>
+ _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
+ __copy_move_backward_a1(
+ _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
+ _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
+ _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>);
+
+ template<bool _IsMove, typename _II, typename _Tp>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II>::__value,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
+ __copy_move_backward_a1(_II, _II,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
+
+ template<bool _IsMove, typename _II, typename _OI>
+ _GLIBCXX20_CONSTEXPR
+ inline _OI
+ __copy_move_backward_a(_II __first, _II __last, _OI __result)
{
return std::__niter_wrap(__result,
- std::__copy_move_backward_a<_IsMove>
+ std::__copy_move_backward_a1<_IsMove>
(std::__niter_base(__first), std::__niter_base(__last),
std::__niter_base(__result)));
}
+ template<bool _IsMove,
+ typename _Ite, typename _Seq, typename _Cat, typename _OI>
+ _OI
+ __copy_move_backward_a(
+ const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
+ const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
+ _OI);
+
+ template<bool _IsMove,
+ typename _II, typename _Ite, typename _Seq, typename _Cat>
+ __gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
+ __copy_move_backward_a(_II, _II,
+ const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&);
+
+ template<bool _IsMove,
+ typename _IIte, typename _ISeq, typename _ICat,
+ typename _OIte, typename _OSeq, typename _OCat>
+ ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>
+ __copy_move_backward_a(
+ const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
+ const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
+ const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&);
+
/**
* @brief Copies the range [first,last) into result.
* @ingroup mutating_algorithms
@@ -758,7 +863,7 @@ namespace __detail
typename iterator_traits<_BI2>::value_type>)
__glibcxx_requires_can_decrement_range(__first, __last, __result);
- return std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value>
+ return std::__copy_move_backward_a<__is_move_iterator<_BI1>::__value>
(std::__miter_base(__first), std::__miter_base(__last), __result);
}
@@ -794,9 +899,9 @@ namespace __detail
typename iterator_traits<_BI2>::value_type>)
__glibcxx_requires_can_decrement_range(__first, __last, __result);
- return std::__copy_move_backward_a2<true>(std::__miter_base(__first),
- std::__miter_base(__last),
- __result);
+ return std::__copy_move_backward_a<true>(std::__miter_base(__first),
+ std::__miter_base(__last),
+ __result);
}
#define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp)
@@ -808,8 +913,8 @@ namespace __detail
_GLIBCXX20_CONSTEXPR
inline typename
__gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type
- __fill_a(_ForwardIterator __first, _ForwardIterator __last,
- const _Tp& __value)
+ __fill_a1(_ForwardIterator __first, _ForwardIterator __last,
+ const _Tp& __value)
{
for (; __first != __last; ++__first)
*__first = __value;
@@ -819,8 +924,8 @@ namespace __detail
_GLIBCXX20_CONSTEXPR
inline typename
__gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type
- __fill_a(_ForwardIterator __first, _ForwardIterator __last,
- const _Tp& __value)
+ __fill_a1(_ForwardIterator __first, _ForwardIterator __last,
+ const _Tp& __value)
{
const _Tp __tmp = __value;
for (; __first != __last; ++__first)
@@ -831,13 +936,39 @@ namespace __detail
template<typename _Tp>
inline typename
__gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type
- __fill_a(_Tp* __first, _Tp* __last, const _Tp& __c)
+ __fill_a1(_Tp* __first, _Tp* __last, const _Tp& __c)
{
const _Tp __tmp = __c;
if (const size_t __len = __last - __first)
__builtin_memset(__first, static_cast<unsigned char>(__tmp), __len);
}
+ template<typename _Ite, typename _Cont, typename _Tp>
+ _GLIBCXX20_CONSTEXPR
+ inline void
+ __fill_a1(::__gnu_cxx::__normal_iterator<_Ite, _Cont> __first,
+ ::__gnu_cxx::__normal_iterator<_Ite, _Cont> __last,
+ const _Tp& __value)
+ { std::__fill_a1(__first.base(), __last.base(), __value); }
+
+ template<typename _Tp, typename _VTp>
+ void
+ __fill_a1(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&,
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&,
+ const _VTp&);
+
+ template<typename _FIte, typename _Tp>
+ _GLIBCXX20_CONSTEXPR
+ inline void
+ __fill_a(_FIte __first, _FIte __last, const _Tp& __value)
+ { std::__fill_a1(__first, __last, __value); }
+
+ template<typename _Ite, typename _Seq, typename _Cat, typename _Tp>
+ void
+ __fill_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
+ const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
+ const _Tp&);
+
/**
* @brief Fills the range [first,last) with copies of value.
* @ingroup mutating_algorithms
@@ -860,8 +991,7 @@ namespace __detail
_ForwardIterator>)
__glibcxx_requires_valid_range(__first, __last);
- std::__fill_a(std::__niter_base(__first), std::__niter_base(__last),
- __value);
+ std::__fill_a(__first, __last, __value);
}
// Used by fill_n, generate_n, etc. to convert _Size to an integral type:
@@ -918,11 +1048,8 @@ namespace __detail
_GLIBCXX20_CONSTEXPR
inline typename
__gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type
- __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
+ __fill_n_a1(_OutputIterator __first, _Size __n, const _Tp& __value)
{
-#if __cplusplus >= 201103L
- static_assert(is_integral<_Size>{}, "fill_n must pass integral size");
-#endif
for (; __n > 0; --__n, (void) ++__first)
*__first = __value;
return __first;
@@ -932,24 +1059,60 @@ namespace __detail
_GLIBCXX20_CONSTEXPR
inline typename
__gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type
- __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value)
+ __fill_n_a1(_OutputIterator __first, _Size __n, const _Tp& __value)
{
-#if __cplusplus >= 201103L
- static_assert(is_integral<_Size>{}, "fill_n must pass integral size");
-#endif
const _Tp __tmp = __value;
for (; __n > 0; --__n, (void) ++__first)
*__first = __tmp;
return __first;
}
- template<typename _Size, typename _Tp>
+ template<typename _Ite, typename _Seq, typename _Cat, typename _Size,
+ typename _Tp>
+ ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
+ __fill_n_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
+ _Size __n, const _Tp& __value,
+ std::input_iterator_tag);
+
+ template<typename _OutputIterator, typename _Size, typename _Tp>
_GLIBCXX20_CONSTEXPR
- inline typename
- __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, _Tp*>::__type
- __fill_n_a(_Tp* __first, _Size __n, const _Tp& __c)
+ inline _OutputIterator
+ __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value,
+ std::output_iterator_tag)
+ {
+#if __cplusplus >= 201103L
+ static_assert(is_integral<_Size>{}, "fill_n must pass integral size");
+#endif
+ return __fill_n_a1(__first, __n, __value);
+ }
+
+ template<typename _OutputIterator, typename _Size, typename _Tp>
+ _GLIBCXX20_CONSTEXPR
+ inline _OutputIterator
+ __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value,
+ std::input_iterator_tag)
+ {
+#if __cplusplus >= 201103L
+ static_assert(is_integral<_Size>{}, "fill_n must pass integral size");
+#endif
+ return __fill_n_a1(__first, __n, __value);
+ }
+
+ template<typename _OutputIterator, typename _Size, typename _Tp>
+ _GLIBCXX20_CONSTEXPR
+ inline _OutputIterator
+ __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value,
+ std::random_access_iterator_tag)
{
- std::__fill_a(__first, __first + __n, __c);
+#if __cplusplus >= 201103L
+ static_assert(is_integral<_Size>{}, "fill_n must pass integral size");
+#endif
+ if (__n <= 0)
+ return __first;
+
+ __glibcxx_requires_can_increment(__first, __n);
+
+ std::__fill_a(__first, __first + __n, __value);
return __first + __n;
}
@@ -978,10 +1141,8 @@ namespace __detail
// concept requirements
__glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>)
- return std::__niter_wrap(__first,
- std::__fill_n_a(std::__niter_base(__first),
- std::__size_to_integer(__n),
- __value));
+ return std::__fill_n_a(__first, std::__size_to_integer(__n), __value,
+ std::__iterator_category(__first));
}
template<bool _BoolType>
@@ -1013,10 +1174,30 @@ namespace __detail
}
};
+ template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II>::__value, bool>::__type
+ __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
+ _II);
+
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ bool
+ __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
+
+ template<typename _II, typename _Tp, typename _Ref, typename _Ptr>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II>::__value, bool>::__type
+ __equal_aux1(_II, _II,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>);
+
template<typename _II1, typename _II2>
_GLIBCXX20_CONSTEXPR
inline bool
- __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
+ __equal_aux1(_II1 __first1, _II1 __last1, _II2 __first2)
{
typedef typename iterator_traits<_II1>::value_type _ValueType1;
typedef typename iterator_traits<_II2>::value_type _ValueType2;
@@ -1029,6 +1210,34 @@ namespace __detail
return std::__equal<__simple>::equal(__first1, __last1, __first2);
}
+ template<typename _II1, typename _II2>
+ _GLIBCXX20_CONSTEXPR
+ inline bool
+ __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
+ {
+ return std::__equal_aux1(std::__niter_base(__first1),
+ std::__niter_base(__last1),
+ std::__niter_base(__first2));
+ }
+
+ template<typename _II1, typename _Seq1, typename _Cat1, typename _II2>
+ bool
+ __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
+ const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
+ _II2);
+
+ template<typename _II1, typename _II2, typename _Seq2, typename _Cat2>
+ bool
+ __equal_aux(_II1, _II1,
+ const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&);
+
+ template<typename _II1, typename _Seq1, typename _Cat1,
+ typename _II2, typename _Seq2, typename _Cat2>
+ bool
+ __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
+ const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
+ const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&);
+
template<typename, typename>
struct __lc_rai
{
@@ -1255,9 +1464,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
typename iterator_traits<_II2>::value_type>)
__glibcxx_requires_can_increment_range(__first1, __last1, __first2);
- return std::__equal_aux(std::__niter_base(__first1),
- std::__niter_base(__last1),
- std::__niter_base(__first2));
+ return std::__equal_aux(__first1, __last1, __first2);
}
/**
diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h
index 676768c0159..dcb68da4b61 100644
--- a/libstdc++-v3/include/bits/stl_deque.h
+++ b/libstdc++-v3/include/bits/stl_deque.h
@@ -373,77 +373,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
{ return __x + __n; }
};
- template<typename _Tp>
- void
- fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>&,
- const _Deque_iterator<_Tp, _Tp&, _Tp*>&, const _Tp&);
-
- template<typename _Tp>
- _Deque_iterator<_Tp, _Tp&, _Tp*>
- copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
- _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
- _Deque_iterator<_Tp, _Tp&, _Tp*>);
-
- template<typename _Tp>
- inline _Deque_iterator<_Tp, _Tp&, _Tp*>
- copy(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
- _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
- _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
- { return std::copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
- _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
- __result); }
-
- template<typename _Tp>
- _Deque_iterator<_Tp, _Tp&, _Tp*>
- copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
- _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
- _Deque_iterator<_Tp, _Tp&, _Tp*>);
-
- template<typename _Tp>
- inline _Deque_iterator<_Tp, _Tp&, _Tp*>
- copy_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
- _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
- _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
- { return std::copy_backward(_Deque_iterator<_Tp,
- const _Tp&, const _Tp*>(__first),
- _Deque_iterator<_Tp,
- const _Tp&, const _Tp*>(__last),
- __result); }
-
-#if __cplusplus >= 201103L
- template<typename _Tp>
- _Deque_iterator<_Tp, _Tp&, _Tp*>
- move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
- _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
- _Deque_iterator<_Tp, _Tp&, _Tp*>);
-
- template<typename _Tp>
- inline _Deque_iterator<_Tp, _Tp&, _Tp*>
- move(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
- _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
- _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
- { return std::move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
- _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
- __result); }
-
- template<typename _Tp>
- _Deque_iterator<_Tp, _Tp&, _Tp*>
- move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
- _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
- _Deque_iterator<_Tp, _Tp&, _Tp*>);
-
- template<typename _Tp>
- inline _Deque_iterator<_Tp, _Tp&, _Tp*>
- move_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
- _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
- _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
- { return std::move_backward(_Deque_iterator<_Tp,
- const _Tp&, const _Tp*>(__first),
- _Deque_iterator<_Tp,
- const _Tp&, const _Tp*>(__last),
- __result); }
-#endif
-
/**
* Deque base class. This class provides the unified face for %deque's
* allocation. This class's constructor and destructor allocate and
diff --git a/libstdc++-v3/include/bits/stl_iterator_base_types.h b/libstdc++-v3/include/bits/stl_iterator_base_types.h
index 3fad5869b40..b29a76543f4 100644
--- a/libstdc++-v3/include/bits/stl_iterator_base_types.h
+++ b/libstdc++-v3/include/bits/stl_iterator_base_types.h
@@ -249,10 +249,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
using _RequireInputIter =
__enable_if_t<is_convertible<__iterator_category_t<_InIter>,
input_iterator_tag>::value>;
+
+ template<typename _It,
+ typename _Cat = __iterator_category_t<_It>>
+ struct __is_random_access_iter
+ : is_base_of<random_access_iterator_tag, _Cat>
+ {
+ typedef is_base_of<random_access_iterator_tag, _Cat> _Base;
+ enum { __value = _Base::value };
+ };
+#else
+ template<typename _It, typename _Traits = iterator_traits<_It>,
+ typename _Cat = typename _Traits::iterator_category>
+ struct __is_random_access_iter
+ { enum { __value = __is_base_of(random_access_iterator_tag, _Cat) }; };
#endif
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace
#endif /* _STL_ITERATOR_BASE_TYPES_H */
-
diff --git a/libstdc++-v3/include/debug/debug.h b/libstdc++-v3/include/debug/debug.h
index d851b4ae6dd..8d3a8606ccd 100644
--- a/libstdc++-v3/include/debug/debug.h
+++ b/libstdc++-v3/include/debug/debug.h
@@ -56,6 +56,9 @@ namespace std
namespace __gnu_debug
{
using namespace std::__debug;
+
+ template<typename _Ite, typename _Seq, typename _Cat>
+ struct _Safe_iterator;
}
#ifndef _GLIBCXX_DEBUG
diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h
index fa0d03f39dc..536690d6dcd 100644
--- a/libstdc++-v3/include/debug/safe_iterator.h
+++ b/libstdc++-v3/include/debug/safe_iterator.h
@@ -400,7 +400,7 @@ namespace __gnu_debug
// Can we advance the iterator @p __n steps (@p __n may be negative)
bool
- _M_can_advance(difference_type __n) const;
+ _M_can_advance(difference_type __n, bool __strict = false) const;
// Is the iterator range [*this, __rhs) valid?
bool
diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc b/libstdc++-v3/include/debug/safe_iterator.tcc
index 1750bc473d2..1d98a882d56 100644
--- a/libstdc++-v3/include/debug/safe_iterator.tcc
+++ b/libstdc++-v3/include/debug/safe_iterator.tcc
@@ -29,6 +29,8 @@
#ifndef _GLIBCXX_DEBUG_SAFE_ITERATOR_TCC
#define _GLIBCXX_DEBUG_SAFE_ITERATOR_TCC 1
+#include <bits/stl_algobase.h>
+
namespace __gnu_debug
{
template<typename _Iterator, typename _Sequence, typename _Category>
@@ -82,7 +84,7 @@ namespace __gnu_debug
template<typename _Iterator, typename _Sequence, typename _Category>
bool
_Safe_iterator<_Iterator, _Sequence, _Category>::
- _M_can_advance(difference_type __n) const
+ _M_can_advance(difference_type __n, bool __strict) const
{
if (this->_M_singular())
return false;
@@ -94,17 +96,17 @@ namespace __gnu_debug
{
std::pair<difference_type, _Distance_precision> __dist =
_M_get_distance_from_begin();
- bool __ok = ((__dist.second == __dp_exact && __dist.first >= -__n)
- || (__dist.second != __dp_exact && __dist.first > 0));
- return __ok;
+ return __dist.second == __dp_exact
+ ? __dist.first >= -__n
+ : !__strict && __dist.first > 0;
}
else
{
std::pair<difference_type, _Distance_precision> __dist =
_M_get_distance_to_end();
- bool __ok = ((__dist.second == __dp_exact && __dist.first >= __n)
- || (__dist.second != __dp_exact && __dist.first > 0));
- return __ok;
+ return __dist.second == __dp_exact
+ ? __dist.first >= __n
+ : !__strict && __dist.first > 0;
}
}
@@ -228,4 +230,241 @@ namespace __gnu_debug
}
} // namespace __gnu_debug
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+ template<bool _IsMove,
+ typename _Ite, typename _Seq, typename _Cat, typename _OI>
+ _OI
+ __copy_move_a(
+ const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
+ const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __last,
+ _OI __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<_Ite>::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, __dist.first);
+
+ if (__dist.second > ::__gnu_debug::__dp_equality)
+ return std::__copy_move_a<_IsMove>(__first.base(), __last.base(),
+ __result);
+
+ return std::__copy_move_a1<_IsMove>(__first, __last, __result);
+ }
+
+ template<bool _IsMove,
+ typename _II, typename _Ite, typename _Seq, typename _Cat>
+ __gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
+ __copy_move_a(_II __first, _II __last,
+ const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<_II>::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, __dist.first);
+
+ if (__dist.second > ::__gnu_debug::__dp_sign
+ && __result._M_can_advance(__dist.first, true))
+ return ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>(
+ std::__copy_move_a<_IsMove>(__first, __last, __result.base()),
+ __result._M_sequence);
+
+ return std::__copy_move_a1<_IsMove>(__first, __last, __result);
+ }
+
+ template<bool _IsMove,
+ typename _IIte, typename _ISeq, typename _ICat,
+ typename _OIte, typename _OSeq, typename _OCat>
+ ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>
+ __copy_move_a(
+ const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>& __first,
+ const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>& __last,
+ const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>& __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<_IIte>::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, __dist.first);
+
+ if (__dist.second > ::__gnu_debug::__dp_equality)
+ {
+ if (__dist.second > ::__gnu_debug::__dp_sign
+ && __result._M_can_advance(__dist.first, true))
+ return ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>(
+ std::__copy_move_a<_IsMove>(__first.base(), __last.base(),
+ __result.base()),
+ __result._M_sequence);
+
+ return std::__copy_move_a<_IsMove>(__first.base(), __last.base(),
+ __result);
+ }
+
+ return std::__copy_move_a1<_IsMove>(__first, __last, __result);
+ }
+
+ template<bool _IsMove,
+ typename _Ite, typename _Seq, typename _Cat, typename _OI>
+ _OI
+ __copy_move_backward_a(
+ const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
+ const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __last,
+ _OI __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<_Ite>::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, -__dist.first);
+
+ if (__dist.second > ::__gnu_debug::__dp_equality)
+ return std::__copy_move_backward_a<_IsMove>(
+ __first.base(), __last.base(), __result);
+
+ return std::__copy_move_backward_a1<_IsMove>(__first, __last, __result);
+ }
+
+ template<bool _IsMove,
+ typename _II, typename _Ite, typename _Seq, typename _Cat>
+ __gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
+ __copy_move_backward_a(_II __first, _II __last,
+ const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<_II>::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, -__dist.first);
+
+ if (__dist.second > ::__gnu_debug::__dp_sign
+ && __result._M_can_advance(-__dist.first, true))
+ return ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>(
+ std::__copy_move_backward_a<_IsMove>(__first, __last,
+ __result.base()),
+ __result._M_sequence);
+
+ return std::__copy_move_backward_a1<_IsMove>(__first, __last, __result);
+ }
+
+ template<bool _IsMove,
+ typename _IIte, typename _ISeq, typename _ICat,
+ typename _OIte, typename _OSeq, typename _OCat>
+ ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>
+ __copy_move_backward_a(
+ const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>& __first,
+ const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>& __last,
+ const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>& __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<_IIte>::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, -__dist.first);
+
+ if (__dist.second > ::__gnu_debug::__dp_equality)
+ {
+ if (__dist.second > ::__gnu_debug::__dp_sign
+ && __result._M_can_advance(-__dist.first, true))
+ return ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>(
+ std::__copy_move_backward_a<_IsMove>(__first.base(), __last.base(),
+ __result.base()),
+ __result._M_sequence);
+
+ return std::__copy_move_backward_a<_IsMove>(
+ __first.base(), __last.base(), __result);
+ }
+
+ return std::__copy_move_backward_a1<_IsMove>(__first, __last, __result);
+ }
+
+ template<typename _Ite, typename _Seq, typename _Cat, typename _Tp>
+ void
+ __fill_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
+ const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __last,
+ const _Tp& __value)
+ {
+ typename ::__gnu_debug::_Distance_traits<_Ite>::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+
+ if (__dist.second > ::__gnu_debug::__dp_equality)
+ std::__fill_a(__first.base(), __last.base(), __value);
+
+ std::__fill_a1(__first, __last, __value);
+ }
+
+ template<typename _Ite, typename _Seq, typename _Cat, typename _Size,
+ typename _Tp>
+ ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
+ __fill_n_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
+ _Size __n, const _Tp& __value,
+ std::input_iterator_tag)
+ {
+#if __cplusplus >= 201103L
+ static_assert(is_integral<_Size>{}, "fill_n must pass integral size");
+#endif
+
+ if (__n <= 0)
+ return __first;
+
+ __glibcxx_check_can_increment(__first, __n);
+ if (__first._M_can_advance(__n, true))
+ return ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>(
+ std::__fill_n_a(__first.base(), __n, __value, _Cat()),
+ __first._M_sequence);
+
+ return std::__fill_n_a1(__first, __n, __value);
+ }
+
+ template<typename _II1, typename _Seq1, typename _Cat1, typename _II2>
+ bool
+ __equal_aux(
+ const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>& __first1,
+ const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>& __last1,
+ _II2 __first2)
+ {
+ typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist;
+ __glibcxx_check_valid_range2(__first1, __last1, __dist);
+ __glibcxx_check_can_increment(__first2, __dist.first);
+
+ if (__dist.second > ::__gnu_debug::__dp_equality)
+ return std::__equal_aux(__first1.base(), __last1.base(), __first2);
+
+ return std::__equal_aux1(__first1, __last1, __first2);
+ }
+
+ template<typename _II1, typename _II2, typename _Seq2, typename _Cat2>
+ bool
+ __equal_aux(_II1 __first1, _II1 __last1,
+ const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>& __first2)
+ {
+ typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist;
+ __glibcxx_check_valid_range2(__first1, __last1, __dist);
+ __glibcxx_check_can_increment(__first2, __dist.first);
+
+ if (__dist.second > ::__gnu_debug::__dp_sign
+ && __first2._M_can_advance(__dist.first, true))
+ return std::__equal_aux(__first1, __last1, __first2.base());
+
+ return std::__equal_aux1(__first1, __last1, __first2);
+ }
+
+ template<typename _II1, typename _Seq1, typename _Cat1,
+ typename _II2, typename _Seq2, typename _Cat2>
+ bool
+ __equal_aux(
+ const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>& __first1,
+ const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>& __last1,
+ const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>& __first2)
+ {
+ typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist;
+ __glibcxx_check_valid_range2(__first1, __last1, __dist);
+ __glibcxx_check_can_increment(__first2, __dist.first);
+
+ if (__dist.second > ::__gnu_debug::__dp_equality)
+ {
+ if (__dist.second > ::__gnu_debug::__dp_sign &&
+ __first2._M_can_advance(__dist.first, true))
+ return std::__equal_aux(__first1.base(), __last1.base(),
+ __first2.base());
+ return std::__equal_aux(__first1.base(), __last1.base(), __first2);
+ }
+
+ return __equal_aux1(__first1, __last1, __first2);
+ }
+
+_GLIBCXX_END_NAMESPACE_VERSION
+} // namespace std
+
#endif
diff --git a/libstdc++-v3/include/debug/stl_iterator.h b/libstdc++-v3/include/debug/stl_iterator.h
index 3b9ee5d9beb..8a7c19428a6 100644
--- a/libstdc++-v3/include/debug/stl_iterator.h
+++ b/libstdc++-v3/include/debug/stl_iterator.h
@@ -115,17 +115,4 @@ namespace __gnu_debug
#endif
}
-namespace std
-{
-_GLIBCXX_BEGIN_NAMESPACE_VERSION
-
- template<typename _Iterator, typename _Container, typename _Sequence>
- _Iterator
- __niter_base(const __gnu_debug::_Safe_iterator<
- __gnu_cxx::__normal_iterator<_Iterator, _Container>,
- _Sequence, std::random_access_iterator_tag>&);
-
-_GLIBCXX_END_NAMESPACE_VERSION
-}
-
#endif
diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector
index 56b5e140fd3..8138600f143 100644
--- a/libstdc++-v3/include/debug/vector
+++ b/libstdc++-v3/include/debug/vector
@@ -794,13 +794,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
};
#endif
- template<typename _Iterator, typename _Container, typename _Sequence>
- _Iterator
- __niter_base(const __gnu_debug::_Safe_iterator<
- __gnu_cxx::__normal_iterator<_Iterator, _Container>,
- _Sequence, std::random_access_iterator_tag>& __it)
- { return std::__niter_base(__it.base()); }
-
#if __cplusplus >= 201703L
namespace __detail::__variant
{
diff --git a/libstdc++-v3/include/std/numeric b/libstdc++-v3/include/std/numeric
index a164a9e6430..0135db889c6 100644
--- a/libstdc++-v3/include/std/numeric
+++ b/libstdc++-v3/include/std/numeric
@@ -229,12 +229,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
/// @addtogroup numeric_ops
/// @{
- /// @cond undocumented
- template<typename _It, typename _Cat = __iterator_category_t<_It>>
- using __is_random_access_iter
- = is_base_of<random_access_iterator_tag, _Cat>;
- /// @endcond
-
/**
* @brief Calculate reduction of values in a range.
*
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/debug/1_neg.cc b/libstdc++-v3/testsuite/25_algorithms/copy/debug/1_neg.cc
new file mode 100644
index 00000000000..f5a396e811d
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/debug/1_neg.cc
@@ -0,0 +1,41 @@
+// Copyright (C) 2019 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/>.
+
+// 25.2.1 [lib.alg.copy] Copy.
+
+// { dg-do run { xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <list>
+#include <vector>
+
+void
+test01()
+{
+ std::list<int> l(10, 1);
+ std::vector<int> v(5, 0);
+
+ std::copy(++l.begin(), --l.end(), v.begin());
+}
+
+int
+main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/2.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/2.cc
index c9305718389..7b0dc3d2126 100644
--- a/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/2.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/2.cc
@@ -16,6 +16,8 @@
// <http://www.gnu.org/licenses/>.
#include <algorithm>
+#include <vector>
+#include <list>
#include <deque>
#include <testsuite_hooks.h>
@@ -51,9 +53,57 @@ void test02()
VERIFY( equal(dest.begin(), dest.end(), cd.begin()) );
}
+void test03()
+{
+ using namespace std;
+
+ deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ d.pop_front();
+ d.pop_back();
+
+ vector<int> dest(d.size(), 0);
+
+ copy(d.begin(), d.end(), dest.begin());
+ VERIFY( equal(dest.begin(), dest.end(), d.begin()) );
+}
+
+void test04()
+{
+ using namespace std;
+
+ vector<int> v;
+ for (int i = 0; i != 1024; ++i)
+ v.push_back(i);
+
+ deque<int> dest(v.size() - 10, 0);
+
+ std::copy(v.begin() + 5, v.end() - 5, dest.begin());
+ VERIFY( std::equal(dest.begin(), dest.end(), v.begin() + 5) );
+}
+
+void test05()
+{
+ using namespace std;
+
+ std::list<int> l;
+ for (int i = 0; i != 1024; ++i)
+ l.push_back(i);
+
+ std::deque<int> dest(l.size(), 0);
+
+ std::copy(l.begin(), l.end(), dest.begin());
+ VERIFY( std::equal(dest.begin(), dest.end(), l.begin()) );
+}
+
int main()
{
test01();
test02();
+ test03();
+ test04();
+ test05();
return 0;
}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/31.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/31.cc
new file mode 100644
index 00000000000..ae2c33b1d10
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/31.cc
@@ -0,0 +1,43 @@
+// Copyright (C) 2019 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-do run { xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+#include <vector>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::vector<int> dest(d.size(), 0);
+
+ const std::deque<int>& cd = d;
+ std::copy(cd.begin() + 10, cd.begin() + 5, dest.begin());
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/32.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/32.cc
new file mode 100644
index 00000000000..8028bd6b542
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/32.cc
@@ -0,0 +1,43 @@
+// Copyright (C) 2019 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-do run { xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+#include <vector>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::vector<int> dest(d.size() / 2, 0);
+
+ const std::deque<int>& cd = d;
+ std::copy(cd.begin(), cd.end(), dest.begin());
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/33.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/33.cc
new file mode 100644
index 00000000000..1633fafd20c
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/33.cc
@@ -0,0 +1,57 @@
+// Copyright (C) 2019 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-do run { xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+#include <list>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::list<int> dest(d.size(), 0);
+
+ const std::deque<int>& cd = d;
+ std::copy(cd.begin(), cd.end(), dest.begin());
+}
+
+void test02()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::list<int> dest(d.size() / 2, 0);
+ std::list<int>::iterator lit = dest.begin();
+
+ const std::deque<int>& cd = d;
+ std::copy(cd.begin(), cd.end(), ++lit);
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/41.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/41.cc
new file mode 100644
index 00000000000..0c9d949807a
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/41.cc
@@ -0,0 +1,42 @@
+// Copyright (C) 2019 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-do run { xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+#include <vector>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::vector<int> dest(d.size(), 0);
+
+ std::copy(d.begin() + 10, d.begin() + 5, dest.begin());
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/42.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/42.cc
new file mode 100644
index 00000000000..c7e0c1f49fd
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/42.cc
@@ -0,0 +1,42 @@
+// Copyright (C) 2019 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-do run { xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+#include <vector>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::vector<int> dest(d.size() / 2, 0);
+
+ std::copy(d.begin(), d.end(), dest.begin());
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/43.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/43.cc
new file mode 100644
index 00000000000..2f29afae09f
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/43.cc
@@ -0,0 +1,55 @@
+// Copyright (C) 2019 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-do run { xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+#include <list>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::list<int> dest(d.size(), 0);
+
+ std::copy(d.begin(), d.end(), dest.begin());
+}
+
+void test02()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::list<int> dest(d.size() / 2, 0);
+ std::list<int>::iterator lit = dest.begin();
+
+ std::copy(d.begin(), d.end(), ++lit);
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/streambuf_iterators/char/4.cc b/libstdc++-v3/testsuite/25_algorithms/copy/streambuf_iterators/char/4.cc
index 0709a4077ac..3fd4e271521 100644
--- a/libstdc++-v3/testsuite/25_algorithms/copy/streambuf_iterators/char/4.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/streambuf_iterators/char/4.cc
@@ -21,6 +21,8 @@
#include <fstream>
#include <algorithm>
#include <cstring>
+#include <vector>
+
#include <testsuite_hooks.h>
// { dg-require-fileio "" }
@@ -33,7 +35,7 @@ void test01()
typedef istreambuf_iterator<char> in_iterator_type;
ifstream fbuf_ref("istream_unformatted-1.txt"),
- fbuf("istream_unformatted-1.txt");
+ fbuf("istream_unformatted-1.txt");
char buffer_ref[16500],
buffer[16500];
@@ -50,8 +52,33 @@ void test01()
VERIFY( !memcmp(buffer, buffer_ref, 16500) );
}
+void test02()
+{
+ using namespace std;
+
+ typedef istreambuf_iterator<char> in_iterator_type;
+
+ ifstream fbuf_ref("istream_unformatted-1.txt"),
+ fbuf("istream_unformatted-1.txt");
+
+ char buffer_ref[16500];
+ std::vector<char> buffer(16500, 'a');
+
+ fbuf_ref.read(buffer_ref, 16500);
+
+ in_iterator_type beg(fbuf);
+ in_iterator_type end;
+ copy(beg, end, buffer.begin());
+
+ VERIFY( fbuf_ref.good() );
+ VERIFY( fbuf.good() );
+
+ VERIFY( !memcmp(buffer.data(), buffer_ref, 16500) );
+}
+
int main()
{
test01();
+ test02();
return 0;
}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy_backward/deque_iterators/2.cc b/libstdc++-v3/testsuite/25_algorithms/copy_backward/deque_iterators/2.cc
index 1503e4e5e6f..ccde5279859 100644
--- a/libstdc++-v3/testsuite/25_algorithms/copy_backward/deque_iterators/2.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/copy_backward/deque_iterators/2.cc
@@ -16,6 +16,8 @@
// <http://www.gnu.org/licenses/>.
#include <algorithm>
+#include <vector>
+#include <list>
#include <deque>
#include <testsuite_hooks.h>
@@ -51,9 +53,57 @@ void test02()
VERIFY( equal(dest.begin(), dest.end(), cd.begin()) );
}
+void test03()
+{
+ using namespace std;
+
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ d.pop_front();
+ d.pop_back();
+
+ std::vector<int> dest(d.size(), 0);
+
+ std::copy_backward(d.begin(), d.end(), dest.end());
+ VERIFY( std::equal(dest.begin(), dest.end(), d.begin()) );
+}
+
+void test04()
+{
+ using namespace std;
+
+ std::vector<int> v;
+ for (int i = 0; i != 1024; ++i)
+ v.push_back(i);
+
+ std::deque<int> dest(v.size() - 10, 0);
+
+ std::copy_backward(v.begin() + 5, v.end() - 5, dest.end());
+ VERIFY( std::equal(v.begin() + 5, v.end() - 5, dest.begin()) );
+}
+
+void test05()
+{
+ using namespace std;
+
+ std::list<int> l;
+ for (int i = 0; i != 1024; ++i)
+ l.push_back(i);
+
+ std::deque<int> dest(l.size(), 0);
+
+ std::copy_backward(l.begin(), l.end(), dest.end());
+ VERIFY( std::equal(dest.begin(), dest.end(), l.begin()) );
+}
+
int main()
{
test01();
test02();
+ test03();
+ test04();
+ test05();
return 0;
}
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/1.cc b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/1.cc
new file mode 100644
index 00000000000..b99cf1df538
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/1.cc
@@ -0,0 +1,122 @@
+// Copyright (C) 2019 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/>.
+
+#include <algorithm>
+#include <vector>
+#include <deque>
+
+#include <ext/new_allocator.h>
+#include <ext/malloc_allocator.h>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ deque<int> d;
+ for (int i = 0; i != _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i)
+ d.push_back(i);
+
+ const deque<int>& cd = d;
+
+ VERIFY( equal(cd.begin(), cd.end(), cd.begin()) );
+ VERIFY( equal(cd.begin(), cd.end(), d.begin()) );
+ VERIFY( equal(d.begin(), d.end(), d.begin()) );
+ VERIFY( equal(d.begin(), d.end(), cd.begin()) );
+}
+
+void test02()
+{
+ using namespace std;
+
+ deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i % 10);
+
+ VERIFY( equal(d.begin(), d.begin() + 10, d.begin() + 20) );
+ VERIFY( equal(d.begin() + 10, d.end() - 10, d.begin()) );
+
+ const deque<int>& cd = d;
+
+ VERIFY( equal(cd.begin(), cd.begin() + 10, cd.begin() + 20) );
+ VERIFY( equal(cd.begin() + 10, cd.end() - 10, d.begin()) );
+ VERIFY( equal(d.begin() + 10, d.end() - 10, cd.begin()) );
+}
+
+void test03()
+{
+ using namespace std;
+
+ deque<int> d1;
+ for (int i = 0; i != 1024; ++i)
+ d1.push_back(i % 10);
+
+ deque<int> d2(d1);
+ for (int i = 0; i != 10; ++i)
+ d2.pop_front();
+
+ VERIFY( equal(d1.begin(), d1.begin() + 10, d2.begin()) );
+ VERIFY( equal(d1.begin() + 10, d1.end() - 10, d2.begin()) );
+
+ const deque<int>& cd1 = d1;
+ const deque<int>& cd2 = d2;
+
+ VERIFY( equal(cd1.begin(), cd1.begin() + 10, cd2.begin() + 20) );
+ VERIFY( equal(cd1.begin() + 10, cd1.end() - 10, d2.begin()) );
+ VERIFY( equal(cd2.begin() + 10, cd2.end() - 10, cd1.begin()) );
+}
+
+void test04()
+{
+ using namespace std;
+
+ deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ vector<int> v(d.begin(), d.end());
+
+ VERIFY( equal(d.begin(), d.end(), v.begin()) );
+ VERIFY( equal(v.begin(), v.end(), d.begin()) );
+
+ const deque<int>& cd = d;
+
+ VERIFY( equal(cd.begin(), cd.end(), v.begin()) );
+ VERIFY( equal(v.begin(), v.end(), cd.begin()) );
+}
+
+void test05()
+{
+ using namespace std;
+
+ int a[] { 0, 1, 2, 3, 4 };
+ deque<int, __gnu_cxx::new_allocator<int> > d1(a, a + 5);
+ deque<int, __gnu_cxx::malloc_allocator<int> > d2(a, a + 5);
+
+ VERIFY( equal(d1.begin(), d1.end(), d2.begin()) );
+}
+
+int main()
+{
+ test01();
+ test02();
+ test03();
+ test04();
+ test05();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/move/deque_iterators/2.cc b/libstdc++-v3/testsuite/25_algorithms/move/deque_iterators/2.cc
index 0ff1896dd4d..1f7930036d1 100644
--- a/libstdc++-v3/testsuite/25_algorithms/move/deque_iterators/2.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/move/deque_iterators/2.cc
@@ -17,6 +17,8 @@
// <http://www.gnu.org/licenses/>.
#include <algorithm>
+#include <vector>
+#include <list>
#include <deque>
#include <testsuite_hooks.h>
@@ -52,9 +54,48 @@ void test02()
VERIFY( equal(dest.begin(), dest.end(), cd.begin()) );
}
+void test03()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::vector<int> dest(d.size(), 0);
+
+ std::move(d.begin(), d.end(), dest.begin());
+ VERIFY( std::equal(dest.begin(), dest.end(), d.begin()) );
+}
+
+void test04()
+{
+ std::vector<int> v;
+ for (int i = 0; i != 1024; ++i)
+ v.push_back(i);
+
+ std::deque<int> dest(v.size() - 10, 0);
+
+ std::move(v.begin() + 5, v.end() - 5, dest.begin());
+ VERIFY( std::equal(dest.begin(), dest.end(), v.begin() + 5) );
+}
+
+void test05()
+{
+ std::list<int> l;
+ for (int i = 0; i != 1024; ++i)
+ l.push_back(i);
+
+ std::deque<int> dest(l.size(), 0);
+
+ std::move(l.begin(), l.end(), dest.begin());
+ VERIFY( std::equal(dest.begin(), dest.end(), l.begin()) );
+}
+
int main()
{
test01();
test02();
+ test03();
+ test04();
+ test05();
return 0;
}
diff --git a/libstdc++-v3/testsuite/25_algorithms/move_backward/deque_iterators/2.cc b/libstdc++-v3/testsuite/25_algorithms/move_backward/deque_iterators/2.cc
index 6acc0426aa7..82fff3e20c8 100644
--- a/libstdc++-v3/testsuite/25_algorithms/move_backward/deque_iterators/2.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/move_backward/deque_iterators/2.cc
@@ -17,6 +17,8 @@
// <http://www.gnu.org/licenses/>.
#include <algorithm>
+#include <vector>
+#include <list>
#include <deque>
#include <testsuite_hooks.h>
@@ -52,9 +54,48 @@ void test02()
VERIFY( equal(dest.begin(), dest.end(), cd.begin()) );
}
+void test03()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::vector<int> dest(d.size(), 0);
+
+ std::move_backward(d.begin(), d.end(), dest.end());
+ VERIFY( std::equal(dest.begin(), dest.end(), d.begin()) );
+}
+
+void test04()
+{
+ std::vector<int> v;
+ for (int i = 0; i != 1024; ++i)
+ v.push_back(i);
+
+ std::deque<int> dest(v.size() - 10, 0);
+
+ std::move_backward(v.begin() + 5, v.end() - 5, dest.end());
+ VERIFY( std::equal(dest.begin(), dest.end(), v.begin() + 5) );
+}
+
+void test05()
+{
+ std::list<int> l;
+ for (int i = 0; i != 1024; ++i)
+ l.push_back(i);
+
+ std::deque<int> dest(l.size(), 0);
+
+ std::move_backward(l.begin(), l.end(), dest.end());
+ VERIFY( std::equal(dest.begin(), dest.end(), l.begin()) );
+}
+
int main()
{
test01();
test02();
+ test03();
+ test04();
+ test05();
return 0;
}
