// Deque implementation (out of line) -*- C++ -*-
-// Copyright (C) 2001-2018 Free Software Foundation, Inc.
+// Copyright (C) 2001-2024 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
#ifndef _DEQUE_TCC
#define _DEQUE_TCC 1
+#include <bits/stl_algobase.h>
+
namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
{
_Map_pointer __cur;
__try
- {
- for (__cur = this->_M_impl._M_start._M_node;
+ {
+ for (__cur = this->_M_impl._M_start._M_node;
__cur < this->_M_impl._M_finish._M_node;
++__cur)
- std::__uninitialized_default_a(*__cur, *__cur + _S_buffer_size(),
+ std::__uninitialized_default_a(*__cur, *__cur + _S_buffer_size(),
_M_get_Tp_allocator());
- std::__uninitialized_default_a(this->_M_impl._M_finish._M_first,
+ std::__uninitialized_default_a(this->_M_impl._M_finish._M_first,
this->_M_impl._M_finish._M_cur,
_M_get_Tp_allocator());
- }
+ }
__catch(...)
- {
- std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
+ {
+ std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
_M_get_Tp_allocator());
- __throw_exception_again;
- }
+ __throw_exception_again;
+ }
}
#endif
deque<_Tp, _Alloc>::
operator=(const deque& __x)
{
- if (&__x != this)
+ if (std::__addressof(__x) != this)
{
#if __cplusplus >= 201103L
if (_Alloc_traits::_S_propagate_on_copy_assign())
{
if (!_Alloc_traits::_S_always_equal()
- && _M_get_Tp_allocator() != __x._M_get_Tp_allocator())
- {
+ && _M_get_Tp_allocator() != __x._M_get_Tp_allocator())
+ {
// Replacement allocator cannot free existing storage,
// so deallocate everything and take copy of __x's data.
_M_replace_map(__x, __x.get_allocator());
if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
{
_Alloc_traits::construct(this->_M_impl,
- this->_M_impl._M_start._M_cur - 1,
- std::forward<_Args>(__args)...);
+ this->_M_impl._M_start._M_cur - 1,
+ std::forward<_Args>(__args)...);
--this->_M_impl._M_start._M_cur;
}
else
!= this->_M_impl._M_finish._M_last - 1)
{
_Alloc_traits::construct(this->_M_impl,
- this->_M_impl._M_finish._M_cur,
- std::forward<_Args>(__args)...);
+ this->_M_impl._M_finish._M_cur,
+ std::forward<_Args>(__args)...);
++this->_M_impl._M_finish._M_cur;
}
else
_M_assign_aux(_InputIterator __first, _InputIterator __last,
std::input_iterator_tag)
{
- iterator __cur = begin();
- for (; __first != __last && __cur != end(); ++__cur, ++__first)
- *__cur = *__first;
- if (__first == __last)
- _M_erase_at_end(__cur);
- else
- _M_range_insert_aux(end(), __first, __last,
+ iterator __cur = begin();
+ for (; __first != __last && __cur != end(); ++__cur, (void)++__first)
+ *__cur = *__first;
+ if (__first == __last)
+ _M_erase_at_end(__cur);
+ else
+ _M_range_insert_aux(end(), __first, __last,
std::__iterator_category(__first));
}
}
}
else
- _M_insert_aux(__pos, __n, __x);
+ _M_insert_aux(__pos, __n, __x);
}
#if __cplusplus >= 201103L
{
_Map_pointer __cur;
__try
- {
- for (__cur = this->_M_impl._M_start._M_node;
+ {
+ for (__cur = this->_M_impl._M_start._M_node;
__cur < this->_M_impl._M_finish._M_node;
++__cur)
- std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
+ std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
__value, _M_get_Tp_allocator());
- std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
+ std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
this->_M_impl._M_finish._M_cur,
__value, _M_get_Tp_allocator());
- }
+ }
__catch(...)
- {
- std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
+ {
+ std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
_M_get_Tp_allocator());
- __throw_exception_again;
- }
+ __throw_exception_again;
+ }
}
template <typename _Tp, typename _Alloc>
void
deque<_Tp, _Alloc>::
_M_range_initialize(_InputIterator __first, _InputIterator __last,
- std::input_iterator_tag)
+ std::input_iterator_tag)
{
- this->_M_initialize_map(0);
- __try
- {
- for (; __first != __last; ++__first)
+ this->_M_initialize_map(0);
+ __try
+ {
+ for (; __first != __last; ++__first)
#if __cplusplus >= 201103L
emplace_back(*__first);
#else
- push_back(*__first);
+ push_back(*__first);
#endif
- }
- __catch(...)
- {
- clear();
- __throw_exception_again;
- }
+ }
+ __catch(...)
+ {
+ clear();
+ __throw_exception_again;
+ }
}
template <typename _Tp, typename _Alloc>
void
deque<_Tp, _Alloc>::
_M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
- std::forward_iterator_tag)
+ std::forward_iterator_tag)
{
- const size_type __n = std::distance(__first, __last);
- this->_M_initialize_map(__n);
-
- _Map_pointer __cur_node;
- __try
- {
- for (__cur_node = this->_M_impl._M_start._M_node;
- __cur_node < this->_M_impl._M_finish._M_node;
- ++__cur_node)
+ const size_type __n = std::distance(__first, __last);
+ this->_M_initialize_map(_S_check_init_len(__n, _M_get_Tp_allocator()));
+
+ _Map_pointer __cur_node;
+ __try
+ {
+ for (__cur_node = this->_M_impl._M_start._M_node;
+ __cur_node < this->_M_impl._M_finish._M_node;
+ ++__cur_node)
{
+ if (__n < _S_buffer_size())
+ __builtin_unreachable(); // See PR 100516
+
_ForwardIterator __mid = __first;
std::advance(__mid, _S_buffer_size());
std::__uninitialized_copy_a(__first, __mid, *__cur_node,
_M_get_Tp_allocator());
__first = __mid;
}
- std::__uninitialized_copy_a(__first, __last,
+ std::__uninitialized_copy_a(__first, __last,
this->_M_impl._M_finish._M_first,
_M_get_Tp_allocator());
- }
- __catch(...)
- {
- std::_Destroy(this->_M_impl._M_start,
+ }
+ __catch(...)
+ {
+ std::_Destroy(this->_M_impl._M_start,
iterator(*__cur_node, __cur_node),
_M_get_Tp_allocator());
- __throw_exception_again;
- }
+ __throw_exception_again;
+ }
}
// Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
_M_push_back_aux(const value_type& __t)
#endif
{
+ if (size() == max_size())
+ __throw_length_error(
+ __N("cannot create std::deque larger than max_size()"));
+
_M_reserve_map_at_back();
*(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
__try
{
#if __cplusplus >= 201103L
_Alloc_traits::construct(this->_M_impl,
- this->_M_impl._M_finish._M_cur,
- std::forward<_Args>(__args)...);
+ this->_M_impl._M_finish._M_cur,
+ std::forward<_Args>(__args)...);
#else
this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
#endif
_M_push_front_aux(const value_type& __t)
#endif
{
+ if (size() == max_size())
+ __throw_length_error(
+ __N("cannot create std::deque larger than max_size()"));
+
_M_reserve_map_at_front();
*(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
__try
this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
#if __cplusplus >= 201103L
_Alloc_traits::construct(this->_M_impl,
- this->_M_impl._M_start._M_cur,
- std::forward<_Args>(__args)...);
+ this->_M_impl._M_start._M_cur,
+ std::forward<_Args>(__args)...);
#else
this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
#endif
void
deque<_Tp, _Alloc>::
_M_range_insert_aux(iterator __pos,
- _InputIterator __first, _InputIterator __last,
- std::input_iterator_tag)
+ _InputIterator __first, _InputIterator __last,
+ std::input_iterator_tag)
{ std::copy(__first, __last, std::inserter(*this, __pos)); }
template <typename _Tp, typename _Alloc>
void
deque<_Tp, _Alloc>::
_M_range_insert_aux(iterator __pos,
- _ForwardIterator __first, _ForwardIterator __last,
- std::forward_iterator_tag)
+ _ForwardIterator __first, _ForwardIterator __last,
+ std::forward_iterator_tag)
{
- const size_type __n = std::distance(__first, __last);
- if (__pos._M_cur == this->_M_impl._M_start._M_cur)
+ const size_type __n = std::distance(__first, __last);
+ if (__pos._M_cur == this->_M_impl._M_start._M_cur)
{
iterator __new_start = _M_reserve_elements_at_front(__n);
__try
__throw_exception_again;
}
}
- else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
+ else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
{
iterator __new_finish = _M_reserve_elements_at_back(__n);
__try
__throw_exception_again;
}
}
- else
- _M_insert_aux(__pos, __first, __last, __n);
+ else
+ _M_insert_aux(__pos, __first, __last, __n);
}
template<typename _Tp, typename _Alloc>
void
deque<_Tp, _Alloc>::
_M_insert_aux(iterator __pos,
- _ForwardIterator __first, _ForwardIterator __last,
- size_type __n)
+ _ForwardIterator __first, _ForwardIterator __last,
+ size_type __n)
{
- const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
- const size_type __length = size();
- if (static_cast<size_type>(__elemsbefore) < __length / 2)
+ const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
+ const size_type __length = size();
+ if (static_cast<size_type>(__elemsbefore) < __length / 2)
{
iterator __new_start = _M_reserve_elements_at_front(__n);
iterator __old_start = this->_M_impl._M_start;
__throw_exception_again;
}
}
- else
- {
- iterator __new_finish = _M_reserve_elements_at_back(__n);
- iterator __old_finish = this->_M_impl._M_finish;
- const difference_type __elemsafter =
- difference_type(__length) - __elemsbefore;
- __pos = this->_M_impl._M_finish - __elemsafter;
- __try
- {
- if (__elemsafter > difference_type(__n))
+ else
+ {
+ iterator __new_finish = _M_reserve_elements_at_back(__n);
+ iterator __old_finish = this->_M_impl._M_finish;
+ const difference_type __elemsafter =
+ difference_type(__length) - __elemsbefore;
+ __pos = this->_M_impl._M_finish - __elemsafter;
+ __try
+ {
+ if (__elemsafter > difference_type(__n))
{
iterator __finish_n = (this->_M_impl._M_finish
- difference_type(__n));
_GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
std::copy(__first, __last, __pos);
}
- else
+ else
{
_ForwardIterator __mid = __first;
std::advance(__mid, __elemsafter);
this->_M_impl._M_finish = __new_finish;
std::copy(__first, __mid, __pos);
}
- }
- __catch(...)
- {
- _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
+ }
+ __catch(...)
+ {
+ _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
__new_finish._M_node + 1);
- __throw_exception_again;
- }
- }
+ __throw_exception_again;
+ }
+ }
}
template<typename _Tp, typename _Alloc>
_M_reserve_map_at_front(__new_nodes);
size_type __i;
__try
- {
- for (__i = 1; __i <= __new_nodes; ++__i)
- *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
- }
+ {
+ for (__i = 1; __i <= __new_nodes; ++__i)
+ *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
+ }
__catch(...)
- {
- for (size_type __j = 1; __j < __i; ++__j)
- _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
- __throw_exception_again;
- }
+ {
+ for (size_type __j = 1; __j < __i; ++__j)
+ _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
+ __throw_exception_again;
+ }
}
template <typename _Tp, typename _Alloc>
_M_reserve_map_at_back(__new_nodes);
size_type __i;
__try
- {
- for (__i = 1; __i <= __new_nodes; ++__i)
- *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
- }
+ {
+ for (__i = 1; __i <= __new_nodes; ++__i)
+ *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
+ }
__catch(...)
- {
- for (size_type __j = 1; __j < __i; ++__j)
- _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
- __throw_exception_again;
- }
+ {
+ for (size_type __j = 1; __j < __i; ++__j)
+ _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
+ __throw_exception_again;
+ }
}
template <typename _Tp, typename _Alloc>
{
__new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
- __new_num_nodes) / 2
- + (__add_at_front ? __nodes_to_add : 0);
+ + (__add_at_front ? __nodes_to_add : 0);
if (__new_nstart < this->_M_impl._M_start._M_node)
std::copy(this->_M_impl._M_start._M_node,
this->_M_impl._M_finish._M_node + 1,
else
{
size_type __new_map_size = this->_M_impl._M_map_size
- + std::max(this->_M_impl._M_map_size,
+ + std::max(this->_M_impl._M_map_size,
__nodes_to_add) + 2;
_Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
__new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
- + (__add_at_front ? __nodes_to_add : 0);
+ + (__add_at_front ? __nodes_to_add : 0);
std::copy(this->_M_impl._M_start._M_node,
this->_M_impl._M_finish._M_node + 1,
__new_nstart);
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>
+ template<typename _Tp, typename _VTp>
void
- fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
- const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
+ __fill_a1(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __last,
+ const _VTp& __value)
{
- typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
+ if (__first._M_node != __last._M_node)
+ {
+ std::__fill_a1(__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);
+ for (typename _Iter::_Map_pointer __node = __first._M_node + 1;
+ __node < __last._M_node; ++__node)
+ std::__fill_a1(*__node, *__node + _Iter::_S_buffer_size(), __value);
+
+ std::__fill_a1(__last._M_first, __last._M_cur, __value);
+ }
+ else
+ std::__fill_a1(__first._M_cur, __last._M_cur, __value);
+ }
+ template<bool _IsMove,
+ typename _Tp, typename _Ref, typename _Ptr, typename _OI>
+ _OI
+ __copy_move_dit(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
+ _OI __result)
+ {
+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
if (__first._M_node != __last._M_node)
{
- std::fill(__first._M_cur, __first._M_last, __value);
- std::fill(__last._M_first, __last._M_cur, __value);
+ __result
+ = std::__copy_move_a1<_IsMove>(__first._M_cur, __first._M_last,
+ __result);
+
+ for (typename _Iter::_Map_pointer __node = __first._M_node + 1;
+ __node != __last._M_node; ++__node)
+ __result
+ = std::__copy_move_a1<_IsMove>(*__node,
+ *__node + _Iter::_S_buffer_size(),
+ __result);
+
+ return std::__copy_move_a1<_IsMove>(__last._M_first, __last._M_cur,
+ __result);
}
- else
- std::fill(__first._M_cur, __last._M_cur, __value);
+
+ return std::__copy_move_a1<_IsMove>(__first._M_cur, __last._M_cur,
+ __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)
+ template<bool _IsMove,
+ typename _Tp, typename _Ref, typename _Ptr, typename _OI>
+ _OI
+ __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
+ _OI __result)
+ { return __copy_move_dit<_IsMove>(__first, __last, __result); }
+
+ template<bool _IsMove,
+ typename _ITp, typename _IRef, typename _IPtr, typename _OTp>
+ _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
+ __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last,
+ _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result)
+ { return __copy_move_dit<_IsMove>(__first, __last, __result); }
+
+ template<bool _IsMove, typename _II, typename _Tp>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II>::__value,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
+ __copy_move_a1(_II __first, _II __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;
+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
+ typedef typename _Iter::difference_type difference_type;
difference_type __len = __last - __first;
while (__len > 0)
{
const difference_type __clen
- = std::min(__len, 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);
+ = std::min(__len, __result._M_last - __result._M_cur);
+ std::__copy_move_a1<_IsMove>(__first, __first + __clen,
+ __result._M_cur);
+
__first += __clen;
__result += __clen;
__len -= __clen;
}
+
+ return __result;
+ }
+
+ template<bool _IsMove, typename _CharT>
+ typename __gnu_cxx::__enable_if<
+ __is_char<_CharT>::__value,
+ _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
+ __copy_move_a2(
+ istreambuf_iterator<_CharT, char_traits<_CharT> > __first,
+ istreambuf_iterator<_CharT, char_traits<_CharT> > __last,
+ _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> __result)
+ {
+ if (__first == __last)
+ return __result;
+
+ for (;;)
+ {
+ const std::ptrdiff_t __len = __result._M_last - __result._M_cur;
+ const std::ptrdiff_t __nb
+ = std::__copy_n_a(__first, __len, __result._M_cur, false)
+ - __result._M_cur;
+ __result += __nb;
+
+ if (__nb != __len)
+ break;
+ }
+
return __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)
+ template<typename _CharT, typename _Size>
+ typename __gnu_cxx::__enable_if<
+ __is_char<_CharT>::__value,
+ _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
+ __copy_n_a(
+ istreambuf_iterator<_CharT, char_traits<_CharT> > __it, _Size __size,
+ _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> __result,
+ bool __strict)
+ {
+ if (__size == 0)
+ return __result;
+
+ do
+ {
+ const _Size __len
+ = std::min<_Size>(__result._M_last - __result._M_cur, __size);
+ std::__copy_n_a(__it, __len, __result._M_cur, __strict);
+ __result += __len;
+ __size -= __len;
+ }
+ while (__size != 0);
+ return __result;
+ }
+
+ template<bool _IsMove,
+ typename _Tp, typename _Ref, typename _Ptr, typename _OI>
+ _OI
+ __copy_move_backward_dit(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
+ _OI __result)
+ {
+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
+ if (__first._M_node != __last._M_node)
+ {
+ __result = std::__copy_move_backward_a1<_IsMove>(
+ __last._M_first, __last._M_cur, __result);
+
+ for (typename _Iter::_Map_pointer __node = __last._M_node - 1;
+ __node != __first._M_node; --__node)
+ __result = std::__copy_move_backward_a1<_IsMove>(
+ *__node, *__node + _Iter::_S_buffer_size(), __result);
+
+ return std::__copy_move_backward_a1<_IsMove>(
+ __first._M_cur, __first._M_last, __result);
+ }
+
+ return std::__copy_move_backward_a1<_IsMove>(
+ __first._M_cur, __last._M_cur, __result);
+ }
+
+ template<bool _IsMove,
+ typename _Tp, typename _Ref, typename _Ptr, typename _OI>
+ _OI
+ __copy_move_backward_a1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
+ _OI __result)
+ { return __copy_move_backward_dit<_IsMove>(__first, __last, __result); }
+
+ template<bool _IsMove,
+ typename _ITp, typename _IRef, typename _IPtr, typename _OTp>
+ _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
+ __copy_move_backward_a1(
+ _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first,
+ _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last,
+ _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result)
+ { return __copy_move_backward_dit<_IsMove>(__first, __last, __result); }
+
+ template<bool _IsMove, typename _II, typename _Tp>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II>::__value,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
+ __copy_move_backward_a1(_II __first, _II __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;
+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
+ typedef typename _Iter::difference_type difference_type;
difference_type __len = __last - __first;
while (__len > 0)
{
- difference_type __llen = __last._M_cur - __last._M_first;
- _Tp* __lend = __last._M_cur;
-
difference_type __rlen = __result._M_cur - __result._M_first;
_Tp* __rend = __result._M_cur;
-
- if (!__llen)
- {
- __llen = _Self::_S_buffer_size();
- __lend = *(__last._M_node - 1) + __llen;
- }
if (!__rlen)
{
- __rlen = _Self::_S_buffer_size();
+ __rlen = _Iter::_S_buffer_size();
__rend = *(__result._M_node - 1) + __rlen;
}
- const difference_type __clen = std::min(__len,
- std::min(__llen, __rlen));
- std::copy_backward(__lend - __clen, __lend, __rend);
+ const difference_type __clen = std::min(__len, __rlen);
+ std::__copy_move_backward_a1<_IsMove>(__last - __clen, __last, __rend);
+
__last -= __clen;
__result -= __clen;
__len -= __clen;
}
+
return __result;
}
-#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)
+ template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
+ bool
+ __equal_dit(
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __first1,
+ const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __last1,
+ _II __first2)
{
- typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
- typedef typename _Self::difference_type difference_type;
+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
+ if (__first1._M_node != __last1._M_node)
+ {
+ if (!std::__equal_aux1(__first1._M_cur, __first1._M_last, __first2))
+ return false;
+
+ __first2 += __first1._M_last - __first1._M_cur;
+ for (typename _Iter::_Map_pointer __node = __first1._M_node + 1;
+ __node != __last1._M_node;
+ __first2 += _Iter::_S_buffer_size(), ++__node)
+ if (!std::__equal_aux1(*__node, *__node + _Iter::_S_buffer_size(),
+ __first2))
+ return false;
+
+ return std::__equal_aux1(__last1._M_first, __last1._M_cur, __first2);
+ }
- difference_type __len = __last - __first;
+ return std::__equal_aux1(__first1._M_cur, __last1._M_cur, __first2);
+ }
+
+ template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II>::__value, bool>::__type
+ __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last1,
+ _II __first2)
+ { return std::__equal_dit(__first1, __last1, __first2); }
+
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ bool
+ __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2)
+ { return std::__equal_dit(__first1, __last1, __first2); }
+
+ template<typename _II, typename _Tp, typename _Ref, typename _Ptr>
+ typename __gnu_cxx::__enable_if<
+ __is_random_access_iter<_II>::__value, bool>::__type
+ __equal_aux1(_II __first1, _II __last1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first2)
+ {
+ typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
+ typedef typename _Iter::difference_type difference_type;
+
+ difference_type __len = __last1 - __first1;
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;
+ = std::min(__len, __first2._M_last - __first2._M_cur);
+ if (!std::__equal_aux1(__first1, __first1 + __clen, __first2._M_cur))
+ return false;
+
+ __first1 += __clen;
__len -= __clen;
+ __first2 += __clen;
}
- return __result;
+
+ return true;
}
- 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)
+ template<typename _Tp1, typename _Ref, typename _Ptr, typename _Tp2>
+ int
+ __lex_cmp_dit(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __last1,
+ const _Tp2* __first2, const _Tp2* __last2)
{
- typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
- typedef typename _Self::difference_type difference_type;
+ const bool __simple =
+ (__is_memcmp_ordered_with<_Tp1, _Tp2>::__value
+ && __is_pointer<_Ptr>::__value
+#if __cplusplus > 201703L && __cpp_lib_concepts
+ // For C++20 iterator_traits<volatile T*>::value_type is non-volatile
+ // so __is_byte<T> could be true, but we can't use memcmp with
+ // volatile data.
+ && !is_volatile_v<_Tp1>
+ && !is_volatile_v<_Tp2>
+#endif
+ );
+ typedef std::__lexicographical_compare<__simple> _Lc;
- difference_type __len = __last - __first;
- while (__len > 0)
+ while (__first1._M_node != __last1._M_node)
{
- difference_type __llen = __last._M_cur - __last._M_first;
- _Tp* __lend = __last._M_cur;
-
- difference_type __rlen = __result._M_cur - __result._M_first;
- _Tp* __rend = __result._M_cur;
+ const ptrdiff_t __len1 = __first1._M_last - __first1._M_cur;
+ const ptrdiff_t __len2 = __last2 - __first2;
+ const ptrdiff_t __len = std::min(__len1, __len2);
+ // if __len1 > __len2 this will return a positive value:
+ if (int __ret = _Lc::__3way(__first1._M_cur, __first1._M_last,
+ __first2, __first2 + __len))
+ return __ret;
+
+ __first1 += __len;
+ __first2 += __len;
+ }
+ return _Lc::__3way(__first1._M_cur, __last1._M_cur,
+ __first2, __last2);
+ }
- if (!__llen)
- {
- __llen = _Self::_S_buffer_size();
- __lend = *(__last._M_node - 1) + __llen;
- }
- if (!__rlen)
- {
- __rlen = _Self::_S_buffer_size();
- __rend = *(__result._M_node - 1) + __rlen;
- }
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _Tp2>
+ inline bool
+ __lexicographical_compare_aux1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
+ _Tp2* __first2, _Tp2* __last2)
+ { return std::__lex_cmp_dit(__first1, __last1, __first2, __last2) < 0; }
+
+ template<typename _Tp1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ inline bool
+ __lexicographical_compare_aux1(_Tp1* __first1, _Tp1* __last1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
+ { return std::__lex_cmp_dit(__first2, __last2, __first1, __last1) > 0; }
+
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ inline bool
+ __lexicographical_compare_aux1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
+ {
+ const bool __simple =
+ (__is_memcmp_ordered_with<_Tp1, _Tp2>::__value
+ && __is_pointer<_Ptr1>::__value
+ && __is_pointer<_Ptr2>::__value
+#if __cplusplus > 201703L && __cpp_lib_concepts
+ // For C++20 iterator_traits<volatile T*>::value_type is non-volatile
+ // so __is_byte<T> could be true, but we can't use memcmp with
+ // volatile data.
+ && !is_volatile_v<_Tp1>
+ && !is_volatile_v<_Tp2>
+#endif
+ );
+ typedef std::__lexicographical_compare<__simple> _Lc;
- const difference_type __clen = std::min(__len,
- std::min(__llen, __rlen));
- std::move_backward(__lend - __clen, __lend, __rend);
- __last -= __clen;
- __result -= __clen;
- __len -= __clen;
+ while (__first1 != __last1)
+ {
+ const ptrdiff_t __len2 = __first2._M_node == __last2._M_node
+ ? __last2._M_cur - __first2._M_cur
+ : __first2._M_last - __first2._M_cur;
+ if (__len2 == 0)
+ return false;
+ const ptrdiff_t __len1 = __first1._M_node == __last1._M_node
+ ? __last1._M_cur - __first1._M_cur
+ : __first1._M_last - __first1._M_cur;
+ const ptrdiff_t __len = std::min(__len1, __len2);
+ if (int __ret = _Lc::__3way(__first1._M_cur, __first1._M_cur + __len,
+ __first2._M_cur, __first2._M_cur + __len))
+ return __ret < 0;
+
+ __first1 += __len;
+ __first2 += __len;
}
- return __result;
+
+ return __last2 != __first2;
}
-#endif
-_GLIBCXX_END_NAMESPACE_CONTAINER
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std