This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Keep std::deque algos specializations in Debug mode
- From: François Dumont <frs dot dumont at gmail dot com>
- To: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Sat, 25 Aug 2018 22:44:22 +0200
- Subject: Keep std::deque algos specializations in Debug mode
The last optimizations that get disabled when Debug mode is enable are
the algo specializations for std::deque iterators.
This patch move those algos in std namespace as they should even when
Debug mode is enable so that they get considered even when calls are
made with the namespace qualification. And it adds all the algos Debug
implementations which forward to normal implementations to benefit from
optimizations.
Note that I try to use typename deque<>::iterator or typename
deque<>::const_iterator to define Debug algos but it didn't work, gcc
was just not considering those overloads. I wonder why ?
I added test and manually checked that behavior was correct. Do you see
a way to automate this validation ?
François
diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
index 125bcffb0c3..2a3f23a8588 100644
--- a/libstdc++-v3/include/bits/deque.tcc
+++ b/libstdc++-v3/include/bits/deque.tcc
@@ -980,22 +980,27 @@ _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
@@ -1003,12 +1008,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
}
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 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>::_Self
+ _Self;
typedef typename _Self::difference_type difference_type;
difference_type __len = __last - __first;
@@ -1026,12 +1032,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
}
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 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>::_Self
+ _Self;
typedef typename _Self::difference_type difference_type;
difference_type __len = __last - __first;
@@ -1066,12 +1074,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
#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)
+ _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 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>::_Self
+ _Self;
typedef typename _Self::difference_type difference_type;
difference_type __len = __last - __first;
@@ -1089,12 +1098,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
}
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_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 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>::_Self
+ _Self;
typedef typename _Self::difference_type difference_type;
difference_type __len = __last - __first;
@@ -1128,7 +1139,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
}
#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 49ee31e1255..f658d99dbbc 100644
--- a/libstdc++-v3/include/bits/stl_deque.h
+++ b/libstdc++-v3/include/bits/stl_deque.h
@@ -396,77 +396,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
_GLIBCXX_NOEXCEPT
{ 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
@@ -2482,6 +2411,84 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
#undef _GLIBCXX_DEQUE_BUF_SIZE
_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>
+ _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 _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); }
+
+#if __cplusplus >= 201103L
+ 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 _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); }
+#endif
+
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
diff --git a/libstdc++-v3/include/debug/deque b/libstdc++-v3/include/debug/deque
index ad86b5c8f38..61908029eac 100644
--- a/libstdc++-v3/include/debug/deque
+++ b/libstdc++-v3/include/debug/deque
@@ -683,8 +683,243 @@ namespace __debug
swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs)
_GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
{ __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 _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 _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());
+ }
+
+#if __cplusplus >= 201103L
+ template<typename _Tp, typename _Alloc1, typename _Alloc2>
+ ::__gnu_debug::_Safe_iterator<
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ __debug::deque<_Tp, _Alloc2> >
+ move(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
+ {
+ std::move(__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> >
+ move(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
+ {
+ std::move(__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> >
+ move_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
+ {
+ std::move_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> >
+ move_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
+ {
+ std::move_backward(__first.base(), __last.base(), __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..9171200bc20
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/copy.cc
@@ -0,0 +1,56 @@
+// Copyright (C) 2018 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 <limits>
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<char> d;
+ for (char c = 0; c != std::numeric_limits<char>::max(); ++c)
+ d.push_back(c);
+
+ std::deque<char> dest(std::numeric_limits<char>::max(), '\0');
+
+ std::copy(d.begin(), d.end(), dest.begin());
+
+ VERIFY( std::equal(dest.begin(), dest.end(), d.begin()) );
+}
+
+void test02()
+{
+ std::deque<char> d;
+ for (char c = 0; c != std::numeric_limits<char>::max(); ++c)
+ d.push_back(c);
+
+ std::deque<char> dest(std::numeric_limits<char>::max(), '\0');
+
+ const std::deque<char>& cd = d;
+ std::copy(cd.begin(), cd.end(), dest.begin());
+
+ VERIFY( std::equal(dest.begin(), dest.end(), cd.begin()) );
+}
+
+int main()
+{
+ test01();
+ test02();
+ 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..0156eee4328
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/copy_backward.cc
@@ -0,0 +1,56 @@
+// Copyright (C) 2018 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 <limits>
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<char> d;
+ for (char c = 0; c != std::numeric_limits<char>::max(); ++c)
+ d.push_back(c);
+
+ std::deque<char> dest(std::numeric_limits<char>::max(), '\0');
+
+ std::copy_backward(d.begin(), d.end(), dest.end());
+
+ VERIFY( std::equal(dest.begin(), dest.end(), d.begin()) );
+}
+
+void test02()
+{
+ std::deque<char> d;
+ for (char c = 0; c != std::numeric_limits<char>::max(); ++c)
+ d.push_back(c);
+
+ std::deque<char> dest(std::numeric_limits<char>::max(), '\0');
+
+ const std::deque<char>& cd = d;
+ std::copy_backward(cd.begin(), cd.end(), dest.end());
+
+ VERIFY( std::equal(dest.begin(), dest.end(), cd.begin()) );
+}
+
+int main()
+{
+ test01();
+ test02();
+ 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..03eb1cd568c
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/fill.cc
@@ -0,0 +1,35 @@
+// Copyright (C) 2018 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 <limits>
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+int main()
+{
+ std::deque<char> d;
+ for (char c = 1; c != std::numeric_limits<char>::max(); ++c)
+ d.push_back(c);
+
+ std::fill(d.begin(), d.end(), '\0');
+
+ VERIFY( d.front() == '\0' );
+ VERIFY( d.back() == '\0' );
+ 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..22b7df76276
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/move.cc
@@ -0,0 +1,56 @@
+// { dg-do run { target c++11 } }
+// Copyright (C) 2018 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 <limits>
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<char> d;
+ for (char c = 0; c != std::numeric_limits<char>::max(); ++c)
+ d.push_back(c);
+
+ std::deque<char> dest(std::numeric_limits<char>::max(), '\0');
+
+ std::move(d.begin(), d.end(), dest.begin());
+
+ VERIFY( std::equal(dest.begin(), dest.end(), d.begin()) );
+}
+
+void test02()
+{
+ std::deque<char> d;
+ for (char c = 0; c != std::numeric_limits<char>::max(); ++c)
+ d.push_back(c);
+
+ std::deque<char> dest(std::numeric_limits<char>::max(), '\0');
+
+ std::move(d.cbegin(), d.cend(), dest.begin());
+
+ VERIFY( std::equal(dest.begin(), dest.end(), d.cbegin()) );
+}
+
+int main()
+{
+ test01();
+ test02();
+ 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..d27c379cbcd
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/move_backward.cc
@@ -0,0 +1,56 @@
+// { dg-do run { target c++11 } }
+// Copyright (C) 2018 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 <limits>
+#include <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ std::deque<char> d;
+ for (char c = 0; c != std::numeric_limits<char>::max(); ++c)
+ d.push_back(c);
+
+ std::deque<char> dest(std::numeric_limits<char>::max(), '\0');
+
+ std::move_backward(d.begin(), d.end(), dest.end());
+
+ VERIFY( std::equal(dest.begin(), dest.end(), d.begin()) );
+}
+
+void test02()
+{
+ std::deque<char> d;
+ for (char c = 0; c != std::numeric_limits<char>::max(); ++c)
+ d.push_back(c);
+
+ std::deque<char> dest(std::numeric_limits<char>::max(), '\0');
+
+ std::move_backward(d.cbegin(), d.cend(), dest.end());
+
+ VERIFY( std::equal(dest.begin(), dest.end(), d.cbegin()) );
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 0;
+}