58 #define _STL_DEQUE_H 1
65 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
79 {
return __size < 512 ? size_t(512 / __size) : size_t(1); }
93 template<
typename _Tp,
typename _Ref,
typename _Ptr>
99 static size_t _S_buffer_size()
103 typedef _Tp value_type;
104 typedef _Ptr pointer;
105 typedef _Ref reference;
106 typedef size_t size_type;
107 typedef ptrdiff_t difference_type;
108 typedef _Tp** _Map_pointer;
114 _Map_pointer _M_node;
117 : _M_cur(__x), _M_first(*__y),
118 _M_last(*__y + _S_buffer_size()), _M_node(__y) { }
121 : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) { }
124 : _M_cur(__x._M_cur), _M_first(__x._M_first),
125 _M_last(__x._M_last), _M_node(__x._M_node) { }
139 if (_M_cur == _M_last)
141 _M_set_node(_M_node + 1);
158 if (_M_cur == _M_first)
160 _M_set_node(_M_node - 1);
176 operator+=(difference_type __n)
178 const difference_type __offset = __n + (_M_cur - _M_first);
179 if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
183 const difference_type __node_offset =
184 __offset > 0 ? __offset / difference_type(_S_buffer_size())
185 : -difference_type((-__offset - 1)
186 / _S_buffer_size()) - 1;
187 _M_set_node(_M_node + __node_offset);
188 _M_cur = _M_first + (__offset - __node_offset
189 * difference_type(_S_buffer_size()));
195 operator+(difference_type __n)
const
202 operator-=(difference_type __n)
203 {
return *
this += -__n; }
206 operator-(difference_type __n)
const
213 operator[](difference_type __n)
const
214 {
return *(*
this + __n); }
224 _M_node = __new_node;
225 _M_first = *__new_node;
226 _M_last = _M_first + difference_type(_S_buffer_size());
233 template<
typename _Tp,
typename _Ref,
typename _Ptr>
235 operator==(
const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
236 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
237 {
return __x._M_cur == __y._M_cur; }
239 template<
typename _Tp,
typename _RefL,
typename _PtrL,
240 typename _RefR,
typename _PtrR>
242 operator==(
const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
243 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
244 {
return __x._M_cur == __y._M_cur; }
246 template<
typename _Tp,
typename _Ref,
typename _Ptr>
248 operator!=(
const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
249 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
250 {
return !(__x == __y); }
252 template<
typename _Tp,
typename _RefL,
typename _PtrL,
253 typename _RefR,
typename _PtrR>
255 operator!=(
const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
256 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
257 {
return !(__x == __y); }
259 template<
typename _Tp,
typename _Ref,
typename _Ptr>
261 operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
262 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
263 {
return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
264 : (__x._M_node < __y._M_node); }
266 template<
typename _Tp,
typename _RefL,
typename _PtrL,
267 typename _RefR,
typename _PtrR>
269 operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
270 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
271 {
return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
272 : (__x._M_node < __y._M_node); }
274 template<
typename _Tp,
typename _Ref,
typename _Ptr>
276 operator>(
const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
277 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
278 {
return __y < __x; }
280 template<
typename _Tp,
typename _RefL,
typename _PtrL,
281 typename _RefR,
typename _PtrR>
283 operator>(
const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
284 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
285 {
return __y < __x; }
287 template<
typename _Tp,
typename _Ref,
typename _Ptr>
289 operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
290 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
291 {
return !(__y < __x); }
293 template<
typename _Tp,
typename _RefL,
typename _PtrL,
294 typename _RefR,
typename _PtrR>
296 operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
297 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
298 {
return !(__y < __x); }
300 template<
typename _Tp,
typename _Ref,
typename _Ptr>
302 operator>=(
const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
303 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
304 {
return !(__x < __y); }
306 template<
typename _Tp,
typename _RefL,
typename _PtrL,
307 typename _RefR,
typename _PtrR>
309 operator>=(
const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
310 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
311 {
return !(__x < __y); }
317 template<
typename _Tp,
typename _Ref,
typename _Ptr>
318 inline typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type
319 operator-(
const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
320 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
322 return typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type
323 (_Deque_iterator<_Tp, _Ref, _Ptr>::_S_buffer_size())
324 * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
325 + (__y._M_last - __y._M_cur);
328 template<
typename _Tp,
typename _RefL,
typename _PtrL,
329 typename _RefR,
typename _PtrR>
330 inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
331 operator-(
const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
332 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
334 return typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
335 (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size())
336 * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
337 + (__y._M_last - __y._M_cur);
340 template<
typename _Tp,
typename _Ref,
typename _Ptr>
341 inline _Deque_iterator<_Tp, _Ref, _Ptr>
342 operator+(ptrdiff_t __n,
const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
343 {
return __x + __n; }
345 template<
typename _Tp>
347 fill(
const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
348 const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last,
const _Tp& __value);
360 template<
typename _Tp,
typename _Alloc>
364 typedef _Alloc allocator_type;
367 get_allocator()
const
368 {
return allocator_type(_M_get_Tp_allocator()); }
375 { _M_initialize_map(0); }
377 _Deque_base(
const allocator_type& __a,
size_t __num_elements)
379 { _M_initialize_map(__num_elements); }
385 #ifdef __GXX_EXPERIMENTAL_CXX0X__
387 : _M_impl(__x._M_get_Tp_allocator())
389 _M_initialize_map(0);
390 if (__x._M_impl._M_map)
392 std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
393 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
394 std::swap(this->_M_impl._M_map, __x._M_impl._M_map);
395 std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size);
406 typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type;
408 typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
411 :
public _Tp_alloc_type
419 : _Tp_alloc_type(), _M_map(0), _M_map_size(0),
420 _M_start(), _M_finish()
423 _Deque_impl(
const _Tp_alloc_type& __a)
424 : _Tp_alloc_type(__a), _M_map(0), _M_map_size(0),
425 _M_start(), _M_finish()
430 _M_get_Tp_allocator()
431 {
return *
static_cast<_Tp_alloc_type*
>(&this->_M_impl); }
433 const _Tp_alloc_type&
434 _M_get_Tp_allocator()
const
435 {
return *
static_cast<const _Tp_alloc_type*
>(&this->_M_impl); }
438 _M_get_map_allocator()
const
439 {
return _Map_alloc_type(_M_get_Tp_allocator()); }
448 _M_deallocate_node(_Tp* __p)
454 _M_allocate_map(
size_t __n)
455 {
return _M_get_map_allocator().allocate(__n); }
458 _M_deallocate_map(_Tp** __p,
size_t __n)
459 { _M_get_map_allocator().deallocate(__p, __n); }
462 void _M_initialize_map(
size_t);
463 void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
464 void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
465 enum { _S_initial_map_size = 8 };
470 template<
typename _Tp,
typename _Alloc>
474 if (this->_M_impl._M_map)
476 _M_destroy_nodes(this->_M_impl._M_start._M_node,
477 this->_M_impl._M_finish._M_node + 1);
478 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
490 template<
typename _Tp,
typename _Alloc>
492 _Deque_base<_Tp, _Alloc>::
493 _M_initialize_map(
size_t __num_elements)
498 this->_M_impl._M_map_size =
std::max((
size_t) _S_initial_map_size,
499 size_t(__num_nodes + 2));
500 this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
507 _Tp** __nstart = (this->_M_impl._M_map
508 + (this->_M_impl._M_map_size - __num_nodes) / 2);
509 _Tp** __nfinish = __nstart + __num_nodes;
512 { _M_create_nodes(__nstart, __nfinish); }
515 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
516 this->_M_impl._M_map = 0;
517 this->_M_impl._M_map_size = 0;
518 __throw_exception_again;
521 this->_M_impl._M_start._M_set_node(__nstart);
522 this->_M_impl._M_finish._M_set_node(__nfinish - 1);
523 this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
524 this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
529 template<
typename _Tp,
typename _Alloc>
537 for (__cur = __nstart; __cur < __nfinish; ++__cur)
538 *__cur = this->_M_allocate_node();
542 _M_destroy_nodes(__nstart, __cur);
543 __throw_exception_again;
547 template<
typename _Tp,
typename _Alloc>
549 _Deque_base<_Tp, _Alloc>::
550 _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
552 for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
553 _M_deallocate_node(*__n);
637 template<
typename _Tp,
typename _Alloc = std::allocator<_Tp> >
641 typedef typename _Alloc::value_type _Alloc_value_type;
642 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
643 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
646 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
649 typedef _Tp value_type;
650 typedef typename _Tp_alloc_type::pointer pointer;
651 typedef typename _Tp_alloc_type::const_pointer const_pointer;
652 typedef typename _Tp_alloc_type::reference reference;
653 typedef typename _Tp_alloc_type::const_reference const_reference;
658 typedef size_t size_type;
659 typedef ptrdiff_t difference_type;
660 typedef _Alloc allocator_type;
663 typedef pointer* _Map_pointer;
665 static size_t _S_buffer_size()
669 using _Base::_M_initialize_map;
670 using _Base::_M_create_nodes;
671 using _Base::_M_destroy_nodes;
672 using _Base::_M_allocate_node;
673 using _Base::_M_deallocate_node;
674 using _Base::_M_allocate_map;
675 using _Base::_M_deallocate_map;
676 using _Base::_M_get_Tp_allocator;
682 using _Base::_M_impl;
710 deque(size_type __n,
const value_type& __value = value_type(),
711 const allocator_type& __a = allocator_type())
713 { _M_fill_initialize(__value); }
723 :
_Base(__x._M_get_Tp_allocator(), __x.size())
724 { std::__uninitialized_copy_a(__x.
begin(), __x.
end(),
725 this->_M_impl._M_start,
726 _M_get_Tp_allocator()); }
728 #ifdef __GXX_EXPERIMENTAL_CXX0X__
751 const allocator_type& __a = allocator_type())
754 _M_range_initialize(__l.begin(), __l.end(),
774 template<
typename _InputIterator>
775 deque(_InputIterator __first, _InputIterator __last,
776 const allocator_type& __a = allocator_type())
780 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
781 _M_initialize_dispatch(__first, __last, _Integral());
790 { _M_destroy_data(begin(), end(), _M_get_Tp_allocator()); }
800 operator=(
const deque& __x);
802 #ifdef __GXX_EXPERIMENTAL_CXX0X__
833 this->assign(__l.begin(), __l.end());
849 assign(size_type __n,
const value_type& __val)
850 { _M_fill_assign(__n, __val); }
864 template<
typename _InputIterator>
866 assign(_InputIterator __first, _InputIterator __last)
868 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
869 _M_assign_dispatch(__first, __last, _Integral());
872 #ifdef __GXX_EXPERIMENTAL_CXX0X__
886 { this->assign(__l.begin(), __l.end()); }
892 {
return _Base::get_allocator(); }
901 {
return this->_M_impl._M_start; }
909 {
return this->_M_impl._M_start; }
918 {
return this->_M_impl._M_finish; }
927 {
return this->_M_impl._M_finish; }
943 const_reverse_iterator
961 const_reverse_iterator
965 #ifdef __GXX_EXPERIMENTAL_CXX0X__
972 {
return this->_M_impl._M_start; }
981 {
return this->_M_impl._M_finish; }
988 const_reverse_iterator
997 const_reverse_iterator
1006 {
return this->_M_impl._M_finish - this->_M_impl._M_start; }
1011 {
return _M_get_Tp_allocator().max_size(); }
1025 resize(size_type __new_size, value_type __x = value_type())
1027 const size_type __len = size();
1028 if (__new_size < __len)
1029 _M_erase_at_end(this->_M_impl._M_start + difference_type(__new_size));
1031 insert(this->_M_impl._M_finish, __new_size - __len, __x);
1040 {
return this->_M_impl._M_finish == this->_M_impl._M_start; }
1056 {
return this->_M_impl._M_start[difference_type(__n)]; }
1071 {
return this->_M_impl._M_start[difference_type(__n)]; }
1078 if (__n >= this->size())
1079 __throw_out_of_range(__N(
"deque::_M_range_check"));
1097 _M_range_check(__n);
1098 return (*
this)[__n];
1115 _M_range_check(__n);
1116 return (*
this)[__n];
1125 {
return *begin(); }
1133 {
return *begin(); }
1172 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
1174 this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1, __x);
1175 --this->_M_impl._M_start._M_cur;
1178 _M_push_front_aux(__x);
1181 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1183 push_front(value_type&& __x)
1184 { emplace_front(std::move(__x)); }
1186 template<
typename... _Args>
1188 emplace_front(_Args&&... __args);
1203 if (this->_M_impl._M_finish._M_cur
1204 != this->_M_impl._M_finish._M_last - 1)
1206 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __x);
1207 ++this->_M_impl._M_finish._M_cur;
1210 _M_push_back_aux(__x);
1213 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1215 push_back(value_type&& __x)
1216 { emplace_back(std::move(__x)); }
1218 template<
typename... _Args>
1220 emplace_back(_Args&&... __args);
1234 if (this->_M_impl._M_start._M_cur
1235 != this->_M_impl._M_start._M_last - 1)
1237 this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
1238 ++this->_M_impl._M_start._M_cur;
1255 if (this->_M_impl._M_finish._M_cur
1256 != this->_M_impl._M_finish._M_first)
1258 --this->_M_impl._M_finish._M_cur;
1259 this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
1265 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1275 template<
typename... _Args>
1277 emplace(
iterator __position, _Args&&... __args);
1290 insert(
iterator __position,
const value_type& __x);
1292 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1304 {
return emplace(__position,
std::move(__x)); }
1317 { this->insert(__p, __l.begin(), __l.end()); }
1331 { _M_fill_insert(__position, __n, __x); }
1343 template<
typename _InputIterator>
1346 _InputIterator __last)
1349 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1350 _M_insert_dispatch(__position, __first, __last, _Integral());
1398 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1404 std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
1405 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
1406 std::swap(this->_M_impl._M_map, __x._M_impl._M_map);
1407 std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size);
1411 std::__alloc_swap<_Tp_alloc_type>::_S_do_it(_M_get_Tp_allocator(),
1412 __x._M_get_Tp_allocator());
1423 { _M_erase_at_end(begin()); }
1432 template<
typename _Integer>
1434 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1436 _M_initialize_map(static_cast<size_type>(__n));
1437 _M_fill_initialize(__x);
1441 template<
typename _InputIterator>
1443 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1447 iterator_category _IterCategory;
1448 _M_range_initialize(__first, __last, _IterCategory());
1463 template<
typename _InputIterator>
1465 _M_range_initialize(_InputIterator __first, _InputIterator __last,
1469 template<
typename _ForwardIterator>
1471 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
1486 _M_fill_initialize(
const value_type& __value);
1495 template<
typename _Integer>
1497 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1498 { _M_fill_assign(__n, __val); }
1501 template<
typename _InputIterator>
1503 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1507 iterator_category _IterCategory;
1508 _M_assign_aux(__first, __last, _IterCategory());
1512 template<
typename _InputIterator>
1514 _M_assign_aux(_InputIterator __first, _InputIterator __last,
1518 template<
typename _ForwardIterator>
1520 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1526 _ForwardIterator __mid = __first;
1528 std::copy(__first, __mid, begin());
1529 insert(end(), __mid, __last);
1532 _M_erase_at_end(std::copy(__first, __last, begin()));
1538 _M_fill_assign(size_type __n,
const value_type& __val)
1542 std::fill(begin(), end(), __val);
1543 insert(end(), __n - size(), __val);
1547 _M_erase_at_end(begin() + difference_type(__n));
1548 std::fill(begin(), end(), __val);
1554 #ifndef __GXX_EXPERIMENTAL_CXX0X__
1555 void _M_push_back_aux(
const value_type&);
1557 void _M_push_front_aux(
const value_type&);
1559 template<
typename... _Args>
1560 void _M_push_back_aux(_Args&&... __args);
1562 template<
typename... _Args>
1563 void _M_push_front_aux(_Args&&... __args);
1566 void _M_pop_back_aux();
1568 void _M_pop_front_aux();
1578 template<
typename _Integer>
1580 _M_insert_dispatch(iterator __pos,
1581 _Integer __n, _Integer __x, __true_type)
1582 { _M_fill_insert(__pos, __n, __x); }
1585 template<
typename _InputIterator>
1587 _M_insert_dispatch(iterator __pos,
1588 _InputIterator __first, _InputIterator __last,
1592 iterator_category _IterCategory;
1593 _M_range_insert_aux(__pos, __first, __last, _IterCategory());
1597 template<
typename _InputIterator>
1599 _M_range_insert_aux(iterator __pos, _InputIterator __first,
1603 template<
typename _ForwardIterator>
1605 _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
1612 _M_fill_insert(iterator __pos, size_type __n,
const value_type& __x);
1615 #ifndef __GXX_EXPERIMENTAL_CXX0X__
1617 _M_insert_aux(iterator __pos,
const value_type& __x);
1619 template<
typename... _Args>
1621 _M_insert_aux(iterator __pos, _Args&&... __args);
1626 _M_insert_aux(iterator __pos, size_type __n,
const value_type& __x);
1629 template<
typename _ForwardIterator>
1631 _M_insert_aux(iterator __pos,
1632 _ForwardIterator __first, _ForwardIterator __last,
1639 _M_destroy_data_aux(iterator __first, iterator __last);
1643 template<
typename _Alloc1>
1645 _M_destroy_data(iterator __first, iterator __last,
const _Alloc1&)
1646 { _M_destroy_data_aux(__first, __last); }
1649 _M_destroy_data(iterator __first, iterator __last,
1652 if (!__has_trivial_destructor(value_type))
1653 _M_destroy_data_aux(__first, __last);
1658 _M_erase_at_begin(iterator __pos)
1660 _M_destroy_data(begin(), __pos, _M_get_Tp_allocator());
1661 _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node);
1662 this->_M_impl._M_start = __pos;
1668 _M_erase_at_end(iterator __pos)
1670 _M_destroy_data(__pos, end(), _M_get_Tp_allocator());
1671 _M_destroy_nodes(__pos._M_node + 1,
1672 this->_M_impl._M_finish._M_node + 1);
1673 this->_M_impl._M_finish = __pos;
1681 const size_type __vacancies = this->_M_impl._M_start._M_cur
1682 - this->_M_impl._M_start._M_first;
1683 if (__n > __vacancies)
1684 _M_new_elements_at_front(__n - __vacancies);
1685 return this->_M_impl._M_start - difference_type(__n);
1691 const size_type __vacancies = (this->_M_impl._M_finish._M_last
1692 - this->_M_impl._M_finish._M_cur) - 1;
1693 if (__n > __vacancies)
1694 _M_new_elements_at_back(__n - __vacancies);
1695 return this->_M_impl._M_finish + difference_type(__n);
1699 _M_new_elements_at_front(size_type __new_elements);
1702 _M_new_elements_at_back(size_type __new_elements);
1717 if (__nodes_to_add + 1 > this->_M_impl._M_map_size
1718 - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
1719 _M_reallocate_map(__nodes_to_add,
false);
1725 if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
1726 - this->_M_impl._M_map))
1727 _M_reallocate_map(__nodes_to_add,
true);
1731 _M_reallocate_map(size_type __nodes_to_add,
bool __add_at_front);
1746 template<
typename _Tp,
typename _Alloc>
1764 template<
typename _Tp,
typename _Alloc>
1766 operator<(const deque<_Tp, _Alloc>& __x,
1769 __y.begin(), __y.end()); }
1772 template<
typename _Tp,
typename _Alloc>
1776 {
return !(__x == __y); }
1779 template<
typename _Tp,
typename _Alloc>
1783 {
return __y < __x; }
1786 template<
typename _Tp,
typename _Alloc>
1788 operator<=(const deque<_Tp, _Alloc>& __x,
1790 {
return !(__y < __x); }
1793 template<
typename _Tp,
typename _Alloc>
1797 {
return !(__x < __y); }
1800 template<
typename _Tp,
typename _Alloc>
1805 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1806 template<
typename _Tp,
typename _Alloc>
1808 swap(deque<_Tp,_Alloc>&& __x, deque<_Tp,_Alloc>& __y)
1811 template<
typename _Tp,
typename _Alloc>
1813 swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>&& __y)
1817 _GLIBCXX_END_NESTED_NAMESPACE
iterator _M_reserve_elements_at_back(size_type __n)
Memory-handling helpers for the previous internal insert functions.
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
const_reference back() const
size_type max_size() const
void insert(iterator __p, initializer_list< value_type > __l)
Inserts an initializer list into the deque.
const_reverse_iterator crend() const
void insert(iterator __position, _InputIterator __first, _InputIterator __last)
Inserts a range into the deque.
deque()
Default constructor creates no elements.
reference operator[](size_type __n)
Subscript access to the data contained in the deque.
void _M_range_check(size_type __n) const
Safety check used only from at().
void _M_set_node(_Map_pointer __new_node)
bool operator==(const deque< _Tp, _Alloc > &__x, const deque< _Tp, _Alloc > &__y)
Deque equality comparison.
allocator_type get_allocator() const
Get a copy of the memory allocation object.
void _M_reserve_map_at_front(size_type __nodes_to_add=1)
Memory-handling helpers for the major map.
deque(_InputIterator __first, _InputIterator __last, const allocator_type &__a=allocator_type())
Builds a deque from a range.
void resize(size_type __new_size, value_type __x=value_type())
Resizes the deque to the specified number of elements.
deque & operator=(initializer_list< value_type > __l)
Assigns an initializer list to a deque.
deque(const deque &__x)
Deque copy constructor.
deque(initializer_list< value_type > __l, const allocator_type &__a=allocator_type())
Builds a deque from an initializer list.
deque(const allocator_type &__a)
Creates a deque with no elements.
deque(deque &&__x)
Deque move constructor.
void push_back(const value_type &__x)
Add data to the end of the deque.
deque & operator=(deque &&__x)
Deque move assignment operator.
const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
const_reverse_iterator rend() const
void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
deque(size_type __n, const value_type &__value=value_type(), const allocator_type &__a=allocator_type())
Creates a deque with copies of an exemplar element.
iterator insert(iterator __position, value_type &&__x)
Inserts given rvalue into deque before specified iterator.
void push_front(const value_type &__x)
Add data to the front of the deque.
void assign(_InputIterator __first, _InputIterator __last)
Assigns a range to a deque.
const_reference at(size_type __n) const
Provides access to the data contained in the deque.
The "standard" allocator, as per [20.4].Further details: http://gcc.gnu.org/onlinedocs/libstdc++/manu...
void assign(size_type __n, const value_type &__val)
Assigns a given value to a deque.
const_reverse_iterator crbegin() const
const_iterator end() const
_OI move(_II __first, _II __last, _OI __result)
Moves the range [first,last) into result.
void insert(iterator __position, size_type __n, const value_type &__x)
Inserts a number of copies of given data into the deque.
const_reference operator[](size_type __n) const
Subscript access to the data contained in the deque.
bool operator>(const deque< _Tp, _Alloc > &__x, const deque< _Tp, _Alloc > &__y)
Based on operator<.
const_reverse_iterator rbegin() const
const_reference front() const
void swap(deque &&__x)
Swaps data with another deque.
void _M_reserve_map_at_back(size_type __nodes_to_add=1)
Memory-handling helpers for the major map.
void assign(initializer_list< value_type > __l)
Assigns an initializer list to a deque.
A standard container using fixed-size memory allocation and constant-time manipulation of elements at...
size_t __deque_buf_size(size_t __size)
This function controls the size of memory nodes.
void pop_front()
Removes first element.
reference at(size_type __n)
Provides access to the data contained in the deque.
Random-access iterators support a superset of bidirectional iterator operations.
bool lexicographical_compare(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2, _Compare __comp)
Performs "dictionary" comparison on ranges.
bool operator>=(const deque< _Tp, _Alloc > &__x, const deque< _Tp, _Alloc > &__y)
Based on operator<.
const_iterator cbegin() const
bool operator!=(const deque< _Tp, _Alloc > &__x, const deque< _Tp, _Alloc > &__y)
Based on operator==.
iterator _M_reserve_elements_at_front(size_type __n)
Memory-handling helpers for the previous internal insert functions.
reverse_iterator rbegin()
Forward iterators support a superset of input iterator operations.
bool equal(_II1 __first1, _II1 __last1, _II2 __first2)
Tests a range for element-wise equality.
const_iterator cend() const
void pop_back()
Removes last element.
const_iterator begin() const