This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


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

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;
+}

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