// Deque implementation (out of line) -*- C++ -*-
-// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
-// 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
* purpose. It is provided "as is" without express or implied warranty.
*/
-/** @file deque.tcc
+/** @file bits/deque.tcc
* This is an internal header file, included by other library headers.
- * You should not attempt to use it directly.
+ * Do not attempt to use it directly. @headername{deque}
*/
#ifndef _DEQUE_TCC
#define _DEQUE_TCC 1
-_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
+#include <bits/stl_algobase.h>
+
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
+
+#if __cplusplus >= 201103L
+ template <typename _Tp, typename _Alloc>
+ void
+ deque<_Tp, _Alloc>::
+ _M_default_initialize()
+ {
+ _Map_pointer __cur;
+ __try
+ {
+ 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(),
+ _M_get_Tp_allocator());
+ 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),
+ _M_get_Tp_allocator());
+ __throw_exception_again;
+ }
+ }
+#endif
template <typename _Tp, typename _Alloc>
deque<_Tp, _Alloc>&
deque<_Tp, _Alloc>::
operator=(const deque& __x)
{
- const size_type __len = size();
- 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())
+ {
+ // Replacement allocator cannot free existing storage,
+ // so deallocate everything and take copy of __x's data.
+ _M_replace_map(__x, __x.get_allocator());
+ std::__alloc_on_copy(_M_get_Tp_allocator(),
+ __x._M_get_Tp_allocator());
+ return *this;
+ }
+ std::__alloc_on_copy(_M_get_Tp_allocator(),
+ __x._M_get_Tp_allocator());
+ }
+#endif
+ const size_type __len = size();
if (__len >= __x.size())
_M_erase_at_end(std::copy(__x.begin(), __x.end(),
this->_M_impl._M_start));
{
const_iterator __mid = __x.begin() + difference_type(__len);
std::copy(__x.begin(), __mid, this->_M_impl._M_start);
- insert(this->_M_impl._M_finish, __mid, __x.end());
+ _M_range_insert_aux(this->_M_impl._M_finish, __mid, __x.end(),
+ std::random_access_iterator_tag());
}
}
return *this;
}
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
+#if __cplusplus >= 201103L
template<typename _Tp, typename _Alloc>
template<typename... _Args>
+#if __cplusplus > 201402L
+ typename deque<_Tp, _Alloc>::reference
+#else
void
+#endif
deque<_Tp, _Alloc>::
emplace_front(_Args&&... __args)
{
if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
{
- this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1,
- std::forward<_Args>(__args)...);
+ _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;
}
else
_M_push_front_aux(std::forward<_Args>(__args)...);
+#if __cplusplus > 201402L
+ return front();
+#endif
}
template<typename _Tp, typename _Alloc>
template<typename... _Args>
+#if __cplusplus > 201402L
+ typename deque<_Tp, _Alloc>::reference
+#else
void
+#endif
deque<_Tp, _Alloc>::
emplace_back(_Args&&... __args)
{
if (this->_M_impl._M_finish._M_cur
!= this->_M_impl._M_finish._M_last - 1)
{
- this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
- std::forward<_Args>(__args)...);
+ _Alloc_traits::construct(this->_M_impl,
+ this->_M_impl._M_finish._M_cur,
+ std::forward<_Args>(__args)...);
++this->_M_impl._M_finish._M_cur;
}
else
_M_push_back_aux(std::forward<_Args>(__args)...);
+#if __cplusplus > 201402L
+ return back();
+#endif
}
#endif
- template <typename _Tp, typename _Alloc>
- typename deque<_Tp, _Alloc>::iterator
- deque<_Tp, _Alloc>::
- insert(iterator __position, const value_type& __x)
- {
- if (__position._M_cur == this->_M_impl._M_start._M_cur)
- {
- push_front(__x);
- return this->_M_impl._M_start;
- }
- else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
- {
- push_back(__x);
- iterator __tmp = this->_M_impl._M_finish;
- --__tmp;
- return __tmp;
- }
- else
- return _M_insert_aux(__position, __x);
- }
-
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
+#if __cplusplus >= 201103L
template<typename _Tp, typename _Alloc>
template<typename... _Args>
typename deque<_Tp, _Alloc>::iterator
deque<_Tp, _Alloc>::
- emplace(iterator __position, _Args&&... __args)
+ emplace(const_iterator __position, _Args&&... __args)
{
if (__position._M_cur == this->_M_impl._M_start._M_cur)
{
- push_front(std::forward<_Args>(__args)...);
+ emplace_front(std::forward<_Args>(__args)...);
return this->_M_impl._M_start;
}
else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
{
- push_back(std::forward<_Args>(__args)...);
+ emplace_back(std::forward<_Args>(__args)...);
iterator __tmp = this->_M_impl._M_finish;
--__tmp;
return __tmp;
}
else
- return _M_insert_aux(__position, std::forward<_Args>(__args)...);
+ return _M_insert_aux(__position._M_const_cast(),
+ std::forward<_Args>(__args)...);
}
#endif
template <typename _Tp, typename _Alloc>
typename deque<_Tp, _Alloc>::iterator
deque<_Tp, _Alloc>::
- erase(iterator __position)
+#if __cplusplus >= 201103L
+ insert(const_iterator __position, const value_type& __x)
+#else
+ insert(iterator __position, const value_type& __x)
+#endif
+ {
+ if (__position._M_cur == this->_M_impl._M_start._M_cur)
+ {
+ push_front(__x);
+ return this->_M_impl._M_start;
+ }
+ else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
+ {
+ push_back(__x);
+ iterator __tmp = this->_M_impl._M_finish;
+ --__tmp;
+ return __tmp;
+ }
+ else
+ return _M_insert_aux(__position._M_const_cast(), __x);
+ }
+
+ template <typename _Tp, typename _Alloc>
+ typename deque<_Tp, _Alloc>::iterator
+ deque<_Tp, _Alloc>::
+ _M_erase(iterator __position)
{
iterator __next = __position;
++__next;
template <typename _Tp, typename _Alloc>
typename deque<_Tp, _Alloc>::iterator
deque<_Tp, _Alloc>::
- erase(iterator __first, iterator __last)
+ _M_erase(iterator __first, iterator __last)
{
- if (__first == begin() && __last == end())
+ if (__first == __last)
+ return __first;
+ else if (__first == begin() && __last == end())
{
clear();
return end();
_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
- insert(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));
}
template <typename _Tp, typename _Alloc>
}
}
else
- _M_insert_aux(__pos, __n, __x);
+ _M_insert_aux(__pos, __n, __x);
+ }
+
+#if __cplusplus >= 201103L
+ template <typename _Tp, typename _Alloc>
+ void
+ deque<_Tp, _Alloc>::
+ _M_default_append(size_type __n)
+ {
+ if (__n)
+ {
+ iterator __new_finish = _M_reserve_elements_at_back(__n);
+ __try
+ {
+ std::__uninitialized_default_a(this->_M_impl._M_finish,
+ __new_finish,
+ _M_get_Tp_allocator());
+ this->_M_impl._M_finish = __new_finish;
+ }
+ __catch(...)
+ {
+ _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
+ __new_finish._M_node + 1);
+ __throw_exception_again;
+ }
+ }
}
+ template <typename _Tp, typename _Alloc>
+ bool
+ deque<_Tp, _Alloc>::
+ _M_shrink_to_fit()
+ {
+ const difference_type __front_capacity
+ = (this->_M_impl._M_start._M_cur - this->_M_impl._M_start._M_first);
+ if (__front_capacity == 0)
+ return false;
+
+ const difference_type __back_capacity
+ = (this->_M_impl._M_finish._M_last - this->_M_impl._M_finish._M_cur);
+ if (__front_capacity + __back_capacity < _S_buffer_size())
+ return false;
+
+ return std::__shrink_to_fit_aux<deque>::_S_do_it(*this);
+ }
+#endif
+
template <typename _Tp, typename _Alloc>
void
deque<_Tp, _Alloc>::
{
_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)
- push_back(*__first);
- }
- __catch(...)
- {
- clear();
- __throw_exception_again;
- }
+ this->_M_initialize_map(0);
+ __try
+ {
+ for (; __first != __last; ++__first)
+#if __cplusplus >= 201103L
+ emplace_back(*__first);
+#else
+ push_back(*__first);
+#endif
+ }
+ __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.
template<typename _Tp, typename _Alloc>
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
+#if __cplusplus >= 201103L
template<typename... _Args>
void
deque<_Tp, _Alloc>::
_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
{
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
- this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
- std::forward<_Args>(__args)...);
+#if __cplusplus >= 201103L
+ _Alloc_traits::construct(this->_M_impl,
+ 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
// Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
template<typename _Tp, typename _Alloc>
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
+#if __cplusplus >= 201103L
template<typename... _Args>
void
deque<_Tp, _Alloc>::
_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_set_node(this->_M_impl._M_start._M_node
- 1);
this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
- this->_M_impl.construct(this->_M_impl._M_start._M_cur,
- std::forward<_Args>(__args)...);
+#if __cplusplus >= 201103L
+ _Alloc_traits::construct(this->_M_impl,
+ 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
_M_deallocate_node(this->_M_impl._M_finish._M_first);
this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
- this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
+ _Alloc_traits::destroy(_M_get_Tp_allocator(),
+ this->_M_impl._M_finish._M_cur);
}
// Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
void deque<_Tp, _Alloc>::
_M_pop_front_aux()
{
- this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
+ _Alloc_traits::destroy(_M_get_Tp_allocator(),
+ this->_M_impl._M_start._M_cur);
_M_deallocate_node(this->_M_impl._M_start._M_first);
this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
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>
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
+#if __cplusplus >= 201103L
template<typename... _Args>
typename deque<_Tp, _Alloc>::iterator
deque<_Tp, _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". NB: leave const_iterators alone!
- template<typename _Tp>
+ // optimization".
+ 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 _Iter::_Map_pointer __node = __first._M_node + 1;
+ __node < __last._M_node; ++__node)
+ std::__fill_a1(*__node, *__node + _Iter::_S_buffer_size(), __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_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<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 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
+ typedef typename _Iter::difference_type difference_type;
+
+ difference_type __len = __last - __first;
+ while (__len > 0)
+ {
+ const difference_type __clen
+ = std::min(__len, __result._M_last - __result._M_cur);
+ std::__copy_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 _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 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
+ typedef typename _Iter::difference_type difference_type;
+
+ difference_type __len = __last - __first;
+ while (__len > 0)
+ {
+ difference_type __rlen = __result._M_cur - __result._M_first;
+ _Tp* __rend = __result._M_cur;
+ if (!__rlen)
+ {
+ __rlen = _Iter::_S_buffer_size();
+ __rend = *(__result._M_node - 1) + __rlen;
+ }
+
+ const difference_type __clen = std::min(__len, __rlen);
+ std::__copy_move_backward_a1<_IsMove>(__last - __clen, __last, __rend);
+
+ __last -= __clen;
+ __result -= __clen;
+ __len -= __clen;
+ }
+
+ return __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 _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);
+ }
+
+ 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, __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 true;
+ }
+
+ 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)
+ {
+ 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;
+
+ while (__first1._M_node != __last1._M_node)
+ {
+ 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);
+ }
+
+ 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;
+
+ 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 __last2 != __first2;
}
-_GLIBCXX_END_NESTED_NAMESPACE
+_GLIBCXX_END_NAMESPACE_VERSION
+} // namespace std
#endif