This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: PR 90409 Deque fiil/copy/move/copy_backward/move_backward/equal overloads
On 8/1/19 2:53 PM, Jonathan Wakely wrote:
On 01/08/19 13:52 +0100, Jonathan Wakely wrote:
On 01/08/19 13:31 +0200, Daniel Krügler wrote:
Am Do., 1. Aug. 2019 um 13:01 Uhr schrieb Jonathan Wakely
<jwakely@redhat.com>:
On 01/08/19 12:36 +0200, Daniel Krügler wrote:
Am Do., 1. Aug. 2019 um 11:57 Uhr schrieb Jonathan Wakely
<jwakely@redhat.com>:
More comments inline below ...
[..]
>François
>
>On 6/19/19 7:32 PM, François Dumont wrote:
>>I wanted to implement Debug overloads for those already existing
>>overloads but then realized that those algos could be generalized.
>>This way we will benefit from the memmove replacement when
operating
>>with C array or std::array or std::vector iterators.
>>
>>I might do the same for lexicographical_compare one day.
>>
>>The ChangeLog below is quite huge so I attached it. I wonder if I
>>could use deque::iterator and deque::const_iterator in place of
the
>>_Deque_iterator<> to reduce it ?
>>
>>Tested under Linux x86_64 normal and debug modes, ok to commit ?
>>
>>François
>>
>
>diff --git a/libstdc++-v3/include/bits/deque.tcc
b/libstdc++-v3/include/bits/deque.tcc
>index 3f77b4f079c..9db869fb666 100644
>--- a/libstdc++-v3/include/bits/deque.tcc
>+++ b/libstdc++-v3/include/bits/deque.tcc
>@@ -967,155 +967,507 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> this->_M_impl._M_finish._M_set_node(__new_nstart +
__old_num_nodes - 1);
> }
>
[..]
And anyway, isn't _Deque_iterator<T, T&, T*>::_Self just the same
type as
_Deque_iterator<T, T&, T*> ? It should be something like:
typedef typename _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&,
_Tp*> _Iter;
>+ template<typename _II, typename _Tp>
>+ typename enable_if<
>+ is_same<typename
std::iterator_traits<_II>::iterator_category,
>+ std::random_access_iterator_tag>::value,
Use is_base_of<random_access_iterator_tag,
...::iterator_category> so
it works for types derived from random_access_iterator_tag too.
Interesting. Traditional type tag dispatching approaches (as function
parameters) do have more in a manner that would be equivalent to an
implicit conversion (Being used as "by-value-parameters"), so I'm
wondering whether this should not instead refer to is_convertible? I
also found examples where this trait is currently used in
<stl_algo.h>
such as
static_assert(
__or_<is_convertible<__pop_cat, forward_iterator_tag>,
is_convertible<__samp_cat,
random_access_iterator_tag>>::value,
"output range must use a RandomAccessIterator when input range"
" does not meet the ForwardIterator requirements");
Should possibly this trait be preferred?
Hmm, I don't know why I did it that way in sample.
The standard requires derivation in a couple of places today, see
[reverse.iterator] bullet 2.1 and [move.iterator] bullet 1.1 which use
DerivedFrom<random_access_iterator_tag> to check whether the base
iterator is random access or not.
If you want to mimic DerivedFrom you also need to include
is_convertible in some way, because is_base_of does not care about
access.
Ah yes, that's probably why I used is_convertible :-)
Maybe introduce __is_derived_from?
Whatever we do, we should make it work for C++98 too, as that's needed
for François's patch. I wonder if it's good enough to just check if
iterator_traits<I>::iterator_category* converts to
random_access_iterator_tag*.
So rather than a generic is_derived_from, just a check for
is_random_access, as that's all we need here.
I already added a C++11-and-later version of that to <numeric>, but
forgot to check that the base is public and unambiguous:
template<typename _It, typename _Traits = iterator_traits<_It>,
typename _Cat = typename _Traits::iterator_category>
using __is_random_access_iter
= is_base_of<random_access_iterator_tag, _Cat>;
I use it in this new patch making it compatible for C++98.
I haven't added the is_convertible. It seems strange to use
random_access_iterator_tag to hide it but if you think otherwise I can
try to add it.
Performance enhancements are very good.
Before:
copy_deque_iterators.cc deque 2 deque 735r 733u
0s 0mem 0pf
copy_deque_iterators.cc deque 2 vector 3420r 3419u
0s 0mem 0pf
copy_deque_iterators.cc vector 2 deque 3197r 3196u
0s 0mem 0pf
copy_deque_iterators.cc int deque 2 char vector 3341r 3336u
0s 0mem 0pf
copy_deque_iterators.cc char vector 2 int deque 3136r 3134u
1s 0mem 0pf
copy_deque_iterators.cc deque 2 list 9941r 9940u
0s 0mem 0pf
copy_deque_iterators.cc list 2 deque 2273r 2274u
0s 0mem 0pf
After:
copy_deque_iterators.cc deque 2 deque 554r 553u
0s 0mem 0pf
copy_deque_iterators.cc deque 2 vector 316r 316u
0s 0mem 0pf
copy_deque_iterators.cc vector 2 deque 524r 523u
0s 0mem 0pf
copy_deque_iterators.cc int deque 2 char vector 1882r 1879u
0s 0mem 0pf
copy_deque_iterators.cc char vector 2 int deque 2199r 2192u
2s 0mem 0pf
copy_deque_iterators.cc deque 2 list 7630r 7625u
1s 0mem 0pf
copy_deque_iterators.cc list 2 deque 2254r 2254u
0s 0mem 0pf
Even deque 2 deque is enhanced which I don't explain. The good point is
that even if it eventually do not use memcpy it is still a good
enhancement. It behaves like a loop unrolling optimization I think. And
moreover the deque iterator arithmetic is more complicated than the
pointer one.
Note that 'list 2 deque' perf are identical which is normal as in this
case the copy overload is disabled. I hesitated but prefer to keep it,
let me know if I better remove it.
For std::equal the result are also very good:
Before:
equal_deque_iterators.cc deque vs deque 6275r 6274u
0s 0mem 0pf
equal_deque_iterators.cc deque vs vector 4277r 4277u
0s 0mem 0pf
equal_deque_iterators.cc vector vs deque 2280r 2280u
0s 0mem 0pf
equal_deque_iterators.cc int deque vs char vector 4263r 4263u
0s 0mem 0pf
equal_deque_iterators.cc char vector vs int deque 2390r 2390u
0s 0mem 0pf
After:
equal_deque_iterators.cc deque vs deque 555r 554u
0s 0mem 0pf
equal_deque_iterators.cc deque vs vector 201r 201u
0s 0mem 0pf
equal_deque_iterators.cc vector vs deque 360r 360u
0s 0mem 0pf
equal_deque_iterators.cc int deque vs char vector 1197r 1196u
0s 0mem 0pf
equal_deque_iterators.cc char vector vs int deque 1311r 1310u
0s 0mem 0pf
testsuite_file/25_algorithms tested under Linux x86_64.
Ok to commit after I run all the other tests ?
François
diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
index 3f77b4f079c..867b7c9e8d8 100644
--- a/libstdc++-v3/include/bits/deque.tcc
+++ b/libstdc++-v3/include/bits/deque.tcc
@@ -967,155 +967,488 @@ _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>
void
- fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
- const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
+ fill(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __last,
+ const _Tp& __value)
{
- typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
-
- for (typename _Self::_Map_pointer __node = __first._M_node + 1;
- __node < __last._M_node; ++__node)
- std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
if (__first._M_node != __last._M_node)
{
std::fill(__first._M_cur, __first._M_last, __value);
+
+ for (typename _Iter::_Map_pointer __node = __first._M_node + 1;
+ __node < __last._M_node; ++__node)
+ std::fill(*__node, *__node + _Iter::_S_buffer_size(), __value);
+
std::fill(__last._M_first, __last._M_cur, __value);
}
else
std::fill(__first._M_cur, __last._M_cur, __value);
}
+ namespace __detail
+ {
+ template<typename _Tp, typename _OI>
+ _OI
+ __copy_from_dit(
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+ const _Tp*>& __first,
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+ const _Tp*>& __last,
+ _OI __result)
+ {
+ typedef
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> _Iter;
+
+ if (__first._M_node != __last._M_node)
+ {
+ __result = std::copy(__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(*__node, *__node + _Iter::_S_buffer_size(),
+ __result);
+
+ return std::copy(__last._M_first, __last._M_cur, __result);
+ }
+
+ return std::copy(__first._M_cur, __last._M_cur, __result);
+ }
+
+ template<typename _II, typename _Tp>
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
+ __copy_to_dit(_II __first, _II __last,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
+ {
+ 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, __result._M_last - __result._M_cur);
+ std::copy(__first, __first + __clen, __result._M_cur);
+
+ __first += __clen;
+ __result += __clen;
+ __len -= __clen;
+ }
+
+ return __result;
+ }
+
+ template<typename _Tp, typename _OI>
+ _OI
+ __copy_backward_from_dit(
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+ const _Tp*>& __first,
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+ const _Tp*>& __last,
+ _OI __result)
+ {
+ typedef
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> _Iter;
+
+ if (__first._M_node != __last._M_node)
+ {
+ __result = std::copy_backward(__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_backward(*__node, *__node + _Iter::_S_buffer_size(),
+ __result);
+
+ return std::copy_backward(__first._M_cur, __first._M_last, __result);
+ }
+
+ return std::copy_backward(__first._M_cur, __last._M_cur, __result);
+ }
+
+ template<typename _II, typename _Tp>
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
+ __copy_backward_to_dit(
+ _II __first, _II __last,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
+ {
+ 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 __rlen = __result._M_cur - __result._M_first;
+ _Tp* __rend = __result._M_cur;
+ if (!__rlen)
+ {
+ __rlen = _Iter::_S_buffer_size();
+ __rend = *(__result._M_node - 1) + __rlen;
+ }
+
+ const difference_type __clen = std::min(__len, __rlen);
+ std::copy_backward(__last - __clen, __last, __rend);
+
+ __last -= __clen;
+ __result -= __clen;
+ __len -= __clen;
+ }
+
+ return __result;
+ }
+
+ template<typename _Tp, typename _II>
+ bool
+ __equal_from_dit(
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+ const _Tp*>& __first1,
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+ const _Tp*>& __last1,
+ _II __first2)
+ {
+ typedef
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> _Iter;
+
+ if (__first1._M_node != __last1._M_node)
+ {
+ if (!std::equal(__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(*__node, *__node + _Iter::_S_buffer_size(), __first2))
+ return false;
+
+ return std::equal(__last1._M_first, __last1._M_cur, __first2);
+ }
+
+ return std::equal(__first1._M_cur, __last1._M_cur, __first2);
+ }
+
+ template<typename _II, typename _Tp>
+ bool
+ __equal_to_dit(_II __first1, _II __last1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first2)
+ {
+ typedef
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> _Iter;
+ typedef typename _Iter::difference_type difference_type;
+
+ difference_type __len = __last1 - __first1;
+ while (__len > 0)
+ {
+ const difference_type __clen
+ = std::min(__len, __first2._M_last - __first2._M_cur);
+ if (!std::equal(__first1, __first1 + __clen, __first2._M_cur))
+ return false;
+
+ __first1 += __clen;
+ __len -= __clen;
+ __first2 += __clen;
+ }
+
+ return true;
+ }
+
+#if __cplusplus >= 201103L
+ template<typename _Tp, typename _OI>
+ _OI
+ __move_from_dit(
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+ const _Tp*>& __first,
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+ const _Tp*>& __last,
+ _OI __result)
+ {
+ typedef
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> _Iter;
+
+ if (__first._M_node != __last._M_node)
+ {
+ __result = std::move(__first._M_cur, __first._M_last, __result);
+
+ for (typename _Iter::_Map_pointer __node = __first._M_node + 1;
+ __node != __last._M_node; ++__node)
+ __result = std::move(*__node, *__node + _Iter::_S_buffer_size(),
+ __result);
+
+ return std::move(__last._M_first, __last._M_cur, __result);
+ }
+
+ return std::move(__first._M_cur, __last._M_cur, __result);
+ }
+
+ template<typename _II, typename _Tp>
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
+ __move_to_dit(_II __first, _II __last,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
+ {
+ 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, __result._M_last - __result._M_cur);
+ std::move(__first, __first + __clen, __result._M_cur);
+
+ __first += __clen;
+ __result += __clen;
+ __len -= __clen;
+ }
+
+ return __result;
+ }
+
+ template<typename _Tp, typename _OI>
+ _OI
+ __move_backward_from_dit(
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+ const _Tp*>& __first,
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+ const _Tp*>& __last,
+ _OI __result)
+ {
+ typedef
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> _Iter;
+
+ if (__first._M_node != __last._M_node)
+ {
+ __result = std::move_backward(__last._M_first, __last._M_cur,
+ __result);
+
+ for (typename _Iter::_Map_pointer __node = __last._M_node - 1;
+ __node != __first._M_node; --__node)
+ __result
+ = std::move_backward(*__node, *__node + _Iter::_S_buffer_size(),
+ __result);
+
+ return std::move_backward(__first._M_cur, __first._M_last, __result);
+ }
+
+ return std::move_backward(__first._M_cur, __last._M_cur, __result);
+ }
+
+ template<typename _II, typename _Tp>
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
+ __move_backward_to_dit(
+ _II __first, _II __last,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
+ {
+ 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 __rlen = __result._M_cur - __result._M_first;
+ _Tp* __rend = __result._M_cur;
+ if (!__rlen)
+ {
+ __rlen = _Iter::_S_buffer_size();
+ __rend = *(__result._M_node - 1) + __rlen;
+ }
+
+ const difference_type __clen = std::min(__len, __rlen);
+ std::move_backward(__last - __clen, __last, __rend);
+
+ __last -= __clen;
+ __result -= __clen;
+ __len -= __clen;
+ }
+
+ return __result;
+ }
+#endif // C++11
+ }
+
+ template<typename _Tp, typename _OI>
+ _OI
+ copy(_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
+ _OI __result)
+ {
+ __glibcxx_requires_can_increment_range(__first, __last, __result);
+
+ return __detail::__copy_from_dit(__first, __last, __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)
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
+ copy(_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __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;
+ __glibcxx_requires_can_increment_range(__first, __last, __result);
- 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);
- __first += __clen;
- __result += __clen;
- __len -= __clen;
- }
- return __result;
+ return __detail::__copy_from_dit(__first, __last, __result);
+ }
+
+ template<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(_II __first, _II __last,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
+ {
+ __glibcxx_requires_can_increment_range(__first, __last, __result);
+
+ return __detail::__copy_to_dit(__first, __last, __result);
+ }
+
+ template<typename _Tp, typename _OI>
+ _OI
+ copy_backward(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
+ _OI __result)
+ {
+ __glibcxx_requires_can_decrement_range(__first, __last, __result);
+
+ return __detail::__copy_backward_from_dit(__first, __last, __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)
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
+ copy_backward(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __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;
+ __glibcxx_requires_can_decrement_range(__first, __last, __result);
- difference_type __len = __last - __first;
- while (__len > 0)
- {
- difference_type __llen = __last._M_cur - __last._M_first;
- _Tp* __lend = __last._M_cur;
+ return __detail::__copy_backward_from_dit(__first, __last, __result);
+ }
- difference_type __rlen = __result._M_cur - __result._M_first;
- _Tp* __rend = __result._M_cur;
+ template<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_backward(_II __first, _II __last,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
+ {
+ __glibcxx_requires_can_decrement_range(__first, __last, __result);
- 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;
- }
+ return __detail::__copy_backward_to_dit(__first, __last, __result);
+ }
- const difference_type __clen = std::min(__len,
- std::min(__llen, __rlen));
- std::copy_backward(__lend - __clen, __lend, __rend);
- __last -= __clen;
- __result -= __clen;
- __len -= __clen;
- }
- return __result;
+ template<typename _Tp, typename _II>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II>::__value, bool>::__type
+ equal(_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __last1,
+ _II __first2)
+ {
+ __glibcxx_requires_can_increment_range(__first1, __last1, __first2);
+
+ return __detail::__equal_from_dit(__first1, __last1, __first2);
}
-#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)
+ bool
+ equal(_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __last1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first2)
{
- typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
- typedef typename _Self::difference_type difference_type;
+ __glibcxx_requires_can_increment_range(__first1, __last1, __first2);
- 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::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur);
- __first += __clen;
- __result += __clen;
- __len -= __clen;
- }
- return __result;
+ return __detail::__equal_from_dit(__first1, __last1, __first2);
+ }
+
+ template<typename _II, typename _Tp>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II>::__value, bool>::__type
+ equal(_II __first1, _II __last1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first2)
+ {
+ __glibcxx_requires_can_increment_range(__first1, __last1, __first2);
+
+ return __detail::__equal_to_dit(__first1, __last1, __first2);
+ }
+
+#if __cplusplus >= 201103L
+ template<typename _Tp, typename _OI>
+ _OI
+ move(_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
+ _OI __result)
+ {
+ __glibcxx_requires_can_increment_range(__first, __last, __result);
+
+ return __detail::__move_from_dit(__first, __last, __result);
}
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)
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
+ move(_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __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;
+ __glibcxx_requires_can_increment_range(__first, __last, __result);
- difference_type __len = __last - __first;
- while (__len > 0)
- {
- difference_type __llen = __last._M_cur - __last._M_first;
- _Tp* __lend = __last._M_cur;
+ return __detail::__move_from_dit(__first, __last, __result);
+ }
+
+ template<typename _II, typename _Tp>
+ typename enable_if<
+ __is_random_access_iter<_II>::value,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::type
+ move(_II __first, _II __last,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
+ {
+ __glibcxx_requires_can_increment_range(__first, __last, __result);
- difference_type __rlen = __result._M_cur - __result._M_first;
- _Tp* __rend = __result._M_cur;
+ return __detail::__move_to_dit(__first, __last, __result);
+ }
- 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;
- }
+ template<typename _Tp, typename _OI>
+ _OI
+ move_backward(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
+ _OI __result)
+ {
+ __glibcxx_requires_can_decrement_range(__first, __last, __result);
- const difference_type __clen = std::min(__len,
- std::min(__llen, __rlen));
- std::move_backward(__lend - __clen, __lend, __rend);
- __last -= __clen;
- __result -= __clen;
- __len -= __clen;
- }
- return __result;
+ return __detail::__move_backward_from_dit(__first, __last, __result);
}
-#endif
-_GLIBCXX_END_NAMESPACE_CONTAINER
+ template<typename _Tp>
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
+ move_backward(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
+ {
+ __glibcxx_requires_can_decrement_range(__first, __last, __result);
+
+ return __detail::__move_backward_from_dit(__first, __last, __result);
+ }
+
+ template<typename _II, typename _Tp>
+ typename enable_if<
+ __is_random_access_iter<_II>::value,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::type
+ move_backward(_II __first, _II __last,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
+ {
+ __glibcxx_requires_can_decrement_range(__first, __last, __result);
+
+ return __detail::__move_backward_to_dit(__first, __last, __result);
+ }
+#endif // C++11
+
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h
index ac76d681ff0..ff03ec08dd6 100644
--- a/libstdc++-v3/include/bits/stl_deque.h
+++ b/libstdc++-v3/include/bits/stl_deque.h
@@ -370,77 +370,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
@@ -2343,13 +2272,258 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
_GLIBCXX_END_NAMESPACE_CONTAINER
+ template<typename _Tp>
+ void
+ fill(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&,
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&,
+ const _Tp&);
+
+ template<typename _Tp, typename _OI>
+ _OI
+ copy(_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ _OI);
+
+ template<typename _Tp, typename _OI>
+ inline _OI
+ copy(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __last,
+ _OI __result)
+ {
+ typedef
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> _CIter;
+ return std::copy(_CIter(__first), _CIter(__last), __result);
+ }
+
+ template<typename _Tp>
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
+ copy(_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
+
+ template<typename _Tp>
+ inline _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
+ copy(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __last,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
+ {
+ typedef
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> _CIter;
+ return std::copy(_CIter(__first), _CIter(__last), __result);
+ }
+
+ template<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(_II, _II,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
+
+ template<typename _Tp, typename _OI>
+ _OI
+ copy_backward(_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ _OI);
+
+ template<typename _Tp, typename _OI>
+ inline _OI
+ copy_backward(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __last,
+ _OI __result)
+ {
+ typedef
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> _CIter;
+ return std::copy_backward(_CIter(__first), _CIter(__last), __result);
+ }
+
+ template<typename _Tp>
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
+ copy_backward(_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
+
+ template<typename _Tp>
+ inline _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
+ copy_backward(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __last,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
+ {
+ typedef
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> _CIter;
+ return std::copy_backward(_CIter(__first), _CIter(__last), __result);
+ }
+
+ template<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_backward(_II, _II,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
+
+ template<typename _Tp, typename _II>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II>::__value, bool>::__type
+ equal(_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ _II);
+
+ template<typename _Tp, typename _II>
+ inline typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II>::__value, bool>::__type
+ equal(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __last1,
+ _II __first2)
+ {
+ typedef
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> _CIter;
+ return std::equal(_CIter(__first1), _CIter(__last1), __first2);
+ }
+
+ template<typename _Tp>
+ bool
+ equal(_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>);
+
+ template<typename _Tp>
+ inline bool
+ equal(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __last1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first2)
+ {
+ typedef
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> _CIter;
+ return std::equal(_CIter(__first1), _CIter(__last1), __first2);
+ }
+
+ template<typename _Tp>
+ inline bool
+ equal(_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __last1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first2)
+ {
+ typedef
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> _CIter;
+ return std::equal(__first1, __last1, _CIter(__first2));
+ }
+
+ template<typename _Tp>
+ inline bool
+ equal(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __last1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first2)
+ {
+ typedef
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> _CIter;
+ return std::equal(_CIter(__first1), _CIter(__last1), _CIter(__first2));
+ }
+
+ template<typename _II, typename _Tp>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II>::__value, bool>::__type
+ equal(_II, _II,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>);
+
+ template<typename _II, typename _Tp>
+ inline typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II>::__value, bool>::__type
+ equal(_II __first1, _II __last1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first2)
+ {
+ typedef
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> _CIter;
+ return std::equal(__first1, __last1, _CIter(__first2));
+ }
+
#if __cplusplus >= 201103L
// std::allocator is safe, but it is not the only allocator
// for which this is valid.
template<class _Tp>
struct __is_bitwise_relocatable<_GLIBCXX_STD_C::deque<_Tp>>
: true_type { };
-#endif
+
+ template<typename _Tp, typename _OI>
+ _OI
+ move(_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ _OI);
+
+ template<typename _Tp, typename _OI>
+ inline _OI
+ move(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __last,
+ _OI __result)
+ {
+ typedef
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> _CIter;
+ return std::move(_CIter(__first), _CIter(__last), __result);
+ }
+
+ template<typename _Tp>
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
+ move(_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
+
+ template<typename _Tp>
+ inline _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
+ move(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __last,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
+ {
+ typedef
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> _CIter;
+ return std::move(_CIter(__first), _CIter(__last), __result);
+ }
+
+ template<typename _II, typename _Tp>
+ typename enable_if<
+ __is_random_access_iter<_II>::value,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::type
+ move(_II, _II,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
+
+ template<typename _Tp, typename _OI>
+ _OI
+ move_backward(_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ _OI);
+
+ template<typename _Tp, typename _OI>
+ inline _OI
+ move_backward(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __last,
+ _OI __result)
+ {
+ typedef
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> _CIter;
+ return std::move_backward(_CIter(__first), _CIter(__last), __result);
+ }
+
+ template<typename _Tp>
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
+ move_backward(_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
+
+ template<typename _Tp>
+ inline _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
+ move_backward(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __last,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
+ {
+ typedef
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> _CIter;
+ return std::move_backward(_CIter(__first), _CIter(__last), __result);
+ }
+
+ template<typename _II, typename _Tp>
+ typename enable_if<
+ __is_random_access_iter<_II>::value,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::type
+ move_backward(_II, _II,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
+#endif // C++11
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
diff --git a/libstdc++-v3/include/bits/stl_iterator_base_types.h b/libstdc++-v3/include/bits/stl_iterator_base_types.h
index af69dbb017a..8135f4857fc 100644
--- a/libstdc++-v3/include/bits/stl_iterator_base_types.h
+++ b/libstdc++-v3/include/bits/stl_iterator_base_types.h
@@ -213,6 +213,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
enable_if<is_convertible<typename
iterator_traits<_InIter>::iterator_category,
input_iterator_tag>::value>::type;
+
+ template<typename _It, typename _Traits = iterator_traits<_It>,
+ typename _Cat = typename _Traits::iterator_category>
+ 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
diff --git a/libstdc++-v3/include/debug/deque b/libstdc++-v3/include/debug/deque
index 973f39fced6..d15156f29a4 100644
--- a/libstdc++-v3/include/debug/deque
+++ b/libstdc++-v3/include/debug/deque
@@ -685,6 +685,600 @@ namespace __debug
{ __lhs.swap(__rhs); }
} // namespace __debug
+
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+ template<typename _Tp, typename _Alloc>
+ void
+ fill(const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc> >& __first,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc> >& __last,
+ const _Tp& __value)
+ {
+ __glibcxx_check_valid_range(__first, __last);
+ std::fill(__first.base(), __last.base(), __value);
+ }
+
+ template<typename _Tp, typename _Alloc, typename _OI>
+ _OI
+ copy(const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ __debug::deque<_Tp, _Alloc> >& __first,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ __debug::deque<_Tp, _Alloc> >& __last,
+ _OI __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+ const _Tp*> >::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, __dist.first);
+
+ return std::copy(__first.base(), __last.base(), __result);
+ }
+
+ template<typename _Tp, typename _Alloc, typename _OI>
+ _OI
+ copy(const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc> >& __first,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc> >& __last,
+ _OI __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, __dist.first);
+
+ return std::copy(__first.base(), __last.base(), __result);
+ }
+
+ template<typename _Tp, typename _Alloc1, typename _Alloc2>
+ ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc2> >
+ copy(const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ __debug::deque<_Tp, _Alloc1> >& __first,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ __debug::deque<_Tp, _Alloc1> >& __last,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc2> >& __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+ const _Tp*> >::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, __dist.first);
+
+ return ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc2> >(
+ std::copy(__first.base(), __last.base(), __result.base()),
+ __result._M_get_sequence());
+ }
+
+ template<typename _Tp, typename _Alloc1, typename _Alloc2>
+ ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc2> >
+ copy(const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc1> >& __first,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc1> >& __last,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc2> >& __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, __dist.first);
+
+ return ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc2> >(
+ std::copy(__first.base(), __last.base(), __result.base()),
+ __result._M_get_sequence());
+ }
+
+ template<typename _II, typename _Tp, typename _Alloc>
+ typename __gnu_cxx::__enable_if<
+ std::__is_random_access_iter<_II>::__value,
+ ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc> > >::__type
+ copy(_II __first, _II __last,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc> >& __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<_II>::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, __dist.first);
+
+ return ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc> >(
+ std::copy(::__gnu_debug::__unsafe(__first),
+ ::__gnu_debug::__unsafe(__last), __result.base()),
+ __result._M_get_sequence());
+ }
+
+ template<typename _Tp, typename _Alloc, typename _OI>
+ _OI
+ copy_backward(
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ __debug::deque<_Tp, _Alloc> >& __first,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ __debug::deque<_Tp, _Alloc> >& __last,
+ _OI __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+ const _Tp*> >::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, -__dist.first);
+
+ return std::copy_backward(__first.base(), __last.base(), __result);
+ }
+
+ template<typename _Tp, typename _Alloc, typename _OI>
+ inline _OI
+ copy_backward(
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc> >& __first,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc> >& __last,
+ _OI __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, -__dist.first);
+
+ return std::copy_backward(__first.base(), __last.base(), __result);
+ }
+
+ template<typename _Tp, typename _Alloc1, typename _Alloc2>
+ ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc2> >
+ copy_backward(
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ __debug::deque<_Tp, _Alloc1> >& __first,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ __debug::deque<_Tp, _Alloc1> >& __last,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc2> >& __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+ const _Tp*> >::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, -__dist.first);
+
+ return ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc2> >(
+ std::copy_backward(__first.base(), __last.base(), __result.base()),
+ __result._M_get_sequence());
+ }
+
+ template<typename _Tp, typename _Alloc1, typename _Alloc2>
+ ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc2> >
+ copy_backward(
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc1> >& __first,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc1> >& __last,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc2> >& __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, -__dist.first);
+
+ return ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc2> >(
+ std::copy_backward(__first.base(), __last.base(), __result.base()),
+ __result._M_get_sequence());
+ }
+
+ template<typename _II, typename _Tp, typename _Alloc>
+ typename __gnu_cxx::__enable_if<
+ std::__is_random_access_iter<_II>::__value,
+ ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc> > >::__type
+ copy_backward(_II __first, _II __last,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc> >& __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<_II>::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, -__dist.first);
+
+ return ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc> >(
+ std::copy_backward(::__gnu_debug::__unsafe(__first),
+ ::__gnu_debug::__unsafe(__last),
+ __result.base()),
+ __result._M_get_sequence());
+ }
+
+ template<typename _Tp, typename _Alloc, typename _II>
+ inline typename __gnu_cxx::__enable_if<
+ std::__is_random_access_iter<_II>::__value, bool>::__type
+ equal(const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ __debug::deque<_Tp, _Alloc> >& __first1,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ __debug::deque<_Tp, _Alloc> >& __last1,
+ _II __first2)
+ {
+ typename ::__gnu_debug::_Distance_traits<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> >::__type
+ __dist;
+ __glibcxx_check_valid_range2(__first1, __last1, __dist);
+ __glibcxx_check_can_increment(__first2, __dist.first);
+
+ return std::equal(__first1.base(), __last1.base(),
+ ::__gnu_debug::__unsafe(__first2));
+ }
+
+ template<typename _Tp, typename _Alloc, typename _II>
+ inline typename __gnu_cxx::__enable_if<
+ std::__is_random_access_iter<_II>::__value, bool>::__type
+ equal(const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc> >& __first1,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc> >& __last1,
+ _II __first2)
+ {
+ typename ::__gnu_debug::_Distance_traits<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
+ __dist;
+ __glibcxx_check_valid_range2(__first1, __last1, __dist);
+ __glibcxx_check_can_increment(__first2, __dist.first);
+
+ return std::equal(__first1.base(), __last1.base(),
+ ::__gnu_debug::__unsafe(__first2));
+ }
+
+ template<typename _Tp, typename _Alloc1, typename _Alloc2>
+ bool
+ equal(const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ __debug::deque<_Tp, _Alloc1> >& __first1,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ __debug::deque<_Tp, _Alloc1> >& __last1,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ __debug::deque<_Tp, _Alloc2> >& __first2)
+ {
+ typename ::__gnu_debug::_Distance_traits<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> >::__type
+ __dist;
+ __glibcxx_check_valid_range2(__first1, __last1, __dist);
+ __glibcxx_check_can_increment(__first2, __dist.first);
+
+ return std::equal(__first1.base(), __last1.base(), __first2.base());
+ }
+
+ template<typename _Tp, typename _Alloc1, typename _Alloc2>
+ bool
+ equal(const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc1> >& __first1,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc1> >& __last1,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ __debug::deque<_Tp, _Alloc2> >& __first2)
+ {
+ typename ::__gnu_debug::_Distance_traits<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
+ __dist;
+ __glibcxx_check_valid_range2(__first1, __last1, __dist);
+ __glibcxx_check_can_increment(__first2, __dist.first);
+
+ return std::equal(__first1.base(), __last1.base(), __first2.base());
+ }
+
+ template<typename _Tp, typename _Alloc1, typename _Alloc2>
+ bool
+ equal(const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ __debug::deque<_Tp, _Alloc1> >& __first1,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ __debug::deque<_Tp, _Alloc1> >& __last1,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc2> >& __first2)
+ {
+ typename ::__gnu_debug::_Distance_traits<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> >::__type
+ __dist;
+ __glibcxx_check_valid_range2(__first1, __last1, __dist);
+ __glibcxx_check_can_increment(__first2, __dist.first);
+
+ return std::equal(__first1.base(), __last1.base(), __first2.base());
+ }
+
+ template<typename _Tp, typename _Alloc1, typename _Alloc2>
+ bool
+ equal(const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc1> >& __first1,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc1> >& __last1,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc2> >& __first2)
+ {
+ typename ::__gnu_debug::_Distance_traits<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
+ __dist;
+ __glibcxx_check_valid_range2(__first1, __last1, __dist);
+ __glibcxx_check_can_increment(__first2, __dist.first);
+
+ return std::equal(__first1.base(), __last1.base(), __first2.base());
+ }
+
+ template<typename _II, typename _Tp, typename _Alloc>
+ typename __gnu_cxx::__enable_if<
+ std::__is_random_access_iter<_II>::__value, bool>::__type
+ equal(_II __first1, _II __last1,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ __debug::deque<_Tp, _Alloc> >& __first2)
+ {
+ __glibcxx_check_can_increment_range(__first1, __last1, __first2);
+
+ return std::equal(::__gnu_debug::__unsafe(__first1),
+ ::__gnu_debug::__unsafe(__last1),
+ __first2.base());
+ }
+
+ template<typename _II, typename _Tp, typename _Alloc>
+ typename __gnu_cxx::__enable_if<
+ std::__is_random_access_iter<_II>::__value, bool>::__type
+ equal(_II __first1, _II __last1,
+ const ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc> >& __first2)
+ {
+ __glibcxx_check_can_increment_range(__first1, __last1, __first2);
+
+ return std::equal(::__gnu_debug::__unsafe(__first1),
+ ::__gnu_debug::__unsafe(__last1),
+ __first2.base());
+ }
+
+#if __cplusplus >= 201103L
+
+ namespace __detail
+ {
+ template<typename _Tp, typename _Alloc>
+ using _SDeque_iterator = ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc> >;
+
+ template<typename _Tp, typename _Alloc>
+ using _SDeque_const_iterator = ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ __debug::deque<_Tp, _Alloc> >;
+ }
+
+ template<typename _Tp, typename _Alloc, typename _OI>
+ _OI
+ move(const __detail::_SDeque_const_iterator<_Tp, _Alloc>& __first,
+ const __detail::_SDeque_const_iterator<_Tp, _Alloc>& __last,
+ _OI __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+ const _Tp*> >::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, __dist.first);
+
+ return std::move(__first.base(), __last.base(), __result);
+ }
+
+ template<typename _Tp, typename _Alloc, typename _OI>
+ _OI
+ move(const __detail::_SDeque_iterator<_Tp, _Alloc>& __first,
+ const __detail::_SDeque_iterator<_Tp, _Alloc>& __last,
+ _OI __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, __dist.first);
+
+ return std::move(__first.base(), __last.base(), __result);
+ }
+
+ template<typename _Tp, typename _Alloc1, typename _Alloc2>
+ __detail::_SDeque_iterator<_Tp, _Alloc2>
+ move(const __detail::_SDeque_const_iterator<_Tp, _Alloc1>& __first,
+ const __detail::_SDeque_const_iterator<_Tp, _Alloc1>& __last,
+ const __detail::_SDeque_iterator<_Tp, _Alloc2>& __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+ const _Tp*> >::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, __dist.first);
+
+ return
+ {
+ std::move(__first.base(), __last.base(), __result.base()),
+ __result._M_get_sequence()
+ };
+ }
+
+ template<typename _Tp, typename _Alloc1, typename _Alloc2>
+ __detail::_SDeque_iterator<_Tp, _Alloc2>
+ move(const __detail::_SDeque_iterator<_Tp, _Alloc1>& __first,
+ const __detail::_SDeque_iterator<_Tp, _Alloc1>& __last,
+ const __detail::_SDeque_iterator<_Tp, _Alloc2>& __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, __dist.first);
+
+ return
+ {
+ std::move(__first.base(), __last.base(), __result.base()),
+ __result._M_get_sequence()
+ };
+ }
+
+ template<typename _II, typename _Tp, typename _Alloc>
+ typename enable_if<
+ std::__is_random_access_iter<_II>::value,
+ __detail::_SDeque_iterator<_Tp, _Alloc> >::type
+ move(_II __first, _II __last,
+ const __detail::_SDeque_iterator<_Tp, _Alloc>& __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<_II>::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, __dist.first);
+
+ return
+ {
+ std::move(::__gnu_debug::__unsafe(__first),
+ ::__gnu_debug::__unsafe(__last), __result.base()),
+ __result._M_get_sequence()
+ };
+ }
+
+ template<typename _Tp, typename _Alloc, typename _OI>
+ _OI
+ move_backward(
+ const __detail::_SDeque_const_iterator<_Tp, _Alloc>& __first,
+ const __detail::_SDeque_const_iterator<_Tp, _Alloc>& __last,
+ _OI __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+ const _Tp*> >::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, -__dist.first);
+
+ return std::move_backward(__first.base(), __last.base(), __result);
+ }
+
+ template<typename _Tp, typename _Alloc, typename _OI>
+ inline _OI
+ move_backward(const __detail::_SDeque_iterator<_Tp, _Alloc>& __first,
+ const __detail::_SDeque_iterator<_Tp, _Alloc>& __last,
+ _OI __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, -__dist.first);
+
+ return std::move_backward(__first.base(), __last.base(), __result);
+ }
+
+ template<typename _Tp, typename _Alloc1, typename _Alloc2>
+ __detail::_SDeque_iterator<_Tp, _Alloc2>
+ move_backward(
+ const __detail::_SDeque_const_iterator<_Tp, _Alloc1>& __first,
+ const __detail::_SDeque_const_iterator<_Tp, _Alloc1>& __last,
+ const __detail::_SDeque_iterator<_Tp, _Alloc2>& __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+ const _Tp*> >::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, -__dist.first);
+
+ return
+ {
+ std::move_backward(__first.base(), __last.base(), __result.base()),
+ __result._M_get_sequence()
+ };
+ }
+
+ template<typename _Tp, typename _Alloc1, typename _Alloc2>
+ __detail::_SDeque_iterator<_Tp, _Alloc2>
+ move_backward(
+ const __detail::_SDeque_iterator<_Tp, _Alloc1>& __first,
+ const __detail::_SDeque_iterator<_Tp, _Alloc1>& __last,
+ const __detail::_SDeque_iterator<_Tp, _Alloc2>& __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, -__dist.first);
+
+ return
+ {
+ std::move_backward(__first.base(), __last.base(), __result.base()),
+ __result._M_get_sequence()
+ };
+ }
+
+ template<typename _II, typename _Tp, typename _Alloc>
+ typename enable_if<
+ std::__is_random_access_iter<_II>::value,
+ __detail::_SDeque_iterator<_Tp, _Alloc> >::type
+ move_backward(_II __first, _II __last,
+ const __detail::_SDeque_iterator<_Tp, _Alloc>& __result)
+ {
+ typename ::__gnu_debug::_Distance_traits<_II>::__type __dist;
+ __glibcxx_check_valid_range2(__first, __last, __dist);
+ __glibcxx_check_can_increment(__result, -__dist.first);
+
+ return
+ {
+ std::move_backward(::__gnu_debug::__unsafe(__first),
+ ::__gnu_debug::__unsafe(__last), __result.base()),
+ __result._M_get_sequence()
+ };
+ }
+#endif
+
+_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
#endif
diff --git a/libstdc++-v3/include/std/numeric b/libstdc++-v3/include/std/numeric
index 239276946b5..0135db889c6 100644
--- a/libstdc++-v3/include/std/numeric
+++ b/libstdc++-v3/include/std/numeric
@@ -229,13 +229,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
/// @addtogroup numeric_ops
/// @{
- /// @cond undocumented
- template<typename _It, typename _Traits = iterator_traits<_It>,
- typename _Cat = typename _Traits::iterator_category>
- 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/deque_iterators/11_neg.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/11_neg.cc
new file mode 100644
index 00000000000..86594da0102
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/11_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/>.
+//
+// { dg-do run { xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::deque<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/12_neg.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/12_neg.cc
new file mode 100644
index 00000000000..1507e8903a1
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/12_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/>.
+//
+// { dg-do run { xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::deque<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/2.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/2.cc
new file mode 100644
index 00000000000..7b0dc3d2126
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/2.cc
@@ -0,0 +1,109 @@
+// 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 <list>
+#include <deque>
+
+#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);
+
+ deque<int> dest(d.size(), 0);
+
+ copy(d.begin(), d.end(), dest.begin());
+
+ VERIFY( equal(dest.begin(), dest.end(), d.begin()) );
+}
+
+void test02()
+{
+ using namespace std;
+
+ deque<int> d;
+ for (int i = 0; i != 4 * _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i)
+ d.push_back(i);
+
+ deque<int> dest(d.size(), 0);
+
+ const deque<int>& cd = d;
+ copy(cd.begin(), cd.end(), dest.begin());
+
+ 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/21_neg.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/21_neg.cc
new file mode 100644
index 00000000000..fc09f661b25
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/21_neg.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 <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::deque<int> dest(d.size(), 0);
+
+ const std::deque<int>& cd = d;
+ 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/22_neg.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/22_neg.cc
new file mode 100644
index 00000000000..64ff6c487e3
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/22_neg.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 <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::deque<int> dest(d.size() / 2, 0);
+
+ const std::deque<int>& cd = d;
+ copy(cd.begin(), cd.end(), dest.begin());
+}
+
+int main()
+{
+ test01();
+ 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/deque_iterators/51_neg.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/51_neg.cc
new file mode 100644
index 00000000000..eaaa8b3d2d6
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/51_neg.cc
@@ -0,0 +1,44 @@
+// 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 <iterator>
+
+#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;
+
+ const std::deque<int>& cd = d;
+ std::copy(cd.begin() + 10, cd.begin() + 5, std::back_inserter(dest));
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/61_neg.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/61_neg.cc
new file mode 100644
index 00000000000..f6b20f6ee0e
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/61_neg.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 <iterator>
+
+#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;
+
+ std::copy(d.begin() + 10, d.begin() + 5, std::back_inserter(dest));
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/71_neg.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/71_neg.cc
new file mode 100644
index 00000000000..063acf096f6
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/71_neg.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::vector<int> v;
+ for (int i = 0; i != 1024; ++i)
+ v.push_back(i);
+
+ std::deque<int> dest(v.size(), 0);
+
+ std::copy(v.begin() + 10, v.begin() + 5, dest.begin());
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/72_neg.cc b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/72_neg.cc
new file mode 100644
index 00000000000..855957ae1b6
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy/deque_iterators/72_neg.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::vector<int> v;
+ for (int i = 0; i != 1024; ++i)
+ v.push_back(i);
+
+ std::deque<int> dest(v.size() / 2, 0);
+
+ std::copy(v.begin(), v.end(), dest.begin());
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy_backward/deque_iterators/11_neg.cc b/libstdc++-v3/testsuite/25_algorithms/copy_backward/deque_iterators/11_neg.cc
new file mode 100644
index 00000000000..a497267f04f
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy_backward/deque_iterators/11_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/>.
+//
+// { dg-do run { xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::deque<int> dest(d.size(), 0);
+
+ std::copy_backward(d.begin() + 10, d.begin() + 5, dest.end());
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy_backward/deque_iterators/12_neg.cc b/libstdc++-v3/testsuite/25_algorithms/copy_backward/deque_iterators/12_neg.cc
new file mode 100644
index 00000000000..f30d9f3c3b7
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy_backward/deque_iterators/12_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/>.
+//
+// { dg-do run { xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::deque<int> dest(d.size() / 2, 0);
+
+ std::copy_backward(d.begin(), d.end(), dest.end());
+}
+
+int main()
+{
+ test01();
+ 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
new file mode 100644
index 00000000000..ccde5279859
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy_backward/deque_iterators/2.cc
@@ -0,0 +1,109 @@
+// 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 <list>
+#include <deque>
+
+#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);
+
+ deque<int> dest(d.size(), 0);
+
+ copy_backward(d.begin(), d.end(), dest.end());
+
+ VERIFY( equal(dest.begin(), dest.end(), d.begin()) );
+}
+
+void test02()
+{
+ using namespace std;
+
+ deque<int> d;
+ for (int i = 0; i != 4 * _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i)
+ d.push_back(i);
+
+ deque<int> dest(d.size(), 0);
+
+ const deque<int>& cd = d;
+ copy_backward(cd.begin(), cd.end(), dest.end());
+
+ 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/copy_backward/deque_iterators/21_neg.cc b/libstdc++-v3/testsuite/25_algorithms/copy_backward/deque_iterators/21_neg.cc
new file mode 100644
index 00000000000..aec11a81172
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy_backward/deque_iterators/21_neg.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 <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::deque<int> dest(d.size(), 0);
+
+ const std::deque<int>& cd = d;
+ copy_backward(cd.begin() + 10, cd.begin() + 5, dest.end());
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/copy_backward/deque_iterators/22_neg.cc b/libstdc++-v3/testsuite/25_algorithms/copy_backward/deque_iterators/22_neg.cc
new file mode 100644
index 00000000000..89db2024ac9
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/copy_backward/deque_iterators/22_neg.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 <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::deque<int> dest(d.size() / 2, 0);
+
+ const std::deque<int>& cd = d;
+ copy_backward(cd.begin(), cd.end(), dest.end());
+}
+
+int main()
+{
+ test01();
+ 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/equal/deque_iterators/10_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/10_neg.cc
new file mode 100644
index 00000000000..72f070b292d
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/10_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/>.
+
+// { dg-do run { xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ int a[] { 0, 1, 2 };
+ deque<int> d(a, a + 3);
+ const deque<int>& cd = d;
+
+ VERIFY( equal(cd.begin(), cd.end(), d.begin() + 2) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/11_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/11_neg.cc
new file mode 100644
index 00000000000..ae11f23d3b0
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/11_neg.cc
@@ -0,0 +1,40 @@
+// 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 <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ int a[] { 0, 1, 2 };
+ deque<int> d(a, a + 3);
+
+ VERIFY( equal(d.begin() + 2, d.begin(), d.begin()) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/12_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/12_neg.cc
new file mode 100644
index 00000000000..a0c2cece818
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/12_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/>.
+
+// { dg-do run { xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ int a[] { 0, 1, 2 };
+ deque<int> d(a, a + 3);
+ const deque<int>& cd = d;
+
+ VERIFY( equal(d.begin(), d.end(), d.begin() + 2) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/13_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/13_neg.cc
new file mode 100644
index 00000000000..b6f8519b1b2
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/13_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/>.
+
+// { dg-do run { xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ int a[] { 0, 1, 2 };
+ deque<int> d(a, a + 3);
+ const deque<int>& cd = d;
+
+ VERIFY( equal(a + 2, a, cd.begin()) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/14_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/14_neg.cc
new file mode 100644
index 00000000000..6dfea283516
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/14_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/>.
+
+// { dg-do run { xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ int a[] { 0, 1, 2 };
+ deque<int> d(a, a + 3);
+ const deque<int>& cd = d;
+
+ VERIFY( equal(a, a + 3, cd.begin() + 2) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/15_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/15_neg.cc
new file mode 100644
index 00000000000..fe0360a1842
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/15_neg.cc
@@ -0,0 +1,40 @@
+// 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 <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ int a[] { 0, 1, 2 };
+ deque<int> d(a, a + 3);
+
+ VERIFY( equal(a + 2, a, d.begin()) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/16_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/16_neg.cc
new file mode 100644
index 00000000000..8330edc9b2e
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/16_neg.cc
@@ -0,0 +1,40 @@
+// 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 <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ int a[] { 0, 1, 2 };
+ deque<int> d(a, a + 3);
+
+ VERIFY( equal(a, a + 3, d.begin() + 2) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/1_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/1_neg.cc
new file mode 100644
index 00000000000..1f26672b31d
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/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/>.
+
+// { dg-do run { xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ int a[] { 0, 1, 2 };
+ deque<int> d(a, a + 3);
+ const deque<int>& cd = d;
+
+ VERIFY( equal(cd.begin() + 2, cd.begin(), a) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/2_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/2_neg.cc
new file mode 100644
index 00000000000..caadc2b77d1
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/2_neg.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 <vector>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ int a[] { 0, 1, 2 };
+ deque<int> d(a, a + 3);
+ const deque<int>& cd = d;
+ vector<int> v;
+
+ VERIFY( equal(cd.begin(), cd.end(), v.begin()) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/3_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/3_neg.cc
new file mode 100644
index 00000000000..55ed05c0ae5
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/3_neg.cc
@@ -0,0 +1,40 @@
+// 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 <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ int a[] { 0, 1, 2 };
+ deque<int> d(a, a + 3);
+
+ VERIFY( equal(d.begin() + 2, d.begin(), a) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/4_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/4_neg.cc
new file mode 100644
index 00000000000..e67d4b19b42
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/4_neg.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 <vector>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ int a[] { 0, 1, 2 };
+ deque<int> d(a, a + 3);
+ vector<int> v;
+
+ VERIFY( equal(d.begin(), d.end(), v.begin()) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/5_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/5_neg.cc
new file mode 100644
index 00000000000..d737aa2edfc
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/5_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/>.
+
+// { dg-do run { xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ int a[] { 0, 1, 2 };
+ deque<int> d(a, a + 3);
+ const deque<int>& cd = d;
+
+ VERIFY( equal(cd.begin() + 2, cd.begin(), cd.begin()) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/6_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/6_neg.cc
new file mode 100644
index 00000000000..d1a74dd068a
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/6_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/>.
+
+// { dg-do run { xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ int a[] { 0, 1, 2 };
+ deque<int> d(a, a + 3);
+ const deque<int>& cd = d;
+
+ VERIFY( equal(cd.begin(), cd.end(), cd.begin() + 2) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/7_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/7_neg.cc
new file mode 100644
index 00000000000..e3c9cf1325f
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/7_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/>.
+
+// { dg-do run { xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ int a[] { 0, 1, 2 };
+ deque<int> d(a, a + 3);
+ const deque<int>& cd = d;
+
+ VERIFY( equal(d.begin() + 2, d.begin(), cd.begin()) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/8_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/8_neg.cc
new file mode 100644
index 00000000000..6078f598447
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/8_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/>.
+
+// { dg-do run { xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ int a[] { 0, 1, 2 };
+ deque<int> d(a, a + 3);
+ const deque<int>& cd = d;
+
+ VERIFY( equal(d.begin(), d.end(), cd.begin() + 2) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/9_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/9_neg.cc
new file mode 100644
index 00000000000..7dd86ce3ec8
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/deque_iterators/9_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/>.
+
+// { dg-do run { xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ int a[] { 0, 1, 2 };
+ deque<int> d(a, a + 3);
+ const deque<int>& cd = d;
+
+ VERIFY( equal(cd.begin() + 2, cd.begin(), d.begin()) );
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/fill/deque_iterators/1.cc b/libstdc++-v3/testsuite/25_algorithms/fill/deque_iterators/1.cc
new file mode 100644
index 00000000000..604ccb67fcd
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/fill/deque_iterators/1.cc
@@ -0,0 +1,58 @@
+// 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 <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ deque<char> d1;
+ for (int i = 0; i != _GLIBCXX_STD_C::__deque_buf_size(sizeof(char)); ++i)
+ d1.push_back((char)i);
+
+ deque<char> d2(d1.size(), '\0');
+
+ fill(d1.begin(), d1.end(), '\0');
+
+ VERIFY( equal(d1.begin(), d1.end(), d2.begin()) );
+}
+
+void test02()
+{
+ using namespace std;
+
+ deque<char> d1;
+ for (int i = 0; i != 4 * _GLIBCXX_STD_C::__deque_buf_size(sizeof(char)); ++i)
+ d1.push_back(i);
+
+ deque<char> d2(d1.size(), '\0');
+
+ fill(d1.begin(), d1.end(), '\0');
+
+ VERIFY( equal(d1.begin(), d1.end(), d2.begin()) );
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/fill/deque_iterators/1_neg.cc b/libstdc++-v3/testsuite/25_algorithms/fill/deque_iterators/1_neg.cc
new file mode 100644
index 00000000000..af25b2ef08a
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/fill/deque_iterators/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/>.
+//
+// { dg-do run { xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ deque<char> d;
+ for (int i = 0; i != _GLIBCXX_STD_C::__deque_buf_size(sizeof(char)); ++i)
+ d.push_back((char)i);
+
+ fill(d.begin() + 10, d.begin() + 5, '\0');
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/move/deque_iterators/11_neg.cc b/libstdc++-v3/testsuite/25_algorithms/move/deque_iterators/11_neg.cc
new file mode 100644
index 00000000000..d3dc432ff7b
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/move/deque_iterators/11_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/>.
+//
+// { dg-do run { target c++11 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::deque<int> dest(d.size(), 0);
+
+ std::move(d.begin() + 10, d.begin() + 5, dest.begin());
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/move/deque_iterators/12_neg.cc b/libstdc++-v3/testsuite/25_algorithms/move/deque_iterators/12_neg.cc
new file mode 100644
index 00000000000..b4079691b7c
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/move/deque_iterators/12_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/>.
+//
+// { dg-do run { target c++11 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::deque<int> dest(d.size() / 2, 0);
+
+ std::move(d.begin(), d.end(), dest.begin());
+}
+
+int main()
+{
+ test01();
+ 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
new file mode 100644
index 00000000000..1f7930036d1
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/move/deque_iterators/2.cc
@@ -0,0 +1,101 @@
+// { dg-do run { target c++11 } }
+// 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 <list>
+#include <deque>
+
+#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);
+
+ deque<int> dest(d.size(), 0);
+
+ move(d.begin(), d.end(), dest.begin());
+
+ VERIFY( equal(dest.begin(), dest.end(), d.begin()) );
+}
+
+void test02()
+{
+ using namespace std;
+
+ deque<int> d;
+ for (int i = 0; i != 4 * _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i)
+ d.push_back(i);
+
+ deque<int> dest(d.size(), 0);
+
+ const deque<int>& cd = d;
+ move(cd.begin(), cd.end(), dest.begin());
+
+ 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/deque_iterators/21_neg.cc b/libstdc++-v3/testsuite/25_algorithms/move/deque_iterators/21_neg.cc
new file mode 100644
index 00000000000..66245fb677b
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/move/deque_iterators/21_neg.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 { target c++11 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::deque<int> dest(d.size(), 0);
+
+ const std::deque<int>& cd = d;
+ move(cd.begin() + 10, cd.begin() + 5, dest.begin());
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/move/deque_iterators/22_neg.cc b/libstdc++-v3/testsuite/25_algorithms/move/deque_iterators/22_neg.cc
new file mode 100644
index 00000000000..ab69e9bab77
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/move/deque_iterators/22_neg.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 { target c++11 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::deque<int> dest(d.size() / 2, 0);
+
+ const std::deque<int>& cd = d;
+ move(cd.begin(), cd.end(), dest.begin());
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/move_backward/deque_iterators/11_neg.cc b/libstdc++-v3/testsuite/25_algorithms/move_backward/deque_iterators/11_neg.cc
new file mode 100644
index 00000000000..c5dbc14f8cc
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/move_backward/deque_iterators/11_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/>.
+//
+// { dg-do run { target c++11 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::deque<int> dest(d.size(), 0);
+
+ std::move_backward(d.begin() + 10, d.begin() + 5, dest.end());
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/move_backward/deque_iterators/12_neg.cc b/libstdc++-v3/testsuite/25_algorithms/move_backward/deque_iterators/12_neg.cc
new file mode 100644
index 00000000000..5718b5df141
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/move_backward/deque_iterators/12_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/>.
+//
+// { dg-do run { target c++11 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::deque<int> dest(d.size() / 2, 0);
+
+ std::move_backward(d.begin(), d.end(), dest.end());
+}
+
+int main()
+{
+ test01();
+ 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
new file mode 100644
index 00000000000..82fff3e20c8
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/move_backward/deque_iterators/2.cc
@@ -0,0 +1,101 @@
+// { dg-do run { target c++11 } }
+// 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 <list>
+#include <deque>
+
+#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);
+
+ deque<int> dest(d.size(), 0);
+
+ move_backward(d.begin(), d.end(), dest.end());
+
+ VERIFY( equal(dest.begin(), dest.end(), d.begin()) );
+}
+
+void test02()
+{
+ using namespace std;
+
+ deque<int> d;
+ for (int i = 0; i != 4 * _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i)
+ d.push_back(i);
+
+ deque<int> dest(d.size(), 0);
+
+ const deque<int>& cd = d;
+ move_backward(cd.begin(), cd.end(), dest.end());
+
+ 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;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/move_backward/deque_iterators/21_neg.cc b/libstdc++-v3/testsuite/25_algorithms/move_backward/deque_iterators/21_neg.cc
new file mode 100644
index 00000000000..002d879928e
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/move_backward/deque_iterators/21_neg.cc
@@ -0,0 +1,40 @@
+// 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 { target c++11 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::deque<int> dest(d.size(), 0);
+ move_backward(d.cbegin() + 10, d.cbegin() + 5, dest.end());
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/move_backward/deque_iterators/22_neg.cc b/libstdc++-v3/testsuite/25_algorithms/move_backward/deque_iterators/22_neg.cc
new file mode 100644
index 00000000000..44cdfc84793
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/move_backward/deque_iterators/22_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/>.
+//
+// { dg-do run { target c++11 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<int> d;
+ for (int i = 0; i != 1024; ++i)
+ d.push_back(i);
+
+ std::deque<int> dest(d.size() / 2, 0);
+
+ move_backward(d.cbegin(), d.cend(), dest.end());
+}
+
+int main()
+{
+ test01();
+ return 0;
+}
diff --git a/libstdc++-v3/testsuite/performance/25_algorithms/copy_backward_deque_iterators.cc b/libstdc++-v3/testsuite/performance/25_algorithms/copy_backward_deque_iterators.cc
index 461dfc044ad..716907c1a96 100644
--- a/libstdc++-v3/testsuite/performance/25_algorithms/copy_backward_deque_iterators.cc
+++ b/libstdc++-v3/testsuite/performance/25_algorithms/copy_backward_deque_iterators.cc
@@ -16,6 +16,9 @@
// <http://www.gnu.org/licenses/>.
#include <deque>
+#include <vector>
+#include <list>
+
#include <testsuite_performance.h>
int main()
@@ -34,7 +37,71 @@ int main()
for (int j = 0; j < 3000; ++j)
std::copy_backward(data.begin(), data.begin() + j, d.end());
stop_counters(time, resource);
- report_performance(__FILE__, "", time, resource);
+ report_performance(__FILE__, "deque 2 deque", time, resource);
+ clear_counters(time, resource);
+
+ std::vector<int> v(3000, 1);
+
+ start_counters(time, resource);
+ for (int i = 0; i < 1000; ++i)
+ for (int j = 0; j < 3000; ++j)
+ std::copy_backward(data.begin(), data.begin() + j, v.end());
+ stop_counters(time, resource);
+ report_performance(__FILE__, "deque 2 vector", time, resource);
+ clear_counters(time, resource);
+
+ d.assign(3000, 1);
+
+ start_counters(time, resource);
+ for (int i = 0; i < 1000; ++i)
+ for (int j = 0; j < 3000; ++j)
+ std::copy_backward(v.begin(), v.begin() + j, d.end());
+ stop_counters(time, resource);
+ report_performance(__FILE__, "vector 2 deque", time, resource);
+ clear_counters(time, resource);
+
+ std::vector<char> cv(3000, 1);
+
+ start_counters(time, resource);
+ for (int i = 0; i < 1000; ++i)
+ for (int j = 0; j < 3000; ++j)
+ std::copy_backward(data.begin(), data.begin() + j, cv.end());
+ stop_counters(time, resource);
+ report_performance(__FILE__, "int deque 2 char vector", time, resource);
+ clear_counters(time, resource);
+
+ d.assign(3000, 1);
+
+ start_counters(time, resource);
+ for (int i = 0; i < 1000; ++i)
+ for (int j = 0; j < 3000; ++j)
+ std::copy_backward(cv.begin(), cv.begin() + j, d.end());
+ stop_counters(time, resource);
+ report_performance(__FILE__, "char vector 2 int deque", time, resource);
+ clear_counters(time, resource);
+
+ std::list<int> l(3000, 1);
+
+ start_counters(time, resource);
+ for (int i = 0; i < 1000; ++i)
+ for (int j = 0; j < 3000; ++j)
+ std::copy_backward(data.begin(), data.begin() + j, l.end());
+ stop_counters(time, resource);
+ report_performance(__FILE__, "deque 2 list", time, resource);
+ clear_counters(time, resource);
+
+ d.assign(3000, 1);
+
+ std::list<int>::iterator lit;
+ start_counters(time, resource);
+ for (int i = 0; i < 200; ++i)
+ {
+ lit = l.begin();
+ for (int j = 0; j < 3000; ++j, ++lit)
+ std::copy_backward(l.begin(), lit, d.end());
+ }
+ stop_counters(time, resource);
+ report_performance(__FILE__, "list 2 deque", time, resource);
return 0;
}
diff --git a/libstdc++-v3/testsuite/performance/25_algorithms/copy_deque_iterators.cc b/libstdc++-v3/testsuite/performance/25_algorithms/copy_deque_iterators.cc
index 35d5d79dec9..0bb2c55a950 100644
--- a/libstdc++-v3/testsuite/performance/25_algorithms/copy_deque_iterators.cc
+++ b/libstdc++-v3/testsuite/performance/25_algorithms/copy_deque_iterators.cc
@@ -16,6 +16,9 @@
// <http://www.gnu.org/licenses/>.
#include <deque>
+#include <vector>
+#include <list>
+
#include <testsuite_performance.h>
int main()
@@ -34,7 +37,71 @@ int main()
for (int j = 0; j < 3000; ++j)
std::copy(data.begin(), data.begin() + j, d.begin());
stop_counters(time, resource);
- report_performance(__FILE__, "", time, resource);
+ report_performance(__FILE__, "deque 2 deque", time, resource);
+ clear_counters(time, resource);
+
+ std::vector<int> v(3000, 1);
+
+ start_counters(time, resource);
+ for (int i = 0; i < 1000; ++i)
+ for (int j = 0; j < 3000; ++j)
+ std::copy(data.begin(), data.begin() + j, v.begin());
+ stop_counters(time, resource);
+ report_performance(__FILE__, "deque 2 vector", time, resource);
+ clear_counters(time, resource);
+
+ d.assign(3000, 1);
+
+ start_counters(time, resource);
+ for (int i = 0; i < 1000; ++i)
+ for (int j = 0; j < 3000; ++j)
+ std::copy(v.begin(), v.begin() + j, d.begin());
+ stop_counters(time, resource);
+ report_performance(__FILE__, "vector 2 deque", time, resource);
+ clear_counters(time, resource);
+
+ std::vector<char> cv(3000, 1);
+
+ start_counters(time, resource);
+ for (int i = 0; i < 1000; ++i)
+ for (int j = 0; j < 3000; ++j)
+ std::copy(data.begin(), data.begin() + j, cv.begin());
+ stop_counters(time, resource);
+ report_performance(__FILE__, "int deque 2 char vector", time, resource);
+ clear_counters(time, resource);
+
+ d.assign(3000, 1);
+
+ start_counters(time, resource);
+ for (int i = 0; i < 1000; ++i)
+ for (int j = 0; j < 3000; ++j)
+ std::copy(cv.begin(), cv.begin() + j, d.begin());
+ stop_counters(time, resource);
+ report_performance(__FILE__, "char vector 2 int deque", time, resource);
+ clear_counters(time, resource);
+
+ std::list<int> l(3000, 1);
+
+ start_counters(time, resource);
+ for (int i = 0; i < 1000; ++i)
+ for (int j = 0; j < 3000; ++j)
+ std::copy(data.begin(), data.begin() + j, l.begin());
+ stop_counters(time, resource);
+ report_performance(__FILE__, "deque 2 list", time, resource);
+ clear_counters(time, resource);
+
+ d.assign(3000, 1);
+
+ std::list<int>::iterator lit;
+ start_counters(time, resource);
+ for (int i = 0; i < 200; ++i)
+ {
+ lit = l.begin();
+ for (int j = 0; j < 3000; ++j, ++lit)
+ std::copy(l.begin(), lit, d.begin());
+ }
+ stop_counters(time, resource);
+ report_performance(__FILE__, "list 2 deque", time, resource);
return 0;
}
diff --git a/libstdc++-v3/testsuite/performance/25_algorithms/equal_deque_iterators.cc b/libstdc++-v3/testsuite/performance/25_algorithms/equal_deque_iterators.cc
new file mode 100644
index 00000000000..66c4601c5f6
--- /dev/null
+++ b/libstdc++-v3/testsuite/performance/25_algorithms/equal_deque_iterators.cc
@@ -0,0 +1,82 @@
+// 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 <deque>
+#include <vector>
+
+#include <testsuite_performance.h>
+
+int main()
+{
+ using namespace __gnu_test;
+
+ time_counter time;
+ resource_counter resource;
+
+ const std::deque<int> data(3000, 1);
+
+ std::deque<int> d(3000, 1);
+
+ start_counters(time, resource);
+ for (int i = 0; i < 1000; ++i)
+ for (int j = 0; j < 3000; ++j)
+ std::equal(data.begin(), data.begin() + j, d.begin());
+ stop_counters(time, resource);
+ report_performance(__FILE__, "deque vs deque", time, resource);
+ clear_counters(time, resource);
+
+ std::vector<int> v(3000, 1);
+
+ start_counters(time, resource);
+ for (int i = 0; i < 1000; ++i)
+ for (int j = 0; j < 3000; ++j)
+ std::equal(data.begin(), data.begin() + j, v.begin());
+ stop_counters(time, resource);
+ report_performance(__FILE__, "deque vs vector", time, resource);
+ clear_counters(time, resource);
+
+ d.assign(3000, 1);
+
+ start_counters(time, resource);
+ for (int i = 0; i < 1000; ++i)
+ for (int j = 0; j < 3000; ++j)
+ std::equal(v.begin(), v.begin() + j, d.begin());
+ stop_counters(time, resource);
+ report_performance(__FILE__, "vector vs deque", time, resource);
+ clear_counters(time, resource);
+
+ std::vector<char> cv(3000, 1);
+
+ start_counters(time, resource);
+ for (int i = 0; i < 1000; ++i)
+ for (int j = 0; j < 3000; ++j)
+ std::equal(data.begin(), data.begin() + j, cv.begin());
+ stop_counters(time, resource);
+ report_performance(__FILE__, "int deque vs char vector", time, resource);
+ clear_counters(time, resource);
+
+ d.assign(3000, 1);
+
+ start_counters(time, resource);
+ for (int i = 0; i < 1000; ++i)
+ for (int j = 0; j < 3000; ++j)
+ std::equal(cv.begin(), cv.begin() + j, d.begin());
+ stop_counters(time, resource);
+ report_performance(__FILE__, "char vector vs int deque", time, resource);
+
+ return 0;
+}