This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Keep std::deque algos specializations in Debug mode
- From: François Dumont <frs dot dumont at gmail dot com>
- To: Jonathan Wakely <jwakely at redhat dot com>
- Cc: "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: Thu, 6 Sep 2018 22:07:47 +0200
- Subject: Re: Keep std::deque algos specializations in Debug mode
- References: <2f4b53ec-bbd3-4196-843a-0ce12e42bc27@gmail.com> <20180904125956.GZ4149@redhat.com>
On 09/04/2018 02:59 PM, Jonathan Wakely wrote:
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)
Is there any particular reason to change this from using < to != for
the comparison?
I consider that the reason for having a < comparison was that this loop
was done before checking __first._M_node != __last._M_node. As I moved
it inside the block I also prefer to use a usual condition when
iterating other iterators/pointers.
Isn't it a simpler operation ? Do you fear a compiler warning about it
like we used to have in vector implementation before introducing the
__builtin_unreachable calls ?
(This change is part of the reason I asked for the ChangeLog, but you
didn't mention it in the ChangeLog).
I had forgotten about it but I can add it in ChangeLog.
Moving it inside the condition makes sense (not only does it avoid a
branch in the single-page case, but means we fill the elements in
order).
Yes, it is the main reason I moved it, I should have signal it when I
submit the patch.
+ std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
+
std::fill(__last._M_first, __last._M_cur, __value);
}
else
The rest of the code changes look fine, I just wondered about that
bit.
I do have some comments on the new tests though ...
+
+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');
These deques only have 127 or 255 elements (depending on
is_signed<char>) which will fit on a single page of a deque (the
default is 512 bytes per page).
That means the tests don't exercise the logic for handling
non-contiguous blocks of memory.
Ideally we'd want to test multiple cases:
- a single page, with/without empty capacity at front/back
- multiple pages, with/without empty capacity at front/back
That would be 8 cases. I think we want to test at least a single
page and multiple pages.
I think I started to create the fill.cc which require usage of char to
make sure it uses __builtin_memset and then extrapolated to other algos.
But I had already reviewed those tests for a patch I'll submit after
this one so here is the revisited tests.
In this new proposal I also introduce a template alias to simplify the
C++11 overloads. I define it in __gnu_debug to avoid polluting std
namespace with a non-Standard thing.
* include/bits/stl_deque.h
(fill, copy, copy_backward, move, move_backward): Move overloads for
std::deque iterators in std namespace.
* include/bits/deque.tcc: Likewise.
(fill): Move loop on nodes inside branch when first and last nodes are
different. Replace for loop < condition on nodes with a !=.
* include/debug/deque
(__gnu_debug::_SDeque_iterator<>, __gnu_debug::_SDeque_const_iterator):
New template aliases.
(fill, copy, copy_backward, move, move_backward):
New overloads for std::__debug::deque iterators. Forward to normal and
optimized implementations after proper debug checks.
* testsuite/23_containers/deque/copy.cc: New.
* testsuite/23_containers/deque/copy_backward.cc: New.
* testsuite/23_containers/deque/fill.cc: New.
* testsuite/23_containers/deque/move.cc: New.
* testsuite/23_containers/deque/move_backward.cc: New.
Tested under Linux x86_64.
Ok to commit ?
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..bc162a35b69 100644
--- a/libstdc++-v3/include/debug/deque
+++ b/libstdc++-v3/include/debug/deque
@@ -683,8 +683,231 @@ 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
+_GLIBCXX_END_NAMESPACE_VERSION
+} // namespace std
+
+namespace __gnu_debug
+{
+ template<typename _Tp, typename _Alloc>
+ using _SDeque_iterator = _Safe_iterator<
+ ::std::_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>,
+ ::std::__debug::deque<_Tp, _Alloc> >;
+
+ template<typename _Tp, typename _Alloc>
+ using _SDeque_const_iterator = _Safe_iterator<
+ ::std::_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
+ ::std::__debug::deque<_Tp, _Alloc> >;
+}
+
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+ template<typename _Tp, typename _Alloc1, typename _Alloc2>
+ ::__gnu_debug::_SDeque_iterator<_Tp, _Alloc2>
+ move(const ::__gnu_debug::_SDeque_const_iterator<_Tp, _Alloc1>& __first,
+ const ::__gnu_debug::_SDeque_const_iterator<_Tp, _Alloc1>& __last,
+ const ::__gnu_debug::_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>
+ ::__gnu_debug::_SDeque_iterator<_Tp, _Alloc2>
+ move(const ::__gnu_debug::_SDeque_iterator<_Tp, _Alloc1>& __first,
+ const ::__gnu_debug::_SDeque_iterator<_Tp, _Alloc1>& __last,
+ const ::__gnu_debug::_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 _Tp, typename _Alloc1, typename _Alloc2>
+ ::__gnu_debug::_SDeque_iterator<_Tp, _Alloc2>
+ move_backward(
+ const ::__gnu_debug::_SDeque_const_iterator<_Tp, _Alloc1>& __first,
+ const ::__gnu_debug::_SDeque_const_iterator<_Tp, _Alloc1>& __last,
+ const ::__gnu_debug::_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>
+ ::__gnu_debug::_SDeque_iterator<_Tp, _Alloc2>
+ move_backward(
+ const ::__gnu_debug::_SDeque_iterator<_Tp, _Alloc1>& __first,
+ const ::__gnu_debug::_SDeque_iterator<_Tp, _Alloc1>& __last,
+ const ::__gnu_debug::_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()
+ };
+ }
+#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..525842996a5
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/copy.cc
@@ -0,0 +1,59 @@
+// 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 <algorithm>
+#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()) );
+}
+
+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..f383aab618d
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/copy_backward.cc
@@ -0,0 +1,59 @@
+// 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 <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ deque<int> d;
+ for (int i = 0; i != _GLIBCXX_STD_A::__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_A::__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()) );
+}
+
+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..54e7b9a34e3
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/fill.cc
@@ -0,0 +1,58 @@
+// 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 <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..924178852a2
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/move.cc
@@ -0,0 +1,60 @@
+// { 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 <algorithm>
+#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()) );
+}
+
+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..81c88736f30
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/deque/move_backward.cc
@@ -0,0 +1,60 @@
+// { 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 <algorithm>
+#include <deque>
+
+#include <testsuite_hooks.h>
+
+void test01()
+{
+ using namespace std;
+
+ deque<int> d;
+ for (int i = 0; i != _GLIBCXX_STD_A::__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_A::__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()) );
+}
+
+int main()
+{
+ test01();
+ test02();
+ return 0;
+}