57 #define _STL_DEQUE_H 1
62 #if __cplusplus >= 201103L
63 #include <initializer_list>
66 namespace std _GLIBCXX_VISIBILITY(default)
68 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
84 #ifndef _GLIBCXX_DEQUE_BUF_SIZE
85 #define _GLIBCXX_DEQUE_BUF_SIZE 512
88 _GLIBCXX_CONSTEXPR
inline size_t
89 __deque_buf_size(
size_t __size)
105 template<
typename _Tp,
typename _Ref,
typename _Ptr>
108 #if __cplusplus < 201103L
111 typedef _Tp* _Elt_pointer;
112 typedef _Tp** _Map_pointer;
115 template<
typename _Up>
117 template<
typename _CvTp>
122 typedef __ptr_to<_Tp> _Elt_pointer;
123 typedef __ptr_to<_Elt_pointer> _Map_pointer;
126 static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
127 {
return __deque_buf_size(
sizeof(_Tp)); }
130 typedef _Tp value_type;
131 typedef _Ptr pointer;
132 typedef _Ref reference;
133 typedef size_t size_type;
134 typedef ptrdiff_t difference_type;
138 _Elt_pointer _M_first;
139 _Elt_pointer _M_last;
140 _Map_pointer _M_node;
143 : _M_cur(__x), _M_first(*__y),
144 _M_last(*__y + _S_buffer_size()), _M_node(__y) { }
147 : _M_cur(), _M_first(), _M_last(), _M_node() { }
150 : _M_cur(__x._M_cur), _M_first(__x._M_first),
151 _M_last(__x._M_last), _M_node(__x._M_node) { }
154 _M_const_cast()
const _GLIBCXX_NOEXCEPT
155 {
return iterator(_M_cur, _M_node); }
158 operator*()
const _GLIBCXX_NOEXCEPT
162 operator->()
const _GLIBCXX_NOEXCEPT
166 operator++() _GLIBCXX_NOEXCEPT
169 if (_M_cur == _M_last)
178 operator++(
int) _GLIBCXX_NOEXCEPT
186 operator--() _GLIBCXX_NOEXCEPT
188 if (_M_cur == _M_first)
198 operator--(
int) _GLIBCXX_NOEXCEPT
206 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
208 const difference_type __offset = __n + (_M_cur - _M_first);
209 if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
213 const difference_type __node_offset =
214 __offset > 0 ? __offset / difference_type(_S_buffer_size())
215 : -difference_type((-__offset - 1)
216 / _S_buffer_size()) - 1;
218 _M_cur = _M_first + (__offset - __node_offset
219 * difference_type(_S_buffer_size()));
225 operator+(difference_type __n)
const _GLIBCXX_NOEXCEPT
232 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
233 {
return *
this += -__n; }
236 operator-(difference_type __n)
const _GLIBCXX_NOEXCEPT
243 operator[](difference_type __n)
const _GLIBCXX_NOEXCEPT
244 {
return *(*
this + __n); }
254 _M_node = __new_node;
255 _M_first = *__new_node;
256 _M_last = _M_first + difference_type(_S_buffer_size());
263 template<
typename _Tp,
typename _Ref,
typename _Ptr>
265 operator==(
const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
266 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT
267 {
return __x._M_cur == __y._M_cur; }
269 template<
typename _Tp,
typename _RefL,
typename _PtrL,
270 typename _RefR,
typename _PtrR>
272 operator==(
const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
273 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
274 {
return __x._M_cur == __y._M_cur; }
276 template<
typename _Tp,
typename _Ref,
typename _Ptr>
278 operator!=(
const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
279 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT
280 {
return !(__x == __y); }
282 template<
typename _Tp,
typename _RefL,
typename _PtrL,
283 typename _RefR,
typename _PtrR>
285 operator!=(
const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
286 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
287 {
return !(__x == __y); }
289 template<
typename _Tp,
typename _Ref,
typename _Ptr>
291 operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
292 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT
293 {
return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
294 : (__x._M_node < __y._M_node); }
296 template<
typename _Tp,
typename _RefL,
typename _PtrL,
297 typename _RefR,
typename _PtrR>
299 operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
300 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
301 {
return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
302 : (__x._M_node < __y._M_node); }
304 template<
typename _Tp,
typename _Ref,
typename _Ptr>
306 operator>(
const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
307 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT
308 {
return __y < __x; }
310 template<
typename _Tp,
typename _RefL,
typename _PtrL,
311 typename _RefR,
typename _PtrR>
313 operator>(
const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
314 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
315 {
return __y < __x; }
317 template<
typename _Tp,
typename _Ref,
typename _Ptr>
319 operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
320 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT
321 {
return !(__y < __x); }
323 template<
typename _Tp,
typename _RefL,
typename _PtrL,
324 typename _RefR,
typename _PtrR>
326 operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
327 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
328 {
return !(__y < __x); }
330 template<
typename _Tp,
typename _Ref,
typename _Ptr>
332 operator>=(
const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
333 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT
334 {
return !(__x < __y); }
336 template<
typename _Tp,
typename _RefL,
typename _PtrL,
337 typename _RefR,
typename _PtrR>
339 operator>=(
const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
340 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
341 {
return !(__x < __y); }
347 template<
typename _Tp,
typename _Ref,
typename _Ptr>
348 inline typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type
349 operator-(
const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
350 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT
352 return typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type
353 (_Deque_iterator<_Tp, _Ref, _Ptr>::_S_buffer_size())
354 * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
355 + (__y._M_last - __y._M_cur);
358 template<
typename _Tp,
typename _RefL,
typename _PtrL,
359 typename _RefR,
typename _PtrR>
360 inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
361 operator-(
const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
362 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
364 return typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
365 (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size())
366 * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
367 + (__y._M_last - __y._M_cur);
370 template<
typename _Tp,
typename _Ref,
typename _Ptr>
371 inline _Deque_iterator<_Tp, _Ref, _Ptr>
372 operator+(ptrdiff_t __n,
const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
374 {
return __x + __n; }
376 template<
typename _Tp>
378 fill(
const _Deque_iterator<_Tp, _Tp&, _Tp*>&,
379 const _Deque_iterator<_Tp, _Tp&, _Tp*>&,
const _Tp&);
381 template<
typename _Tp>
382 _Deque_iterator<_Tp, _Tp&, _Tp*>
383 copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
384 _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
385 _Deque_iterator<_Tp, _Tp&, _Tp*>);
387 template<
typename _Tp>
388 inline _Deque_iterator<_Tp, _Tp&, _Tp*>
389 copy(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
390 _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
391 _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
392 {
return std::copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
393 _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
396 template<
typename _Tp>
397 _Deque_iterator<_Tp, _Tp&, _Tp*>
398 copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
399 _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
400 _Deque_iterator<_Tp, _Tp&, _Tp*>);
402 template<
typename _Tp>
403 inline _Deque_iterator<_Tp, _Tp&, _Tp*>
404 copy_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
405 _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
406 _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
407 {
return std::copy_backward(_Deque_iterator<_Tp,
408 const _Tp&,
const _Tp*>(__first),
410 const _Tp&,
const _Tp*>(__last),
413 #if __cplusplus >= 201103L
414 template<
typename _Tp>
415 _Deque_iterator<_Tp, _Tp&, _Tp*>
416 move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
417 _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
418 _Deque_iterator<_Tp, _Tp&, _Tp*>);
420 template<
typename _Tp>
421 inline _Deque_iterator<_Tp, _Tp&, _Tp*>
422 move(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
423 _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
424 _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
425 {
return std::move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
426 _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
429 template<
typename _Tp>
430 _Deque_iterator<_Tp, _Tp&, _Tp*>
432 _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
433 _Deque_iterator<_Tp, _Tp&, _Tp*>);
435 template<
typename _Tp>
436 inline _Deque_iterator<_Tp, _Tp&, _Tp*>
438 _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
439 _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
441 const _Tp&,
const _Tp*>(__first),
443 const _Tp&,
const _Tp*>(__last),
457 template<
typename _Tp,
typename _Alloc>
462 rebind<_Tp>::other _Tp_alloc_type;
465 #if __cplusplus < 201103L
467 typedef const _Tp* _Ptr_const;
469 typedef typename _Alloc_traits::pointer _Ptr;
470 typedef typename _Alloc_traits::const_pointer _Ptr_const;
473 typedef typename _Alloc_traits::template rebind<_Ptr>::other
478 typedef _Alloc allocator_type;
479 typedef typename _Alloc_traits::size_type size_type;
482 get_allocator()
const _GLIBCXX_NOEXCEPT
483 {
return allocator_type(_M_get_Tp_allocator()); }
496 _Deque_base(
const allocator_type& __a,
size_t __num_elements)
504 #if __cplusplus >= 201103L
506 : _M_impl(__x._M_move_impl())
510 : _M_impl(
std::move(__x._M_get_Tp_allocator()))
513 if (__x._M_impl._M_map)
514 this->_M_impl._M_swap_data(__x._M_impl);
519 __gnu_cxx::__allocator_always_compares_equal<_Alloc>{})
525 if (__x.get_allocator() == __a)
527 if (__x._M_impl._M_map)
530 this->_M_impl._M_swap_data(__x._M_impl);
543 typedef typename iterator::_Map_pointer _Map_pointer;
549 :
public _Tp_alloc_type
557 : _Tp_alloc_type(), _M_map(), _M_map_size(0),
558 _M_start(), _M_finish()
561 _Deque_impl(
const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
562 : _Tp_alloc_type(__a), _M_map(), _M_map_size(0),
563 _M_start(), _M_finish()
566 #if __cplusplus >= 201103L
567 _Deque_impl(_Deque_impl&&) =
default;
569 _Deque_impl(_Tp_alloc_type&& __a) noexcept
570 : _Tp_alloc_type(
std::move(__a)), _M_map(), _M_map_size(0),
571 _M_start(), _M_finish()
575 void _M_swap_data(_Deque_impl& __x) _GLIBCXX_NOEXCEPT
578 swap(this->_M_start, __x._M_start);
579 swap(this->_M_finish, __x._M_finish);
580 swap(this->_M_map, __x._M_map);
581 swap(this->_M_map_size, __x._M_map_size);
586 _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
587 {
return *
static_cast<_Tp_alloc_type*
>(&this->_M_impl); }
589 const _Tp_alloc_type&
590 _M_get_Tp_allocator()
const _GLIBCXX_NOEXCEPT
591 {
return *
static_cast<const _Tp_alloc_type*
>(&this->_M_impl); }
594 _M_get_map_allocator()
const _GLIBCXX_NOEXCEPT
595 {
return _Map_alloc_type(_M_get_Tp_allocator()); }
601 return _Traits::allocate(_M_impl, __deque_buf_size(
sizeof(_Tp)));
605 _M_deallocate_node(_Ptr __p) _GLIBCXX_NOEXCEPT
608 _Traits::deallocate(_M_impl, __p, __deque_buf_size(
sizeof(_Tp)));
612 _M_allocate_map(
size_t __n)
614 _Map_alloc_type __map_alloc = _M_get_map_allocator();
619 _M_deallocate_map(_Map_pointer __p,
size_t __n) _GLIBCXX_NOEXCEPT
621 _Map_alloc_type __map_alloc = _M_get_map_allocator();
627 void _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish);
628 void _M_destroy_nodes(_Map_pointer __nstart,
629 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT;
630 enum { _S_initial_map_size = 8 };
634 #if __cplusplus >= 201103L
643 _Tp_alloc_type __alloc{_M_get_Tp_allocator()};
645 _Tp_alloc_type __sink __attribute((__unused__)) {
std::move(__alloc)};
649 _Deque_impl __ret{
std::move(_M_get_Tp_allocator())};
650 _M_impl._M_swap_data(__ret);
651 _M_impl._M_swap_data(__empty._M_impl);
657 template<
typename _Tp,
typename _Alloc>
661 if (this->_M_impl._M_map)
663 _M_destroy_nodes(this->_M_impl._M_start._M_node,
664 this->_M_impl._M_finish._M_node + 1);
665 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
677 template<
typename _Tp,
typename _Alloc>
682 const size_t __num_nodes = (__num_elements/ __deque_buf_size(
sizeof(_Tp))
685 this->_M_impl._M_map_size =
std::max((
size_t) _S_initial_map_size,
686 size_t(__num_nodes + 2));
687 this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
694 _Map_pointer __nstart = (this->_M_impl._M_map
695 + (this->_M_impl._M_map_size - __num_nodes) / 2);
696 _Map_pointer __nfinish = __nstart + __num_nodes;
699 { _M_create_nodes(__nstart, __nfinish); }
702 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
703 this->_M_impl._M_map = _Map_pointer();
704 this->_M_impl._M_map_size = 0;
705 __throw_exception_again;
708 this->_M_impl._M_start._M_set_node(__nstart);
709 this->_M_impl._M_finish._M_set_node(__nfinish - 1);
710 this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
711 this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
713 % __deque_buf_size(
sizeof(_Tp)));
716 template<
typename _Tp,
typename _Alloc>
724 for (__cur = __nstart; __cur < __nfinish; ++__cur)
725 *__cur = this->_M_allocate_node();
729 _M_destroy_nodes(__nstart, __cur);
730 __throw_exception_again;
734 template<
typename _Tp,
typename _Alloc>
736 _Deque_base<_Tp, _Alloc>::
737 _M_destroy_nodes(_Map_pointer __nstart,
738 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT
740 for (_Map_pointer __n = __nstart; __n < __nfinish; ++__n)
741 _M_deallocate_node(*__n);
828 template<
typename _Tp,
typename _Alloc = std::allocator<_Tp> >
832 typedef typename _Alloc::value_type _Alloc_value_type;
833 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
834 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
837 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
839 typedef typename _Base::_Map_pointer _Map_pointer;
842 typedef _Tp value_type;
843 typedef typename _Alloc_traits::pointer pointer;
844 typedef typename _Alloc_traits::const_pointer const_pointer;
845 typedef typename _Alloc_traits::reference reference;
846 typedef typename _Alloc_traits::const_reference const_reference;
851 typedef size_t size_type;
852 typedef ptrdiff_t difference_type;
853 typedef _Alloc allocator_type;
856 static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
857 {
return __deque_buf_size(
sizeof(_Tp)); }
861 using _Base::_M_create_nodes;
862 using _Base::_M_destroy_nodes;
863 using _Base::_M_allocate_node;
864 using _Base::_M_deallocate_node;
865 using _Base::_M_allocate_map;
866 using _Base::_M_deallocate_map;
867 using _Base::_M_get_Tp_allocator;
873 using _Base::_M_impl;
892 #if __cplusplus >= 201103L
901 deque(size_type __n,
const allocator_type& __a = allocator_type())
903 { _M_default_initialize(); }
913 deque(size_type __n,
const value_type& __value,
914 const allocator_type& __a = allocator_type())
927 deque(size_type __n,
const value_type& __value = value_type(),
928 const allocator_type& __a = allocator_type())
941 : _Base(_Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()),
943 { std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
944 this->_M_impl._M_start,
945 _M_get_Tp_allocator()); }
947 #if __cplusplus >= 201103L
960 : _Base(__a, __x.
size())
961 { std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
962 this->_M_impl._M_start,
963 _M_get_Tp_allocator()); }
969 if (__x.get_allocator() != __a)
971 std::__uninitialized_move_a(__x.begin(), __x.end(),
972 this->_M_impl._M_start,
973 _M_get_Tp_allocator());
989 deque(initializer_list<value_type> __l,
990 const allocator_type& __a = allocator_type())
1013 #if __cplusplus >= 201103L
1014 template<
typename _InputIterator,
1015 typename = std::_RequireInputIter<_InputIterator>>
1016 deque(_InputIterator __first, _InputIterator __last,
1017 const allocator_type& __a = allocator_type())
1019 { _M_initialize_dispatch(__first, __last, __false_type()); }
1021 template<
typename _InputIterator>
1022 deque(_InputIterator __first, _InputIterator __last,
1023 const allocator_type& __a = allocator_type())
1027 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1028 _M_initialize_dispatch(__first, __last, _Integral());
1038 { _M_destroy_data(
begin(),
end(), _M_get_Tp_allocator()); }
1050 #if __cplusplus >= 201103L
1062 constexpr
bool __always_equal = _Alloc_traits::_S_always_equal();
1064 integral_constant<bool, __always_equal>());
1082 this->
assign(__l.begin(), __l.end());
1098 assign(size_type __n,
const value_type& __val)
1099 { _M_fill_assign(__n, __val); }
1113 #if __cplusplus >= 201103L
1114 template<
typename _InputIterator,
1115 typename = std::_RequireInputIter<_InputIterator>>
1117 assign(_InputIterator __first, _InputIterator __last)
1118 { _M_assign_dispatch(__first, __last, __false_type()); }
1120 template<
typename _InputIterator>
1122 assign(_InputIterator __first, _InputIterator __last)
1124 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1125 _M_assign_dispatch(__first, __last, _Integral());
1129 #if __cplusplus >= 201103L
1143 { this->
assign(__l.begin(), __l.end()); }
1149 {
return _Base::get_allocator(); }
1158 {
return this->_M_impl._M_start; }
1166 {
return this->_M_impl._M_start; }
1175 {
return this->_M_impl._M_finish; }
1184 {
return this->_M_impl._M_finish; }
1193 {
return reverse_iterator(this->_M_impl._M_finish); }
1200 const_reverse_iterator
1202 {
return const_reverse_iterator(this->_M_impl._M_finish); }
1211 {
return reverse_iterator(this->_M_impl._M_start); }
1218 const_reverse_iterator
1220 {
return const_reverse_iterator(this->_M_impl._M_start); }
1222 #if __cplusplus >= 201103L
1229 {
return this->_M_impl._M_start; }
1238 {
return this->_M_impl._M_finish; }
1245 const_reverse_iterator
1247 {
return const_reverse_iterator(this->_M_impl._M_finish); }
1254 const_reverse_iterator
1256 {
return const_reverse_iterator(this->_M_impl._M_start); }
1263 {
return this->_M_impl._M_finish - this->_M_impl._M_start; }
1270 #if __cplusplus >= 201103L
1283 const size_type __len =
size();
1284 if (__new_size > __len)
1285 _M_default_append(__new_size - __len);
1286 else if (__new_size < __len)
1287 _M_erase_at_end(this->_M_impl._M_start
1288 + difference_type(__new_size));
1303 resize(size_type __new_size,
const value_type& __x)
1305 const size_type __len =
size();
1306 if (__new_size > __len)
1307 insert(this->_M_impl._M_finish, __new_size - __len, __x);
1308 else if (__new_size < __len)
1309 _M_erase_at_end(this->_M_impl._M_start
1310 + difference_type(__new_size));
1325 resize(size_type __new_size, value_type __x = value_type())
1327 const size_type __len =
size();
1328 if (__new_size > __len)
1329 insert(this->_M_impl._M_finish, __new_size - __len, __x);
1330 else if (__new_size < __len)
1331 _M_erase_at_end(this->_M_impl._M_start
1332 + difference_type(__new_size));
1336 #if __cplusplus >= 201103L
1340 { _M_shrink_to_fit(); }
1349 {
return this->_M_impl._M_finish == this->_M_impl._M_start; }
1365 {
return this->_M_impl._M_start[difference_type(__n)]; }
1380 {
return this->_M_impl._M_start[difference_type(__n)]; }
1387 if (__n >= this->
size())
1388 __throw_out_of_range_fmt(__N(
"deque::_M_range_check: __n "
1389 "(which is %zu)>= this->size() "
1410 return (*
this)[__n];
1428 return (*
this)[__n];
1437 {
return *
begin(); }
1445 {
return *
begin(); }
1454 iterator __tmp =
end();
1466 const_iterator __tmp =
end();
1484 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
1486 _Alloc_traits::construct(this->_M_impl,
1487 this->_M_impl._M_start._M_cur - 1,
1489 --this->_M_impl._M_start._M_cur;
1495 #if __cplusplus >= 201103L
1500 template<
typename... _Args>
1502 emplace_front(_Args&&... __args);
1517 if (this->_M_impl._M_finish._M_cur
1518 != this->_M_impl._M_finish._M_last - 1)
1520 _Alloc_traits::construct(this->_M_impl,
1521 this->_M_impl._M_finish._M_cur, __x);
1522 ++this->_M_impl._M_finish._M_cur;
1528 #if __cplusplus >= 201103L
1533 template<
typename... _Args>
1535 emplace_back(_Args&&... __args);
1549 if (this->_M_impl._M_start._M_cur
1550 != this->_M_impl._M_start._M_last - 1)
1552 _Alloc_traits::destroy(this->_M_impl,
1553 this->_M_impl._M_start._M_cur);
1554 ++this->_M_impl._M_start._M_cur;
1571 if (this->_M_impl._M_finish._M_cur
1572 != this->_M_impl._M_finish._M_first)
1574 --this->_M_impl._M_finish._M_cur;
1575 _Alloc_traits::destroy(this->_M_impl,
1576 this->_M_impl._M_finish._M_cur);
1582 #if __cplusplus >= 201103L
1592 template<
typename... _Args>
1594 emplace(const_iterator __position, _Args&&... __args);
1606 insert(const_iterator __position,
const value_type& __x);
1618 insert(iterator __position,
const value_type& __x);
1621 #if __cplusplus >= 201103L
1632 insert(const_iterator __position, value_type&& __x)
1645 insert(const_iterator __p, initializer_list<value_type> __l)
1646 {
return this->
insert(__p, __l.begin(), __l.end()); }
1649 #if __cplusplus >= 201103L
1661 insert(const_iterator __position, size_type __n,
const value_type& __x)
1663 difference_type __offset = __position -
cbegin();
1664 _M_fill_insert(__position._M_const_cast(), __n, __x);
1665 return begin() + __offset;
1678 insert(iterator __position, size_type __n,
const value_type& __x)
1679 { _M_fill_insert(__position, __n, __x); }
1682 #if __cplusplus >= 201103L
1694 template<
typename _InputIterator,
1695 typename = std::_RequireInputIter<_InputIterator>>
1697 insert(const_iterator __position, _InputIterator __first,
1698 _InputIterator __last)
1700 difference_type __offset = __position -
cbegin();
1701 _M_insert_dispatch(__position._M_const_cast(),
1702 __first, __last, __false_type());
1703 return begin() + __offset;
1716 template<
typename _InputIterator>
1718 insert(iterator __position, _InputIterator __first,
1719 _InputIterator __last)
1722 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1723 _M_insert_dispatch(__position, __first, __last, _Integral());
1741 #if __cplusplus >= 201103L
1744 erase(iterator __position)
1746 {
return _M_erase(__position._M_const_cast()); }
1765 #if __cplusplus >= 201103L
1766 erase(const_iterator __first, const_iterator __last)
1768 erase(iterator __first, iterator __last)
1770 {
return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
1783 #if __cplusplus >= 201103L
1784 noexcept(_Alloc_traits::_S_nothrow_swap())
1787 _M_impl._M_swap_data(__x._M_impl);
1788 _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
1789 __x._M_get_Tp_allocator());
1800 { _M_erase_at_end(
begin()); }
1809 template<
typename _Integer>
1811 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1818 template<
typename _InputIterator>
1820 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1823 typedef typename std::iterator_traits<_InputIterator>::
1824 iterator_category _IterCategory;
1840 template<
typename _InputIterator>
1846 template<
typename _ForwardIterator>
1865 #if __cplusplus >= 201103L
1868 _M_default_initialize();
1878 template<
typename _Integer>
1880 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1881 { _M_fill_assign(__n, __val); }
1884 template<
typename _InputIterator>
1886 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1889 typedef typename std::iterator_traits<_InputIterator>::
1890 iterator_category _IterCategory;
1891 _M_assign_aux(__first, __last, _IterCategory());
1895 template<
typename _InputIterator>
1897 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1901 template<
typename _ForwardIterator>
1903 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1909 _ForwardIterator __mid = __first;
1911 std::copy(__first, __mid,
begin());
1915 _M_erase_at_end(std::copy(__first, __last,
begin()));
1921 _M_fill_assign(size_type __n,
const value_type& __val)
1930 _M_erase_at_end(
begin() + difference_type(__n));
1937 #if __cplusplus < 201103L
1942 template<
typename... _Args>
1945 template<
typename... _Args>
1961 template<
typename _Integer>
1963 _M_insert_dispatch(iterator __pos,
1964 _Integer __n, _Integer __x, __true_type)
1965 { _M_fill_insert(__pos, __n, __x); }
1968 template<
typename _InputIterator>
1970 _M_insert_dispatch(iterator __pos,
1971 _InputIterator __first, _InputIterator __last,
1974 typedef typename std::iterator_traits<_InputIterator>::
1975 iterator_category _IterCategory;
1976 _M_range_insert_aux(__pos, __first, __last, _IterCategory());
1980 template<
typename _InputIterator>
1982 _M_range_insert_aux(iterator __pos, _InputIterator __first,
1986 template<
typename _ForwardIterator>
1988 _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
1995 _M_fill_insert(iterator __pos, size_type __n,
const value_type& __x);
1998 #if __cplusplus < 201103L
2000 _M_insert_aux(iterator __pos,
const value_type& __x);
2002 template<
typename... _Args>
2004 _M_insert_aux(iterator __pos, _Args&&... __args);
2009 _M_insert_aux(iterator __pos, size_type __n,
const value_type& __x);
2012 template<
typename _ForwardIterator>
2014 _M_insert_aux(iterator __pos,
2015 _ForwardIterator __first, _ForwardIterator __last,
2022 _M_destroy_data_aux(iterator __first, iterator __last);
2026 template<
typename _Alloc1>
2028 _M_destroy_data(iterator __first, iterator __last,
const _Alloc1&)
2029 { _M_destroy_data_aux(__first, __last); }
2032 _M_destroy_data(iterator __first, iterator __last,
2035 if (!__has_trivial_destructor(value_type))
2036 _M_destroy_data_aux(__first, __last);
2041 _M_erase_at_begin(iterator __pos)
2043 _M_destroy_data(
begin(), __pos, _M_get_Tp_allocator());
2044 _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node);
2045 this->_M_impl._M_start = __pos;
2051 _M_erase_at_end(iterator __pos)
2053 _M_destroy_data(__pos,
end(), _M_get_Tp_allocator());
2054 _M_destroy_nodes(__pos._M_node + 1,
2055 this->_M_impl._M_finish._M_node + 1);
2056 this->_M_impl._M_finish = __pos;
2060 _M_erase(iterator __pos);
2063 _M_erase(iterator __first, iterator __last);
2065 #if __cplusplus >= 201103L
2068 _M_default_append(size_type __n);
2079 const size_type __vacancies = this->_M_impl._M_start._M_cur
2080 - this->_M_impl._M_start._M_first;
2081 if (__n > __vacancies)
2083 return this->_M_impl._M_start - difference_type(__n);
2089 const size_type __vacancies = (this->_M_impl._M_finish._M_last
2090 - this->_M_impl._M_finish._M_cur) - 1;
2091 if (__n > __vacancies)
2093 return this->_M_impl._M_finish + difference_type(__n);
2115 if (__nodes_to_add + 1 > this->_M_impl._M_map_size
2116 - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
2123 if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
2124 - this->_M_impl._M_map))
2132 #if __cplusplus >= 201103L
2136 _M_move_assign1(
deque&& __x, true_type) noexcept
2138 this->_M_impl._M_swap_data(__x._M_impl);
2140 std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
2144 _M_move_assign1(
deque&& __x, false_type)
2146 constexpr
bool __move_storage =
2147 _Alloc_traits::_S_propagate_on_move_assign();
2149 integral_constant<bool, __move_storage>());
2154 template<
typename... _Args>
2156 _M_replace_map(_Args&&... __args)
2159 deque __newobj(std::forward<_Args>(__args)...);
2162 _M_deallocate_node(*
begin()._M_node);
2163 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
2164 this->_M_impl._M_map =
nullptr;
2165 this->_M_impl._M_map_size = 0;
2167 this->_M_impl._M_swap_data(__newobj._M_impl);
2172 _M_move_assign2(
deque&& __x, true_type)
2175 auto __alloc = __x._M_get_Tp_allocator();
2180 _M_get_Tp_allocator() =
std::move(__alloc);
2186 _M_move_assign2(
deque&& __x, false_type)
2188 if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
2192 _M_replace_map(
std::move(__x), __x.get_allocator());
2198 this->
assign(std::__make_move_if_noexcept_iterator(__x.begin()),
2199 std::__make_move_if_noexcept_iterator(__x.end()));
2217 template<
typename _Tp,
typename _Alloc>
2235 template<
typename _Tp,
typename _Alloc>
2237 operator<(const deque<_Tp, _Alloc>& __x,
2240 __y.begin(), __y.end()); }
2243 template<
typename _Tp,
typename _Alloc>
2247 {
return !(__x == __y); }
2250 template<
typename _Tp,
typename _Alloc>
2254 {
return __y < __x; }
2257 template<
typename _Tp,
typename _Alloc>
2259 operator<=(const deque<_Tp, _Alloc>& __x,
2261 {
return !(__y < __x); }
2264 template<
typename _Tp,
typename _Alloc>
2268 {
return !(__x < __y); }
2271 template<
typename _Tp,
typename _Alloc>
2276 #undef _GLIBCXX_DEQUE_BUF_SIZE
2278 _GLIBCXX_END_NAMESPACE_CONTAINER
void swap(_Tp &, _Tp &) noexcept(__and_< is_nothrow_move_constructible< _Tp >, is_nothrow_move_assignable< _Tp >>::value)
Swaps two values.
reverse_iterator rend() noexcept
const_iterator cbegin() const noexcept
deque(deque &&__x)
Deque move constructor.
void resize(size_type __new_size)
Resizes the deque to the specified number of elements.
void _M_range_check(size_type __n) const
Safety check used only from at().
void _M_set_node(_Map_pointer __new_node) noexcept
size_type max_size() const noexcept
reference front() noexcept
Uniform interface to C++98 and C++0x allocators.
reference at(size_type __n)
Provides access to the data contained in the deque.
void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
iterator _M_reserve_elements_at_back(size_type __n)
Memory-handling helpers for the previous internal insert functions.
void assign(initializer_list< value_type > __l)
Assigns an initializer list to a deque.
void _M_push_front_aux(_Args &&...__args)
Helper functions for push_* and pop_*.
const_reverse_iterator rbegin() const noexcept
iterator insert(const_iterator __position, value_type &&__x)
Inserts given rvalue into deque before specified iterator.
bool operator>=(const basic_string< _CharT, _Traits, _Alloc > &__lhs, const basic_string< _CharT, _Traits, _Alloc > &__rhs)
Test if string doesn't precede string.
deque(const deque &__x, const allocator_type &__a)
Copy constructor with alternative allocator.
void _M_fill_initialize(const value_type &__value)
Fills the deque with copies of value.
deque(const deque &__x)
Deque copy constructor.
Forward iterators support a superset of input iterator operations.
void _M_range_initialize(_InputIterator __first, _InputIterator __last, std::input_iterator_tag)
Fills the deque with whatever is in [first,last).
bool empty() const noexcept
size_type size() const noexcept
void assign(size_type __n, const value_type &__val)
Assigns a given value to a deque.
const_reference at(size_type __n) const
Provides access to the data contained in the deque.
void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
Memory-handling helpers for the major map.
deque(size_type __n, const value_type &__value, const allocator_type &__a=allocator_type())
Creates a deque with copies of an exemplar element.
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
deque(initializer_list< value_type > __l, const allocator_type &__a=allocator_type())
Builds a deque from an initializer list.
iterator begin() noexcept
bool equal(_II1 __first1, _II1 __last1, _II2 __first2)
Tests a range for element-wise equality.
const_reference front() const noexcept
const_reverse_iterator crbegin() const noexcept
iterator _M_reserve_elements_at_front(size_type __n)
Memory-handling helpers for the previous internal insert functions.
const_iterator begin() const noexcept
void _M_pop_back_aux()
Helper functions for push_* and pop_*.
_BI2 move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
Moves the range [first,last) into result.
const_iterator cend() const noexcept
static pointer allocate(_Alloc &__a, size_type __n)
Allocate memory.
deque(deque &&__x, const allocator_type &__a)
Move constructor with alternative allocator.
deque & operator=(deque &&__x) noexcept(_Alloc_traits::_S_always_equal())
Deque move assignment operator.
reference operator[](size_type __n) noexcept
Subscript access to the data contained in the deque.
deque(_InputIterator __first, _InputIterator __last, const allocator_type &__a=allocator_type())
Builds a deque from a range.
bool operator>(const basic_string< _CharT, _Traits, _Alloc > &__lhs, const basic_string< _CharT, _Traits, _Alloc > &__rhs)
Test if string follows string.
deque()
Creates a deque with no elements.
deque & operator=(const deque &__x)
Deque assignment operator.
void push_back(const value_type &__x)
Add data to the end of the deque.
void _M_reserve_map_at_front(size_type __nodes_to_add=1)
Memory-handling helpers for the major map.
void _M_reserve_map_at_back(size_type __nodes_to_add=1)
Memory-handling helpers for the major map.
void _M_new_elements_at_front(size_type __new_elements)
Memory-handling helpers for the previous internal insert functions.
void swap(deque &__x) noexcept(_Alloc_traits::_S_nothrow_swap())
Swaps data with another deque.
iterator insert(const_iterator __position, size_type __n, const value_type &__x)
Inserts a number of copies of given data into the deque.
const_iterator end() const noexcept
deque & operator=(initializer_list< value_type > __l)
Assigns an initializer list to a deque.
void _M_push_back_aux(_Args &&...__args)
Helper functions for push_* and pop_*.
void _M_new_elements_at_back(size_type __new_elements)
Memory-handling helpers for the previous internal insert functions.
The standard allocator, as per [20.4].
void resize(size_type __new_size, const value_type &__x)
Resizes the deque to the specified number of elements.
basic_string< _CharT, _Traits, _Alloc > operator+(const basic_string< _CharT, _Traits, _Alloc > &__lhs, const basic_string< _CharT, _Traits, _Alloc > &__rhs)
Concatenate two strings.
void pop_back() noexcept
Removes last element.
iterator erase(const_iterator __first, const_iterator __last)
Remove a range of elements.
allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
reverse_iterator rbegin() noexcept
iterator emplace(const_iterator __position, _Args &&...__args)
Inserts an object in deque before specified iterator.
A standard container using fixed-size memory allocation and constant-time manipulation of elements at...
void _M_initialize_map(size_t)
Layout storage.
deque(const allocator_type &__a)
Creates a deque with no elements.
const_reference back() const noexcept
const_reverse_iterator rend() const noexcept
void pop_front() noexcept
Removes first element.
reference back() noexcept
static size_type max_size(const _Tp_alloc_type &__a) noexcept
The maximum supported allocation size.
Uniform interface to all pointer-like types.
const_reverse_iterator crend() const noexcept
void shrink_to_fit() noexcept
iterator insert(const_iterator __position, const value_type &__x)
Inserts given value into deque before specified iterator.
iterator insert(const_iterator __p, initializer_list< value_type > __l)
Inserts an initializer list into the deque.
const_reference operator[](size_type __n) const noexcept
Subscript access to the data contained in the deque.
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
static void deallocate(_Alloc &__a, pointer __p, size_type __n)
Deallocate memory.
void assign(_InputIterator __first, _InputIterator __last)
Assigns a range to a deque.
void _M_pop_front_aux()
Helper functions for push_* and pop_*.
iterator erase(const_iterator __position)
Remove element at given position.
void push_front(const value_type &__x)
Add data to the front of the deque.
Random-access iterators support a superset of bidirectional iterator operations.
deque(size_type __n, const allocator_type &__a=allocator_type())
Creates a deque with default constructed elements.
iterator insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
Inserts a range into the deque.
ISO C++ entities toplevel namespace is std.
bool lexicographical_compare(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2, _Compare __comp)
Performs dictionary comparison on ranges.
#define _GLIBCXX_DEQUE_BUF_SIZE
This function controls the size of memory nodes.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.