public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* Deque fiil/copy/move/copy_backward/move_backward/equal overloads
@ 2019-06-19 17:32 François Dumont
  2019-06-20  8:38 ` Morwenn Ed
                   ` (2 more replies)
  0 siblings, 3 replies; 13+ messages in thread
From: François Dumont @ 2019-06-19 17:32 UTC (permalink / raw)
  To: libstdc++, gcc-patches

[-- Attachment #1: Type: text/plain, Size: 565 bytes --]

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


[-- Attachment #2: ChangeLog.entry --]
[-- Type: text/plain, Size: 14921 bytes --]

	* include/bits/stl_deque.h
	(fill, copy, copy_backward, move, move_backward): Move overloads for
	std::deque iterators in std namespace.
	(copy<_Tp, _OI>(
	_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_Deque_iterator<_Tp, const _Tp&, const _Tp*>, _OI)): New.
	(copy<_Tp, _OI>(_Deque_iterator<_Tp, _Tp&, _Tp*>,
	_Deque_iterator<_Tp, _Tp&, _Tp*>, _OI)): New, use latter.
	(copy<_II, _Tp>(_II, _II, _Deque_iterator<_Tp, _Tp&, _Tp*>)): New.
	(copy_backward<_Tp, _OI>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_Deque_iterator<_Tp, const _Tp&, const _Tp*>, _OI)): New.
	(copy_backward<_Tp, _OI>(_Deque_iterator<_Tp, _Tp&, _Tp*>,
	_Deque_iterator<_Tp, _Tp&, _Tp*>, _OI)): New, use latter.
	(copy_backward<_II, _Tp>(_II, _II, _Deque_iterator<_Tp, _Tp&, _Tp*>)):
	New.
	(equal<_Tp, _II>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_Deque_iterator<_Tp, const _Tp&, const _Tp*>, _II)): New.
	(equal<_Tp, _II>(_Deque_iterator<_Tp, _Tp&, _Tp*>,
	_Deque_iterator<_Tp, _Tp&, _Tp*>, _II)): New, use latter.
	(equal<_Tp>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_Deque_iterator<_Tp, const _Tp&, const _Tp*>)): New.
	(equal<_Tp>(_Deque_iterator<_Tp, _Tp&, _Tp*>,
	_Deque_iterator<_Tp, _Tp&, _Tp*>,
	_Deque_iterator<_Tp, const _Tp&, const _Tp*>)): New, use latter.
	(equal<_Tp>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_Deque_iterator<_Tp, _Tp&, _Tp*>)): Likewise.
	(equal<_Tp>(_Deque_iterator<_Tp, _Tp&, _Tp*>,
	_Deque_iterator<_Tp, _Tp&, _Tp*>, _Deque_iterator<_Tp, _Tp&, _Tp*>)):
	Likewise.
	(equal<_II, _Tp>(_II, _II,
	_Deque_iterator<_Tp, const _Tp&, const _Tp*>): New.
	(equal<_II, _Tp>(_II, _II, _Deque_iterator<_Tp, _Tp&, _Tp*>): New, use
	latter.
	(move<_Tp, _OI>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>, _OI)):
	New.
	(move<_Tp, _OI>(_Deque_iterator<_Tp, _Tp&, _Tp*>, _OI)): New, use
	latter.
	(move<_II, _Tp>(_II, _II, _Deque_iterator<_Tp, _Tp&, _Tp*>)): New.
	(move_backward<_Tp, _OI>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_OI)): New.
	(move_backward<_Tp, _OI>(_Deque_iterator<_Tp, _Tp&, _Tp*>, _OI)): New,
	use latter.
	(move_backward<_II, _Tp>(_II, _II, _Deque_iterator<_Tp, _Tp&, _Tp*>)):
	New.
	* include/bits/deque.tcc
	(fill, copy, copy_backward, move, move_backward): Move overloads for
	std::deque iterators in std namespace.
	(fill): Move loop on nodes inside branch when first and last nodes are
	different.
	(std::__detail::__copy_from_dit): New.
	(copy<_Tp>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_Deque_iterator<_Tp, _Tp&, _Tp*>)): Adapt to use latter.
	(copy<_Tp, _OI>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_Deque_iterator<_Tp, const _Tp&, const _Tp*>, _OI)): New, likewise.
	(std::__detail::__copy_to_dit): New.
	(copy<_II, _Tp>(_II, _II, _Deque_iterator<_Tp, _Tp&, _Tp*>)): New, use
	latter.
	(std::__detail::__copy_backward_from_dit): New.
	(copy_backward<_Tp>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_Deque_iterator<_Tp, _Tp&, _Tp*>)): Adapt to use latter.
	(copy_backward<_Tp, _OI>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_Deque_iterator<_Tp, const _Tp&, const _Tp*>, _OI)): New, likewise.
	(std::__detail::__copy_backward_to_dit): New.
	(copy_backward<_II, _Tp>(_II, _II, _Deque_iterator<_Tp, _Tp&, _Tp*>)):
	New, use latter.
	(std::__detail::__equal_from_dit): New.
	(equal<_Tp, _II>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_Deque_iterator<_Tp, const _Tp&, const _Tp*>)): Use latter.
	(equal<_Tp, _II>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_Deque_iterator<_Tp, const _Tp&, const _Tp*>, _II)): New, likewise.
	(std::__detail::__equal_to_dit): New.
	(equal<_II, _Tp>(_II, _II,
	_Deque_iterator<_Tp, const _Tp&, const _Tp*>): New, use latter.
	(std::__detail::__move_from_dit): New.
	(move<_Tp>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_Deque_iterator<_Tp, _Tp&, _Tp*>)): Adapt to use latter.
	(move<_Tp, _OI>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_Deque_iterator<_Tp, const _Tp&, const _Tp*>, _OI)): New, likewise.
	(std::__detail::__move_to_dit): New.
	(move<_II, _Tp>(_II, _II, _Deque_iterator<_Tp, _Tp&, _Tp*>)): New, use
	latter.
	(std::__detail::__move_backward_from_dit): New.
	(move_backward<_Tp>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_Deque_iterator<_Tp, _Tp&, _Tp*>)): Adapt to use latter.
	(move_backward<_Tp, _OI>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	_Deque_iterator<_Tp, const _Tp&, const _Tp*>, _OI)): New, likewise.
	(std::__detail::__move_backward_to_dit): New.
	(move_backward<_II, _Tp>(_II, _II, _Deque_iterator<_Tp, _Tp&, _Tp*>)):
	New, use latter.
	* include/debug/deque
	(fill<_Tp, _Alloc>(const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>
	, __debug::deque<_Tp, _Alloc>>&,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc>>&, const _Tp&)): New.
	(copy<_Tp, _Alloc, _OI>(
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc> >&, _OI)): New.
	(copy<_Tp, _Alloc, _OI>(
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&, _OI)): New.
	(copy<_Tp, _Alloc>(
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&)): New.
	(copy<_Tp, _Alloc>(
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&)): New.
	(copy<_II, _Tp, _Alloc>(_II, _II,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&)): New.
	(copy_backward<_Tp, _Alloc, _OI>(
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc> >&, _OI)): New.
	(copy_backward<_Tp, _Alloc, _OI>(
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&, _OI)): New.
	(copy_backward<_Tp, _Alloc>(
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&)): New.
	(copy_backward<_Tp, _Alloc>(
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&)): New.
	(copy_backward<_II, _Tp, _Alloc>(_II, _II,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&)): New.
	(equal<_Tp, _Alloc, _II>(
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc> >&, _II)): New.
	(equal<_Tp, _Alloc, _II>(
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&, _II)): New.
	(equal<_Tp, _Alloc1, _Alloc2>(
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc1> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc1> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc2> >&)): New.
	(equal<_Tp, _Alloc1, _Alloc2>(
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc1> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc1> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc2> >&)): New.
	(equal<_Tp, _Alloc1, _Alloc2>(
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc1> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc1> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc2> >&)): New.
	(equal<_Tp, _Alloc1, _Alloc2>(
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc1> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc1> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc2> >&)): New.
	(equal<_II, _Tp, _Alloc>(_II, _II,
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc> >&)): New.
	(equal<_II, _Tp, _Alloc>(_II, _II,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&)): New.
	(move<_Tp, _Alloc, _OI>(
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc> >&, _OI)): New.
	(move<_Tp, _Alloc, _OI>(
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&, _OI)): New.
	(move<_Tp, _Alloc>(
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&)): New.
	(move<_Tp, _Alloc>(
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&)): New.
	(move<_II, _Tp, _Alloc>(_II, _II,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&)): New.
	(move_backward<_Tp, _Alloc, _OI>(
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc> >&, _OI)): New.
	(move_backward<_Tp, _Alloc, _OI>(
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&, _OI)): New.
	(move_backward<_Tp, _Alloc>(
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&)): New.
	(move_backward<_Tp, _Alloc>(
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&)): New.
	(move_backward<_II, _Tp, _Alloc>(_II, _II,
	const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
	__debug::deque<_Tp, _Alloc> >&)): New.
	* testsuite/23_containers/deque/copy.cc: New.
	* testsuite/23_containers/deque/copy_backward.cc: New.
	* testsuite/23_containers/deque/debug/copy11_neg.cc: New.
	* testsuite/23_containers/deque/debug/copy12_neg.cc: New.
	* testsuite/23_containers/deque/debug/copy21_neg.cc: New.
	* testsuite/23_containers/deque/debug/copy22_neg.cc: New.
	* testsuite/23_containers/deque/debug/copy31_neg.cc: New.
	* testsuite/23_containers/deque/debug/copy32_neg.cc: New.
	* testsuite/23_containers/deque/debug/copy33_neg.cc: New.
	* testsuite/23_containers/deque/debug/copy41_neg.cc: New.
	* testsuite/23_containers/deque/debug/copy42_neg.cc: New.
	* testsuite/23_containers/deque/debug/copy43_neg.cc: New.
	* testsuite/23_containers/deque/debug/copy51_neg.cc: New.
	* testsuite/23_containers/deque/debug/copy61_neg.cc: New.
	* testsuite/23_containers/deque/debug/copy71_neg.cc: New.
	* testsuite/23_containers/deque/debug/copy72_neg.cc: New.
	* testsuite/23_containers/deque/debug/copy_backward11_neg.cc: New.
	* testsuite/23_containers/deque/debug/copy_backward12_neg.cc: New.
	* testsuite/23_containers/deque/debug/copy_backward21_neg.cc: New.
	* testsuite/23_containers/deque/debug/copy_backward22_neg.cc: New.
	* testsuite/23_containers/deque/debug/fill_neg.cc: New.
	* testsuite/23_containers/deque/debug/move11_neg.cc: New.
	* testsuite/23_containers/deque/debug/move12_neg.cc: New.
	* testsuite/23_containers/deque/debug/move21_neg.cc: New.
	* testsuite/23_containers/deque/debug/move22_neg.cc: New.
	* testsuite/23_containers/deque/debug/move_backward11_neg.cc: New.
	* testsuite/23_containers/deque/debug/move_backward12_neg.cc: New.
	* testsuite/23_containers/deque/debug/move_backward21_neg.cc: New.
	* testsuite/23_containers/deque/debug/move_backward22_neg.cc: New.
	* testsuite/23_containers/deque/fill.cc: New.
	* testsuite/23_containers/deque/move.cc: New.
	* testsuite/23_containers/deque/move_backward.cc: New.
	* testsuite/25_algorithms/equal/debug/deque10_neg.cc: New.
	* testsuite/25_algorithms/equal/debug/deque11_neg.cc: New.
	* testsuite/25_algorithms/equal/debug/deque12_neg.cc: New.
	* testsuite/25_algorithms/equal/debug/deque13_neg.cc: New.
	* testsuite/25_algorithms/equal/debug/deque14_neg.cc: New.
	* testsuite/25_algorithms/equal/debug/deque15_neg.cc: New.
	* testsuite/25_algorithms/equal/debug/deque16_neg.cc: New.
	* testsuite/25_algorithms/equal/debug/deque1_neg.cc: New.
	* testsuite/25_algorithms/equal/debug/deque2_neg.cc: New.
	* testsuite/25_algorithms/equal/debug/deque3_neg.cc: New.
	* testsuite/25_algorithms/equal/debug/deque4_neg.cc: New.
	* testsuite/25_algorithms/equal/debug/deque5_neg.cc: New.
	* testsuite/25_algorithms/equal/debug/deque6_neg.cc: New.
	* testsuite/25_algorithms/equal/debug/deque7_neg.cc: New.
	* testsuite/25_algorithms/equal/debug/deque8_neg.cc: New.
	* testsuite/25_algorithms/equal/debug/deque9_neg.cc: New.
	* testsuite/25_algorithms/equal/deque/equal.cc: New.

[-- Attachment #3: deque_algos.patch --]
[-- Type: text/x-patch, Size: 138987 bytes --]

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);
     }
 
+_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 typename _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>::_Self
+	_Self;
 
       if (__first._M_node != __last._M_node)
 	{
 	  std::fill(__first._M_cur, __first._M_last, __value);
+
+	  for (typename _Self::_Map_pointer __node = __first._M_node + 1;
+	       __node < __last._M_node; ++__node)
+	    std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
+
 	  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 typename _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+							 const _Tp*>::_Self
+	  _Self;
+
+	if (__first._M_node != __last._M_node)
+	  {
+	    __result = std::copy(__first._M_cur, __first._M_last, __result);
+
+	    for (typename _Self::_Map_pointer __node = __first._M_node + 1;
+		 __node != __last._M_node; ++__node)
+	      __result = std::copy(*__node, *__node + _Self::_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 typename _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>::_Self
+	  _Self;
+	typedef typename _Self::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 typename _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+							 const _Tp*>::_Self
+	  _Self;
+
+	if (__first._M_node != __last._M_node)
+	  {
+	    __result = std::copy_backward(__last._M_first, __last._M_cur,
+					  __result);
+
+	    for (typename _Self::_Map_pointer __node = __last._M_node - 1;
+		 __node != __first._M_node; --__node)
+	      __result
+		= std::copy_backward(*__node, *__node + _Self::_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 typename _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>::_Self
+	  _Self;
+	typedef typename _Self::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 = _Self::_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 typename _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+							 const _Tp*>::_Self
+	  _Self;
+
+	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 _Self::_Map_pointer __node = __first1._M_node + 1;
+		 __node != __last1._M_node;
+		 __first2 += _Self::_S_buffer_size(), ++__node)
+	      if (!std::equal(*__node, *__node + _Self::_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 typename _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+							 const _Tp*>::_Self
+	  _Self;
+	typedef typename _Self::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 typename _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+							 const _Tp*>::_Self
+	  _Self;
+
+	if (__first._M_node != __last._M_node)
+	  {
+	    __result = std::move(__first._M_cur, __first._M_last, __result);
+
+	    for (typename _Self::_Map_pointer __node = __first._M_node + 1;
+		 __node != __last._M_node; ++__node)
+	      __result = std::move(*__node, *__node + _Self::_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 typename _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>::_Self
+	  _Self;
+	typedef typename _Self::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 typename _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&,
+							 const _Tp*>::_Self
+	  _Self;
+
+	if (__first._M_node != __last._M_node)
+	  {
+	    __result = std::move_backward(__last._M_first, __last._M_cur,
+					  __result);
+
+	    for (typename _Self::_Map_pointer __node = __last._M_node - 1;
+		 __node != __first._M_node; --__node)
+	      __result
+		= std::move_backward(*__node, *__node + _Self::_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 typename _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>::_Self
+	  _Self;
+	typedef typename _Self::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 = _Self::_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
+  }
+
+  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<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__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<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__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<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__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<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__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);
+    }
 
-	  difference_type __rlen = __result._M_cur - __result._M_first;
-	  _Tp* __rend = __result._M_cur;
+  template<typename _II, typename _Tp>
+    typename enable_if<
+      is_same<typename std::iterator_traits<_II>::iterator_category,
+	      std::random_access_iterator_tag>::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);
 
-	  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::__move_to_dit(__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;
+  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);
+
+      return __detail::__move_backward_from_dit(__first, __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*> __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_same<typename std::iterator_traits<_II>::iterator_category,
+	      std::random_access_iterator_tag>::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
 
-_GLIBCXX_END_NAMESPACE_CONTAINER
 _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..23aea66c42c 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,12 +2272,279 @@ _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)
+    {
+      return std::copy(
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__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)
+    {
+      return std::copy(
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
+	__result);
+    }
+
+  template<typename _II, typename _Tp>
+    typename __gnu_cxx::__enable_if<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__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)
+    {
+      return std::copy_backward(
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__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)
+    {
+      return std::copy_backward(
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
+	__result);
+    }
+
+  template<typename _II, typename _Tp>
+    typename __gnu_cxx::__enable_if<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__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<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__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<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__value,
+      bool>::__type
+    equal(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first1,
+	  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __last1,
+	  _II __first2)
+    {
+      return std::equal(
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first1),
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__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)
+    {
+      return std::equal(
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first1),
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__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)
+    {
+      return std::equal(
+	__first1, __last1,
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__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)
+    {
+      return std::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));
+    }
+
+  template<typename _II, typename _Tp>
+    typename __gnu_cxx::__enable_if<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__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<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__value,
+      bool>::__type
+    equal(_II __first1, _II __last1,
+	  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first2)
+    {
+      return std::equal(__first1, __last1,
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__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 { };
+
+  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)
+    {
+      return std::move(
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__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)
+    {
+      return std::move(
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
+	__result);
+    }
+
+  template<typename _II, typename _Tp>
+    typename enable_if<
+      is_same<typename std::iterator_traits<_II>::iterator_category,
+	      std::random_access_iterator_tag>::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)
+    {
+      return std::move_backward(
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__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)
+    {
+      return std::move_backward(
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
+	__result);
+    }
+
+  template<typename _II, typename _Tp>
+    typename enable_if<
+      is_same<typename std::iterator_traits<_II>::iterator_category,
+	      std::random_access_iterator_tag>::value,
+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::type
+    move_backward(_II, _II,
+		  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
 #endif
 
 _GLIBCXX_END_NAMESPACE_VERSION
diff --git a/libstdc++-v3/include/debug/deque b/libstdc++-v3/include/debug/deque
index 973f39fced6..64a29fbe1bc 100644
--- a/libstdc++-v3/include/debug/deque
+++ b/libstdc++-v3/include/debug/deque
@@ -685,6 +685,612 @@ 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<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__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<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__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<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__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<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__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<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__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<
+      __are_same<typename std::iterator_traits<_II>::iterator_category,
+		 std::random_access_iterator_tag>::__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<
+      is_same<typename std::iterator_traits<_II>::iterator_category,
+	      std::random_access_iterator_tag>::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<
+      is_same<typename std::iterator_traits<_II>::iterator_category,
+	      std::random_access_iterator_tag>::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/testsuite/23_containers/deque/copy.cc b/libstdc++-v3/testsuite/23_containers/deque/copy.cc
new file mode 100644
index 00000000000..7b0dc3d2126
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/copy.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/23_containers/deque/copy_backward.cc b/libstdc++-v3/testsuite/23_containers/deque/copy_backward.cc
new file mode 100644
index 00000000000..ccde5279859
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/copy_backward.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/23_containers/deque/debug/copy11_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/copy11_neg.cc
new file mode 100644
index 00000000000..86594da0102
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/copy11_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/23_containers/deque/debug/copy12_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/copy12_neg.cc
new file mode 100644
index 00000000000..1507e8903a1
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/copy12_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/23_containers/deque/debug/copy21_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/copy21_neg.cc
new file mode 100644
index 00000000000..fc09f661b25
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/copy21_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/23_containers/deque/debug/copy22_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/copy22_neg.cc
new file mode 100644
index 00000000000..64ff6c487e3
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/copy22_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/23_containers/deque/debug/copy31_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/copy31_neg.cc
new file mode 100644
index 00000000000..ae2c33b1d10
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/copy31_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 <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/23_containers/deque/debug/copy32_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/copy32_neg.cc
new file mode 100644
index 00000000000..8028bd6b542
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/copy32_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 <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/23_containers/deque/debug/copy33_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/copy33_neg.cc
new file mode 100644
index 00000000000..1633fafd20c
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/copy33_neg.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/23_containers/deque/debug/copy41_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/copy41_neg.cc
new file mode 100644
index 00000000000..0c9d949807a
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/copy41_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::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/23_containers/deque/debug/copy42_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/copy42_neg.cc
new file mode 100644
index 00000000000..c7e0c1f49fd
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/copy42_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::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/23_containers/deque/debug/copy43_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/copy43_neg.cc
new file mode 100644
index 00000000000..2f29afae09f
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/copy43_neg.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/23_containers/deque/debug/copy51_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/copy51_neg.cc
new file mode 100644
index 00000000000..eaaa8b3d2d6
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/copy51_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/23_containers/deque/debug/copy61_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/copy61_neg.cc
new file mode 100644
index 00000000000..f6b20f6ee0e
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/copy61_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/23_containers/deque/debug/copy71_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/copy71_neg.cc
new file mode 100644
index 00000000000..063acf096f6
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/copy71_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/23_containers/deque/debug/copy72_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/copy72_neg.cc
new file mode 100644
index 00000000000..855957ae1b6
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/copy72_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/23_containers/deque/debug/copy_backward11_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/copy_backward11_neg.cc
new file mode 100644
index 00000000000..a497267f04f
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/copy_backward11_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/23_containers/deque/debug/copy_backward12_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/copy_backward12_neg.cc
new file mode 100644
index 00000000000..f30d9f3c3b7
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/copy_backward12_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/23_containers/deque/debug/copy_backward21_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/copy_backward21_neg.cc
new file mode 100644
index 00000000000..aec11a81172
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/copy_backward21_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/23_containers/deque/debug/copy_backward22_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/copy_backward22_neg.cc
new file mode 100644
index 00000000000..89db2024ac9
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/copy_backward22_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/23_containers/deque/debug/fill_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/fill_neg.cc
new file mode 100644
index 00000000000..af25b2ef08a
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/fill_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/23_containers/deque/debug/move11_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/move11_neg.cc
new file mode 100644
index 00000000000..d3dc432ff7b
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/move11_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/23_containers/deque/debug/move12_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/move12_neg.cc
new file mode 100644
index 00000000000..b4079691b7c
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/move12_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/23_containers/deque/debug/move21_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/move21_neg.cc
new file mode 100644
index 00000000000..66245fb677b
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/move21_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/23_containers/deque/debug/move22_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/move22_neg.cc
new file mode 100644
index 00000000000..ab69e9bab77
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/move22_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/23_containers/deque/debug/move_backward11_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/move_backward11_neg.cc
new file mode 100644
index 00000000000..c5dbc14f8cc
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/move_backward11_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/23_containers/deque/debug/move_backward12_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/move_backward12_neg.cc
new file mode 100644
index 00000000000..5718b5df141
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/move_backward12_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/23_containers/deque/debug/move_backward21_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/move_backward21_neg.cc
new file mode 100644
index 00000000000..002d879928e
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/move_backward21_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/23_containers/deque/debug/move_backward22_neg.cc b/libstdc++-v3/testsuite/23_containers/deque/debug/move_backward22_neg.cc
new file mode 100644
index 00000000000..44cdfc84793
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/debug/move_backward22_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/23_containers/deque/fill.cc b/libstdc++-v3/testsuite/23_containers/deque/fill.cc
new file mode 100644
index 00000000000..604ccb67fcd
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/fill.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/23_containers/deque/move.cc b/libstdc++-v3/testsuite/23_containers/deque/move.cc
new file mode 100644
index 00000000000..1f7930036d1
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/move.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/23_containers/deque/move_backward.cc b/libstdc++-v3/testsuite/23_containers/deque/move_backward.cc
new file mode 100644
index 00000000000..82fff3e20c8
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/move_backward.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/equal/debug/deque10_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque10_neg.cc
new file mode 100644
index 00000000000..72f070b292d
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque10_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/debug/deque11_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque11_neg.cc
new file mode 100644
index 00000000000..ae11f23d3b0
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque11_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/debug/deque12_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque12_neg.cc
new file mode 100644
index 00000000000..a0c2cece818
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque12_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/debug/deque13_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque13_neg.cc
new file mode 100644
index 00000000000..b6f8519b1b2
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque13_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/debug/deque14_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque14_neg.cc
new file mode 100644
index 00000000000..6dfea283516
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque14_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/debug/deque15_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque15_neg.cc
new file mode 100644
index 00000000000..fe0360a1842
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque15_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/debug/deque16_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque16_neg.cc
new file mode 100644
index 00000000000..8330edc9b2e
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque16_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/debug/deque1_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque1_neg.cc
new file mode 100644
index 00000000000..1f26672b31d
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque1_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/debug/deque2_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque2_neg.cc
new file mode 100644
index 00000000000..caadc2b77d1
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque2_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/debug/deque3_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque3_neg.cc
new file mode 100644
index 00000000000..55ed05c0ae5
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque3_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/debug/deque4_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque4_neg.cc
new file mode 100644
index 00000000000..e67d4b19b42
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque4_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/debug/deque5_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque5_neg.cc
new file mode 100644
index 00000000000..d737aa2edfc
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque5_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/debug/deque6_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque6_neg.cc
new file mode 100644
index 00000000000..d1a74dd068a
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque6_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/debug/deque7_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque7_neg.cc
new file mode 100644
index 00000000000..e3c9cf1325f
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque7_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/debug/deque8_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque8_neg.cc
new file mode 100644
index 00000000000..6078f598447
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque8_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/debug/deque9_neg.cc b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque9_neg.cc
new file mode 100644
index 00000000000..7dd86ce3ec8
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/debug/deque9_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/equal/deque/equal.cc b/libstdc++-v3/testsuite/25_algorithms/equal/deque/equal.cc
new file mode 100644
index 00000000000..b99cf1df538
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/deque/equal.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;
+}

^ permalink raw reply	[flat|nested] 13+ messages in thread

end of thread, other threads:[~2019-08-26 19:49 UTC | newest]

Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-06-19 17:32 Deque fiil/copy/move/copy_backward/move_backward/equal overloads François Dumont
2019-06-20  8:38 ` Morwenn Ed
2019-06-21  4:43   ` François Dumont
2019-07-16 17:20 ` François Dumont
2019-07-26  9:13 ` PR 90409 " François Dumont
2019-08-01  9:57   ` Jonathan Wakely
2019-08-01 10:36     ` Daniel Krügler
2019-08-01 11:01       ` Jonathan Wakely
2019-08-01 11:31         ` Daniel Krügler
2019-08-01 12:52           ` Jonathan Wakely
2019-08-01 12:53             ` Jonathan Wakely
2019-08-21 21:18               ` François Dumont
2019-08-26 20:31                 ` François Dumont

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).