00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00061 #include <bits/concept_check.h>
00062 #include <bits/stl_iterator_base_types.h>
00063 #include <bits/stl_iterator_base_funcs.h>
00064
00065 #ifndef __GLIBCPP_INTERNAL_DEQUE_H
00066 #define __GLIBCPP_INTERNAL_DEQUE_H
00067
00068
00069
00070
00071
00072 namespace std
00073 {
00074
00085 inline size_t
00086 __deque_buf_size(size_t __size)
00087 { return __size < 512 ? size_t(512 / __size) : size_t(1); }
00088
00089
00091
00101 template <class _Tp, class _Ref, class _Ptr>
00102 struct _Deque_iterator
00103 {
00104 typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
00105 typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
00106 static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
00107
00108 typedef random_access_iterator_tag iterator_category;
00109 typedef _Tp value_type;
00110 typedef _Ptr pointer;
00111 typedef _Ref reference;
00112 typedef size_t size_type;
00113 typedef ptrdiff_t difference_type;
00114 typedef _Tp** _Map_pointer;
00115 typedef _Deque_iterator _Self;
00116
00117 _Tp* _M_cur;
00118 _Tp* _M_first;
00119 _Tp* _M_last;
00120 _Map_pointer _M_node;
00121
00122 _Deque_iterator(_Tp* __x, _Map_pointer __y)
00123 : _M_cur(__x), _M_first(*__y),
00124 _M_last(*__y + _S_buffer_size()), _M_node(__y) {}
00125 _Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
00126 _Deque_iterator(const iterator& __x)
00127 : _M_cur(__x._M_cur), _M_first(__x._M_first),
00128 _M_last(__x._M_last), _M_node(__x._M_node) {}
00129
00130 reference operator*() const { return *_M_cur; }
00131 pointer operator->() const { return _M_cur; }
00132
00133 _Self& operator++() {
00134 ++_M_cur;
00135 if (_M_cur == _M_last) {
00136 _M_set_node(_M_node + 1);
00137 _M_cur = _M_first;
00138 }
00139 return *this;
00140 }
00141 _Self operator++(int) {
00142 _Self __tmp = *this;
00143 ++*this;
00144 return __tmp;
00145 }
00146
00147 _Self& operator--() {
00148 if (_M_cur == _M_first) {
00149 _M_set_node(_M_node - 1);
00150 _M_cur = _M_last;
00151 }
00152 --_M_cur;
00153 return *this;
00154 }
00155 _Self operator--(int) {
00156 _Self __tmp = *this;
00157 --*this;
00158 return __tmp;
00159 }
00160
00161 _Self& operator+=(difference_type __n)
00162 {
00163 difference_type __offset = __n + (_M_cur - _M_first);
00164 if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
00165 _M_cur += __n;
00166 else {
00167 difference_type __node_offset =
00168 __offset > 0 ? __offset / difference_type(_S_buffer_size())
00169 : -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
00170 _M_set_node(_M_node + __node_offset);
00171 _M_cur = _M_first +
00172 (__offset - __node_offset * difference_type(_S_buffer_size()));
00173 }
00174 return *this;
00175 }
00176
00177 _Self operator+(difference_type __n) const
00178 {
00179 _Self __tmp = *this;
00180 return __tmp += __n;
00181 }
00182
00183 _Self& operator-=(difference_type __n) { return *this += -__n; }
00184
00185 _Self operator-(difference_type __n) const {
00186 _Self __tmp = *this;
00187 return __tmp -= __n;
00188 }
00189
00190 reference operator[](difference_type __n) const { return *(*this + __n); }
00191
00198 void _M_set_node(_Map_pointer __new_node) {
00199 _M_node = __new_node;
00200 _M_first = *__new_node;
00201 _M_last = _M_first + difference_type(_S_buffer_size());
00202 }
00203 };
00204
00205
00206
00207
00208 template <class _Tp, class _Ref, class _Ptr>
00209 inline bool
00210 operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00211 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00212 {
00213 return __x._M_cur == __y._M_cur;
00214 }
00215
00216 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
00217 inline bool
00218 operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00219 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00220 {
00221 return __x._M_cur == __y._M_cur;
00222 }
00223
00224 template <class _Tp, class _Ref, class _Ptr>
00225 inline bool
00226 operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00227 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00228 {
00229 return !(__x == __y);
00230 }
00231
00232 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
00233 inline bool
00234 operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00235 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00236 {
00237 return !(__x == __y);
00238 }
00239
00240 template <class _Tp, class _Ref, class _Ptr>
00241 inline bool
00242 operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00243 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00244 {
00245 return (__x._M_node == __y._M_node) ?
00246 (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
00247 }
00248
00249 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
00250 inline bool
00251 operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00252 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00253 {
00254 return (__x._M_node == __y._M_node) ?
00255 (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
00256 }
00257
00258 template <class _Tp, class _Ref, class _Ptr>
00259 inline bool
00260 operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00261 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00262 {
00263 return __y < __x;
00264 }
00265
00266 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
00267 inline bool
00268 operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00269 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00270 {
00271 return __y < __x;
00272 }
00273
00274 template <class _Tp, class _Ref, class _Ptr>
00275 inline bool
00276 operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00277 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00278 {
00279 return !(__y < __x);
00280 }
00281
00282 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
00283 inline bool
00284 operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00285 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00286 {
00287 return !(__y < __x);
00288 }
00289
00290 template <class _Tp, class _Ref, class _Ptr>
00291 inline bool
00292 operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00293 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00294 {
00295 return !(__x < __y);
00296 }
00297
00298 template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
00299 inline bool
00300 operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00301 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00302 {
00303 return !(__x < __y);
00304 }
00305
00306
00307
00308
00309
00310 template <typename _Tp, typename _RefL, typename _PtrL,
00311 typename _RefR, typename _PtrR>
00312 inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
00313 operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00314 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00315 {
00316 return _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
00317 (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size()) *
00318 (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first) +
00319 (__y._M_last - __y._M_cur);
00320 }
00321
00322 template <class _Tp, class _Ref, class _Ptr>
00323 inline _Deque_iterator<_Tp, _Ref, _Ptr>
00324 operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
00325 {
00326 return __x + __n;
00327 }
00328
00329
00331
00341 template <class _Tp, class _Alloc, bool __is_static>
00342 class _Deque_alloc_base
00343 {
00344 public:
00345 typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
00346 allocator_type get_allocator() const { return _M_node_allocator; }
00347
00348 _Deque_alloc_base(const allocator_type& __a)
00349 : _M_node_allocator(__a), _M_map_allocator(__a),
00350 _M_map(0), _M_map_size(0)
00351 {}
00352
00353 protected:
00354 typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type
00355 _Map_allocator_type;
00356
00357 allocator_type _M_node_allocator;
00358 _Map_allocator_type _M_map_allocator;
00359
00360 _Tp* _M_allocate_node() {
00361 return _M_node_allocator.allocate(__deque_buf_size(sizeof(_Tp)));
00362 }
00363 void _M_deallocate_node(_Tp* __p) {
00364 _M_node_allocator.deallocate(__p, __deque_buf_size(sizeof(_Tp)));
00365 }
00366 _Tp** _M_allocate_map(size_t __n)
00367 { return _M_map_allocator.allocate(__n); }
00368 void _M_deallocate_map(_Tp** __p, size_t __n)
00369 { _M_map_allocator.deallocate(__p, __n); }
00370
00371 _Tp** _M_map;
00372 size_t _M_map_size;
00373 };
00374
00376 template <class _Tp, class _Alloc>
00377 class _Deque_alloc_base<_Tp, _Alloc, true>
00378 {
00379 public:
00380 typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
00381 allocator_type get_allocator() const { return allocator_type(); }
00382
00383 _Deque_alloc_base(const allocator_type&) : _M_map(0), _M_map_size(0) {}
00384
00385 protected:
00386 typedef typename _Alloc_traits<_Tp, _Alloc>::_Alloc_type _Node_alloc_type;
00387 typedef typename _Alloc_traits<_Tp*, _Alloc>::_Alloc_type _Map_alloc_type;
00388
00389 _Tp* _M_allocate_node() {
00390 return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));
00391 }
00392 void _M_deallocate_node(_Tp* __p) {
00393 _Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp)));
00394 }
00395 _Tp** _M_allocate_map(size_t __n)
00396 { return _Map_alloc_type::allocate(__n); }
00397 void _M_deallocate_map(_Tp** __p, size_t __n)
00398 { _Map_alloc_type::deallocate(__p, __n); }
00399
00400 _Tp** _M_map;
00401 size_t _M_map_size;
00402 };
00403
00404
00415 template <class _Tp, class _Alloc>
00416 class _Deque_base
00417 : public _Deque_alloc_base<_Tp,_Alloc,
00418 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00419 {
00420 public:
00421 typedef _Deque_alloc_base<_Tp,_Alloc,
00422 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00423 _Base;
00424 typedef typename _Base::allocator_type allocator_type;
00425 typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator;
00426 typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
00427
00428 _Deque_base(const allocator_type& __a, size_t __num_elements)
00429 : _Base(__a), _M_start(), _M_finish()
00430 { _M_initialize_map(__num_elements); }
00431 _Deque_base(const allocator_type& __a)
00432 : _Base(__a), _M_start(), _M_finish() {}
00433 ~_Deque_base();
00434
00435 protected:
00436 void _M_initialize_map(size_t);
00437 void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
00438 void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
00439 enum { _S_initial_map_size = 8 };
00440
00441 protected:
00442 iterator _M_start;
00443 iterator _M_finish;
00444 };
00445
00446
00447 template <class _Tp, class _Alloc>
00448 _Deque_base<_Tp,_Alloc>::~_Deque_base()
00449 {
00450 if (_M_map) {
00451 _M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1);
00452 _M_deallocate_map(_M_map, _M_map_size);
00453 }
00454 }
00455
00465 template <class _Tp, class _Alloc>
00466 void
00467 _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
00468 {
00469 size_t __num_nodes =
00470 __num_elements / __deque_buf_size(sizeof(_Tp)) + 1;
00471
00472 _M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2);
00473 _M_map = _M_allocate_map(_M_map_size);
00474
00475 _Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2;
00476 _Tp** __nfinish = __nstart + __num_nodes;
00477
00478 try
00479 { _M_create_nodes(__nstart, __nfinish); }
00480 catch(...)
00481 {
00482 _M_deallocate_map(_M_map, _M_map_size);
00483 _M_map = 0;
00484 _M_map_size = 0;
00485 __throw_exception_again;
00486 }
00487
00488 _M_start._M_set_node(__nstart);
00489 _M_finish._M_set_node(__nfinish - 1);
00490 _M_start._M_cur = _M_start._M_first;
00491 _M_finish._M_cur = _M_finish._M_first +
00492 __num_elements % __deque_buf_size(sizeof(_Tp));
00493 }
00494
00495 template <class _Tp, class _Alloc>
00496 void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
00497 {
00498 _Tp** __cur;
00499 try {
00500 for (__cur = __nstart; __cur < __nfinish; ++__cur)
00501 *__cur = _M_allocate_node();
00502 }
00503 catch(...)
00504 {
00505 _M_destroy_nodes(__nstart, __cur);
00506 __throw_exception_again;
00507 }
00508 }
00509
00510 template <class _Tp, class _Alloc>
00511 void
00512 _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
00513 {
00514 for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
00515 _M_deallocate_node(*__n);
00516 }
00517
00518
00599 template <class _Tp, class _Alloc = allocator<_Tp> >
00600 class deque : protected _Deque_base<_Tp, _Alloc>
00601 {
00602
00603 __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
00604
00605 typedef _Deque_base<_Tp, _Alloc> _Base;
00606
00607 public:
00608 typedef _Tp value_type;
00609 typedef value_type* pointer;
00610 typedef const value_type* const_pointer;
00611 typedef value_type& reference;
00612 typedef const value_type& const_reference;
00613 typedef size_t size_type;
00614 typedef ptrdiff_t difference_type;
00615
00616 typedef typename _Base::allocator_type allocator_type;
00617 allocator_type get_allocator() const { return _Base::get_allocator(); }
00618
00619 typedef typename _Base::iterator iterator;
00620 typedef typename _Base::const_iterator const_iterator;
00621 typedef reverse_iterator<const_iterator> const_reverse_iterator;
00622 typedef reverse_iterator<iterator> reverse_iterator;
00623
00624 protected:
00625 typedef pointer* _Map_pointer;
00626 static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
00627
00628
00629 using _Base::_M_initialize_map;
00630 using _Base::_M_create_nodes;
00631 using _Base::_M_destroy_nodes;
00632 using _Base::_M_allocate_node;
00633 using _Base::_M_deallocate_node;
00634 using _Base::_M_allocate_map;
00635 using _Base::_M_deallocate_map;
00636
00643 using _Base::_M_map;
00644 using _Base::_M_map_size;
00645 using _Base::_M_start;
00646 using _Base::_M_finish;
00647
00648 public:
00649 iterator begin() { return _M_start; }
00650 iterator end() { return _M_finish; }
00651 const_iterator begin() const { return _M_start; }
00652 const_iterator end() const { return _M_finish; }
00653
00654 reverse_iterator rbegin() { return reverse_iterator(_M_finish); }
00655 reverse_iterator rend() { return reverse_iterator(_M_start); }
00656 const_reverse_iterator rbegin() const
00657 { return const_reverse_iterator(_M_finish); }
00658 const_reverse_iterator rend() const
00659 { return const_reverse_iterator(_M_start); }
00660
00661 reference operator[](size_type __n)
00662 { return _M_start[difference_type(__n)]; }
00663 const_reference operator[](size_type __n) const
00664 { return _M_start[difference_type(__n)]; }
00665
00666 void _M_range_check(size_type __n) const {
00667 if (__n >= this->size())
00668 __throw_out_of_range("deque");
00669 }
00670
00671 reference at(size_type __n)
00672 { _M_range_check(__n); return (*this)[__n]; }
00673 const_reference at(size_type __n) const
00674 { _M_range_check(__n); return (*this)[__n]; }
00675
00676 reference front() { return *_M_start; }
00677 reference back() {
00678 iterator __tmp = _M_finish;
00679 --__tmp;
00680 return *__tmp;
00681 }
00682 const_reference front() const { return *_M_start; }
00683 const_reference back() const {
00684 const_iterator __tmp = _M_finish;
00685 --__tmp;
00686 return *__tmp;
00687 }
00688
00689 size_type size() const { return _M_finish - _M_start; }
00690 size_type max_size() const { return size_type(-1); }
00691 bool empty() const { return _M_finish == _M_start; }
00692
00693 public:
00694 explicit deque(const allocator_type& __a = allocator_type())
00695 : _Base(__a, 0) {}
00696 deque(const deque& __x) : _Base(__x.get_allocator(), __x.size())
00697 { uninitialized_copy(__x.begin(), __x.end(), _M_start); }
00698 deque(size_type __n, const value_type& __value,
00699 const allocator_type& __a = allocator_type()) : _Base(__a, __n)
00700 { _M_fill_initialize(__value); }
00701
00702 explicit
00703 deque(size_type __n)
00704 : _Base(allocator_type(), __n)
00705 { _M_fill_initialize(value_type()); }
00706
00707
00708 template<class _InputIterator>
00709 deque(_InputIterator __first, _InputIterator __last,
00710 const allocator_type& __a = allocator_type())
00711 : _Base(__a)
00712 {
00713 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00714 _M_initialize_dispatch(__first, __last, _Integral());
00715 }
00716
00717 template<class _Integer>
00718 void
00719 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
00720 {
00721 _M_initialize_map(__n);
00722 _M_fill_initialize(__x);
00723 }
00724
00725 template<class _InputIter>
00726 void
00727 _M_initialize_dispatch(_InputIter __first, _InputIter __last, __false_type)
00728 {
00729 typedef typename iterator_traits<_InputIter>::iterator_category _IterCategory;
00730 _M_range_initialize(__first, __last, _IterCategory());
00731 }
00732
00733 ~deque()
00734 { _Destroy(_M_start, _M_finish); }
00735
00736 deque& operator= (const deque& __x) {
00737 const size_type __len = size();
00738 if (&__x != this) {
00739 if (__len >= __x.size())
00740 erase(copy(__x.begin(), __x.end(), _M_start), _M_finish);
00741 else {
00742 const_iterator __mid = __x.begin() + difference_type(__len);
00743 copy(__x.begin(), __mid, _M_start);
00744 insert(_M_finish, __mid, __x.end());
00745 }
00746 }
00747 return *this;
00748 }
00749
00750 void swap(deque& __x) {
00751 std::swap(_M_start, __x._M_start);
00752 std::swap(_M_finish, __x._M_finish);
00753 std::swap(_M_map, __x._M_map);
00754 std::swap(_M_map_size, __x._M_map_size);
00755 }
00756
00757 public:
00758
00759
00760
00761
00762
00763 void _M_fill_assign(size_type __n, const _Tp& __val) {
00764 if (__n > size()) {
00765 fill(begin(), end(), __val);
00766 insert(end(), __n - size(), __val);
00767 }
00768 else {
00769 erase(begin() + __n, end());
00770 fill(begin(), end(), __val);
00771 }
00772 }
00773
00774 void
00775 assign(size_type __n, const _Tp& __val)
00776 { _M_fill_assign(__n, __val); }
00777
00778 template<class _InputIterator>
00779 void
00780 assign(_InputIterator __first, _InputIterator __last)
00781 {
00782 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00783 _M_assign_dispatch(__first, __last, _Integral());
00784 }
00785
00786 private:
00787
00788 template<class _Integer>
00789 void
00790 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
00791 { _M_fill_assign(static_cast<size_type>(__n), static_cast<_Tp>(__val)); }
00792
00793 template<class _InputIterator>
00794 void
00795 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, __false_type)
00796 {
00797 typedef typename iterator_traits<_InputIterator>::iterator_category _IterCategory;
00798 _M_assign_aux(__first, __last, _IterCategory());
00799 }
00800
00801 template <class _InputIterator>
00802 void _M_assign_aux(_InputIterator __first, _InputIterator __last,
00803 input_iterator_tag);
00804
00805 template <class _ForwardIterator>
00806 void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
00807 forward_iterator_tag) {
00808 size_type __len = distance(__first, __last);
00809 if (__len > size()) {
00810 _ForwardIterator __mid = __first;
00811 advance(__mid, size());
00812 copy(__first, __mid, begin());
00813 insert(end(), __mid, __last);
00814 }
00815 else
00816 erase(copy(__first, __last, begin()), end());
00817 }
00818
00819 public:
00820
00821 void
00822 push_back(const value_type& __t)
00823 {
00824 if (_M_finish._M_cur != _M_finish._M_last - 1) {
00825 _Construct(_M_finish._M_cur, __t);
00826 ++_M_finish._M_cur;
00827 }
00828 else
00829 _M_push_back_aux(__t);
00830 }
00831
00832 void
00833 push_back()
00834 {
00835 if (_M_finish._M_cur != _M_finish._M_last - 1) {
00836 _Construct(_M_finish._M_cur);
00837 ++_M_finish._M_cur;
00838 }
00839 else
00840 _M_push_back_aux();
00841 }
00842
00843 void
00844 push_front(const value_type& __t)
00845 {
00846 if (_M_start._M_cur != _M_start._M_first) {
00847 _Construct(_M_start._M_cur - 1, __t);
00848 --_M_start._M_cur;
00849 }
00850 else
00851 _M_push_front_aux(__t);
00852 }
00853
00854 void
00855 push_front()
00856 {
00857 if (_M_start._M_cur != _M_start._M_first) {
00858 _Construct(_M_start._M_cur - 1);
00859 --_M_start._M_cur;
00860 }
00861 else
00862 _M_push_front_aux();
00863 }
00864
00865
00866 void
00867 pop_back()
00868 {
00869 if (_M_finish._M_cur != _M_finish._M_first) {
00870 --_M_finish._M_cur;
00871 _Destroy(_M_finish._M_cur);
00872 }
00873 else
00874 _M_pop_back_aux();
00875 }
00876
00877 void
00878 pop_front()
00879 {
00880 if (_M_start._M_cur != _M_start._M_last - 1) {
00881 _Destroy(_M_start._M_cur);
00882 ++_M_start._M_cur;
00883 }
00884 else
00885 _M_pop_front_aux();
00886 }
00887
00888 public:
00889
00890 iterator
00891 insert(iterator position, const value_type& __x)
00892 {
00893 if (position._M_cur == _M_start._M_cur) {
00894 push_front(__x);
00895 return _M_start;
00896 }
00897 else if (position._M_cur == _M_finish._M_cur) {
00898 push_back(__x);
00899 iterator __tmp = _M_finish;
00900 --__tmp;
00901 return __tmp;
00902 }
00903 else {
00904 return _M_insert_aux(position, __x);
00905 }
00906 }
00907
00908 iterator
00909 insert(iterator __position)
00910 { return insert(__position, value_type()); }
00911
00912 void
00913 insert(iterator __pos, size_type __n, const value_type& __x)
00914 { _M_fill_insert(__pos, __n, __x); }
00915
00916 void
00917 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
00918
00919
00920 template<class _InputIterator>
00921 void
00922 insert(iterator __pos, _InputIterator __first, _InputIterator __last)
00923 {
00924 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00925 _M_insert_dispatch(__pos, __first, __last, _Integral());
00926 }
00927
00928 template<class _Integer>
00929 void
00930 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, __true_type)
00931 { _M_fill_insert(__pos, static_cast<size_type>(__n), static_cast<value_type>(__x)); }
00932
00933 template<class _InputIterator>
00934 void
00935 _M_insert_dispatch(iterator __pos,
00936 _InputIterator __first, _InputIterator __last,
00937 __false_type)
00938 {
00939 typedef typename iterator_traits<_InputIterator>::iterator_category _IterCategory;
00940 insert(__pos, __first, __last, _IterCategory());
00941 }
00942
00943 void resize(size_type __new_size, const value_type& __x) {
00944 const size_type __len = size();
00945 if (__new_size < __len)
00946 erase(_M_start + __new_size, _M_finish);
00947 else
00948 insert(_M_finish, __new_size - __len, __x);
00949 }
00950
00951 void resize(size_type new_size) { resize(new_size, value_type()); }
00952
00953 public:
00954 iterator erase(iterator __pos) {
00955 iterator __next = __pos;
00956 ++__next;
00957 size_type __index = __pos - _M_start;
00958 if (__index < (size() >> 1)) {
00959 copy_backward(_M_start, __pos, __next);
00960 pop_front();
00961 }
00962 else {
00963 copy(__next, _M_finish, __pos);
00964 pop_back();
00965 }
00966 return _M_start + __index;
00967 }
00968
00969 iterator erase(iterator __first, iterator __last);
00970 void clear();
00971
00972 protected:
00973
00974 void _M_fill_initialize(const value_type& __value);
00975
00976 template <class _InputIterator>
00977 void _M_range_initialize(_InputIterator __first, _InputIterator __last,
00978 input_iterator_tag);
00979
00980 template <class _ForwardIterator>
00981 void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
00982 forward_iterator_tag);
00983
00984 protected:
00985
00986 void _M_push_back_aux(const value_type&);
00987 void _M_push_back_aux();
00988 void _M_push_front_aux(const value_type&);
00989 void _M_push_front_aux();
00990 void _M_pop_back_aux();
00991 void _M_pop_front_aux();
00992
00993 protected:
00994
00995 template <class _InputIterator>
00996 void insert(iterator __pos, _InputIterator __first, _InputIterator __last,
00997 input_iterator_tag);
00998
00999 template <class _ForwardIterator>
01000 void insert(iterator __pos,
01001 _ForwardIterator __first, _ForwardIterator __last,
01002 forward_iterator_tag);
01003
01004 iterator _M_insert_aux(iterator __pos, const value_type& __x);
01005 iterator _M_insert_aux(iterator __pos);
01006 void _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
01007
01008 template <class _ForwardIterator>
01009 void _M_insert_aux(iterator __pos,
01010 _ForwardIterator __first, _ForwardIterator __last,
01011 size_type __n);
01012
01013 iterator _M_reserve_elements_at_front(size_type __n) {
01014 size_type __vacancies = _M_start._M_cur - _M_start._M_first;
01015 if (__n > __vacancies)
01016 _M_new_elements_at_front(__n - __vacancies);
01017 return _M_start - difference_type(__n);
01018 }
01019
01020 iterator _M_reserve_elements_at_back(size_type __n) {
01021 size_type __vacancies = (_M_finish._M_last - _M_finish._M_cur) - 1;
01022 if (__n > __vacancies)
01023 _M_new_elements_at_back(__n - __vacancies);
01024 return _M_finish + difference_type(__n);
01025 }
01026
01027 void _M_new_elements_at_front(size_type __new_elements);
01028 void _M_new_elements_at_back(size_type __new_elements);
01029
01030 protected:
01031
01032
01033
01034
01035
01036 void _M_reserve_map_at_back (size_type __nodes_to_add = 1) {
01037 if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map))
01038 _M_reallocate_map(__nodes_to_add, false);
01039 }
01040
01041 void _M_reserve_map_at_front (size_type __nodes_to_add = 1) {
01042 if (__nodes_to_add > size_type(_M_start._M_node - _M_map))
01043 _M_reallocate_map(__nodes_to_add, true);
01044 }
01045
01046 void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
01047 };
01048
01049
01050
01051 template <class _Tp, class _Alloc>
01052 template <class _InputIter>
01053 void deque<_Tp, _Alloc>
01054 ::_M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag)
01055 {
01056 iterator __cur = begin();
01057 for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
01058 *__cur = *__first;
01059 if (__first == __last)
01060 erase(__cur, end());
01061 else
01062 insert(end(), __first, __last);
01063 }
01064
01065 template <class _Tp, class _Alloc>
01066 void deque<_Tp, _Alloc>::_M_fill_insert(iterator __pos,
01067 size_type __n, const value_type& __x)
01068 {
01069 if (__pos._M_cur == _M_start._M_cur) {
01070 iterator __new_start = _M_reserve_elements_at_front(__n);
01071 try {
01072 uninitialized_fill(__new_start, _M_start, __x);
01073 _M_start = __new_start;
01074 }
01075 catch(...)
01076 {
01077 _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
01078 __throw_exception_again;
01079 }
01080 }
01081 else if (__pos._M_cur == _M_finish._M_cur) {
01082 iterator __new_finish = _M_reserve_elements_at_back(__n);
01083 try {
01084 uninitialized_fill(_M_finish, __new_finish, __x);
01085 _M_finish = __new_finish;
01086 }
01087 catch(...)
01088 {
01089 _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
01090 __throw_exception_again;
01091 }
01092 }
01093 else
01094 _M_insert_aux(__pos, __n, __x);
01095 }
01096
01097 template <class _Tp, class _Alloc>
01098 typename deque<_Tp,_Alloc>::iterator
01099 deque<_Tp,_Alloc>::erase(iterator __first, iterator __last)
01100 {
01101 if (__first == _M_start && __last == _M_finish) {
01102 clear();
01103 return _M_finish;
01104 }
01105 else {
01106 difference_type __n = __last - __first;
01107 difference_type __elems_before = __first - _M_start;
01108 if (static_cast<size_type>(__elems_before) < (size() - __n) / 2) {
01109 copy_backward(_M_start, __first, __last);
01110 iterator __new_start = _M_start + __n;
01111 _Destroy(_M_start, __new_start);
01112 _M_destroy_nodes(_M_start._M_node, __new_start._M_node);
01113 _M_start = __new_start;
01114 }
01115 else {
01116 copy(__last, _M_finish, __first);
01117 iterator __new_finish = _M_finish - __n;
01118 _Destroy(__new_finish, _M_finish);
01119 _M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1);
01120 _M_finish = __new_finish;
01121 }
01122 return _M_start + __elems_before;
01123 }
01124 }
01125
01126 template <class _Tp, class _Alloc>
01127 void deque<_Tp,_Alloc>::clear()
01128 {
01129 for (_Map_pointer __node = _M_start._M_node + 1;
01130 __node < _M_finish._M_node;
01131 ++__node) {
01132 _Destroy(*__node, *__node + _S_buffer_size());
01133 _M_deallocate_node(*__node);
01134 }
01135
01136 if (_M_start._M_node != _M_finish._M_node) {
01137 _Destroy(_M_start._M_cur, _M_start._M_last);
01138 _Destroy(_M_finish._M_first, _M_finish._M_cur);
01139 _M_deallocate_node(_M_finish._M_first);
01140 }
01141 else
01142 _Destroy(_M_start._M_cur, _M_finish._M_cur);
01143
01144 _M_finish = _M_start;
01145 }
01146
01159 template <class _Tp, class _Alloc>
01160 void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __value)
01161 {
01162 _Map_pointer __cur;
01163 try {
01164 for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur)
01165 uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value);
01166 uninitialized_fill(_M_finish._M_first, _M_finish._M_cur, __value);
01167 }
01168 catch(...)
01169 {
01170 _Destroy(_M_start, iterator(*__cur, __cur));
01171 __throw_exception_again;
01172 }
01173 }
01174
01187 template <class _Tp, class _Alloc> template <class _InputIterator>
01188 void deque<_Tp,_Alloc>::_M_range_initialize(_InputIterator __first,
01189 _InputIterator __last,
01190 input_iterator_tag)
01191 {
01192 _M_initialize_map(0);
01193 try {
01194 for ( ; __first != __last; ++__first)
01195 push_back(*__first);
01196 }
01197 catch(...)
01198 {
01199 clear();
01200 __throw_exception_again;
01201 }
01202 }
01203
01204 template <class _Tp, class _Alloc> template <class _ForwardIterator>
01205 void deque<_Tp,_Alloc>::_M_range_initialize(_ForwardIterator __first,
01206 _ForwardIterator __last,
01207 forward_iterator_tag)
01208 {
01209 size_type __n = distance(__first, __last);
01210 _M_initialize_map(__n);
01211
01212 _Map_pointer __cur_node;
01213 try {
01214 for (__cur_node = _M_start._M_node;
01215 __cur_node < _M_finish._M_node;
01216 ++__cur_node) {
01217 _ForwardIterator __mid = __first;
01218 advance(__mid, _S_buffer_size());
01219 uninitialized_copy(__first, __mid, *__cur_node);
01220 __first = __mid;
01221 }
01222 uninitialized_copy(__first, __last, _M_finish._M_first);
01223 }
01224 catch(...)
01225 {
01226 _Destroy(_M_start, iterator(*__cur_node, __cur_node));
01227 __throw_exception_again;
01228 }
01229 }
01232
01233 template <class _Tp, class _Alloc>
01234 void
01235 deque<_Tp,_Alloc>::_M_push_back_aux(const value_type& __t)
01236 {
01237 value_type __t_copy = __t;
01238 _M_reserve_map_at_back();
01239 *(_M_finish._M_node + 1) = _M_allocate_node();
01240 try {
01241 _Construct(_M_finish._M_cur, __t_copy);
01242 _M_finish._M_set_node(_M_finish._M_node + 1);
01243 _M_finish._M_cur = _M_finish._M_first;
01244 }
01245 catch(...)
01246 {
01247 _M_deallocate_node(*(_M_finish._M_node + 1));
01248 __throw_exception_again;
01249 }
01250 }
01251
01252
01253 template <class _Tp, class _Alloc>
01254 void
01255 deque<_Tp,_Alloc>::_M_push_back_aux()
01256 {
01257 _M_reserve_map_at_back();
01258 *(_M_finish._M_node + 1) = _M_allocate_node();
01259 try {
01260 _Construct(_M_finish._M_cur);
01261 _M_finish._M_set_node(_M_finish._M_node + 1);
01262 _M_finish._M_cur = _M_finish._M_first;
01263 }
01264 catch(...)
01265 {
01266 _M_deallocate_node(*(_M_finish._M_node + 1));
01267 __throw_exception_again;
01268 }
01269 }
01270
01271
01272 template <class _Tp, class _Alloc>
01273 void
01274 deque<_Tp,_Alloc>::_M_push_front_aux(const value_type& __t)
01275 {
01276 value_type __t_copy = __t;
01277 _M_reserve_map_at_front();
01278 *(_M_start._M_node - 1) = _M_allocate_node();
01279 try {
01280 _M_start._M_set_node(_M_start._M_node - 1);
01281 _M_start._M_cur = _M_start._M_last - 1;
01282 _Construct(_M_start._M_cur, __t_copy);
01283 }
01284 catch(...)
01285 {
01286 ++_M_start;
01287 _M_deallocate_node(*(_M_start._M_node - 1));
01288 __throw_exception_again;
01289 }
01290 }
01291
01292
01293 template <class _Tp, class _Alloc>
01294 void
01295 deque<_Tp,_Alloc>::_M_push_front_aux()
01296 {
01297 _M_reserve_map_at_front();
01298 *(_M_start._M_node - 1) = _M_allocate_node();
01299 try {
01300 _M_start._M_set_node(_M_start._M_node - 1);
01301 _M_start._M_cur = _M_start._M_last - 1;
01302 _Construct(_M_start._M_cur);
01303 }
01304 catch(...)
01305 {
01306 ++_M_start;
01307 _M_deallocate_node(*(_M_start._M_node - 1));
01308 __throw_exception_again;
01309 }
01310 }
01311
01312
01313 template <class _Tp, class _Alloc>
01314 void deque<_Tp,_Alloc>::_M_pop_back_aux()
01315 {
01316 _M_deallocate_node(_M_finish._M_first);
01317 _M_finish._M_set_node(_M_finish._M_node - 1);
01318 _M_finish._M_cur = _M_finish._M_last - 1;
01319 _Destroy(_M_finish._M_cur);
01320 }
01321
01322
01323
01324
01325
01326 template <class _Tp, class _Alloc>
01327 void deque<_Tp,_Alloc>::_M_pop_front_aux()
01328 {
01329 _Destroy(_M_start._M_cur);
01330 _M_deallocate_node(_M_start._M_first);
01331 _M_start._M_set_node(_M_start._M_node + 1);
01332 _M_start._M_cur = _M_start._M_first;
01333 }
01334
01335 template <class _Tp, class _Alloc> template <class _InputIterator>
01336 void deque<_Tp,_Alloc>::insert(iterator __pos,
01337 _InputIterator __first, _InputIterator __last,
01338 input_iterator_tag)
01339 {
01340 copy(__first, __last, inserter(*this, __pos));
01341 }
01342
01343 template <class _Tp, class _Alloc> template <class _ForwardIterator>
01344 void
01345 deque<_Tp,_Alloc>::insert(iterator __pos,
01346 _ForwardIterator __first, _ForwardIterator __last,
01347 forward_iterator_tag) {
01348 size_type __n = distance(__first, __last);
01349 if (__pos._M_cur == _M_start._M_cur) {
01350 iterator __new_start = _M_reserve_elements_at_front(__n);
01351 try {
01352 uninitialized_copy(__first, __last, __new_start);
01353 _M_start = __new_start;
01354 }
01355 catch(...)
01356 {
01357 _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
01358 __throw_exception_again;
01359 }
01360 }
01361 else if (__pos._M_cur == _M_finish._M_cur) {
01362 iterator __new_finish = _M_reserve_elements_at_back(__n);
01363 try {
01364 uninitialized_copy(__first, __last, _M_finish);
01365 _M_finish = __new_finish;
01366 }
01367 catch(...)
01368 {
01369 _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
01370 __throw_exception_again;
01371 }
01372 }
01373 else
01374 _M_insert_aux(__pos, __first, __last, __n);
01375 }
01376
01377 template <class _Tp, class _Alloc>
01378 typename deque<_Tp, _Alloc>::iterator
01379 deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, const value_type& __x)
01380 {
01381 difference_type __index = __pos - _M_start;
01382 value_type __x_copy = __x;
01383 if (static_cast<size_type>(__index) < size() / 2) {
01384 push_front(front());
01385 iterator __front1 = _M_start;
01386 ++__front1;
01387 iterator __front2 = __front1;
01388 ++__front2;
01389 __pos = _M_start + __index;
01390 iterator __pos1 = __pos;
01391 ++__pos1;
01392 copy(__front2, __pos1, __front1);
01393 }
01394 else {
01395 push_back(back());
01396 iterator __back1 = _M_finish;
01397 --__back1;
01398 iterator __back2 = __back1;
01399 --__back2;
01400 __pos = _M_start + __index;
01401 copy_backward(__pos, __back2, __back1);
01402 }
01403 *__pos = __x_copy;
01404 return __pos;
01405 }
01406
01407 template <class _Tp, class _Alloc>
01408 typename deque<_Tp,_Alloc>::iterator
01409 deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos)
01410 {
01411 difference_type __index = __pos - _M_start;
01412 if (static_cast<size_type>(__index) < size() / 2) {
01413 push_front(front());
01414 iterator __front1 = _M_start;
01415 ++__front1;
01416 iterator __front2 = __front1;
01417 ++__front2;
01418 __pos = _M_start + __index;
01419 iterator __pos1 = __pos;
01420 ++__pos1;
01421 copy(__front2, __pos1, __front1);
01422 }
01423 else {
01424 push_back(back());
01425 iterator __back1 = _M_finish;
01426 --__back1;
01427 iterator __back2 = __back1;
01428 --__back2;
01429 __pos = _M_start + __index;
01430 copy_backward(__pos, __back2, __back1);
01431 }
01432 *__pos = value_type();
01433 return __pos;
01434 }
01435
01436 template <class _Tp, class _Alloc>
01437 void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
01438 size_type __n,
01439 const value_type& __x)
01440 {
01441 const difference_type __elems_before = __pos - _M_start;
01442 size_type __length = this->size();
01443 value_type __x_copy = __x;
01444 if (__elems_before < difference_type(__length / 2)) {
01445 iterator __new_start = _M_reserve_elements_at_front(__n);
01446 iterator __old_start = _M_start;
01447 __pos = _M_start + __elems_before;
01448 try {
01449 if (__elems_before >= difference_type(__n)) {
01450 iterator __start_n = _M_start + difference_type(__n);
01451 uninitialized_copy(_M_start, __start_n, __new_start);
01452 _M_start = __new_start;
01453 copy(__start_n, __pos, __old_start);
01454 fill(__pos - difference_type(__n), __pos, __x_copy);
01455 }
01456 else {
01457 __uninitialized_copy_fill(_M_start, __pos, __new_start,
01458 _M_start, __x_copy);
01459 _M_start = __new_start;
01460 fill(__old_start, __pos, __x_copy);
01461 }
01462 }
01463 catch(...)
01464 {
01465 _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
01466 __throw_exception_again;
01467 }
01468 }
01469 else {
01470 iterator __new_finish = _M_reserve_elements_at_back(__n);
01471 iterator __old_finish = _M_finish;
01472 const difference_type __elems_after =
01473 difference_type(__length) - __elems_before;
01474 __pos = _M_finish - __elems_after;
01475 try {
01476 if (__elems_after > difference_type(__n)) {
01477 iterator __finish_n = _M_finish - difference_type(__n);
01478 uninitialized_copy(__finish_n, _M_finish, _M_finish);
01479 _M_finish = __new_finish;
01480 copy_backward(__pos, __finish_n, __old_finish);
01481 fill(__pos, __pos + difference_type(__n), __x_copy);
01482 }
01483 else {
01484 __uninitialized_fill_copy(_M_finish, __pos + difference_type(__n),
01485 __x_copy, __pos, _M_finish);
01486 _M_finish = __new_finish;
01487 fill(__pos, __old_finish, __x_copy);
01488 }
01489 }
01490 catch(...)
01491 {
01492 _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
01493 __throw_exception_again;
01494 }
01495 }
01496 }
01497
01498 template <class _Tp, class _Alloc> template <class _ForwardIterator>
01499 void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
01500 _ForwardIterator __first,
01501 _ForwardIterator __last,
01502 size_type __n)
01503 {
01504 const difference_type __elemsbefore = __pos - _M_start;
01505 size_type __length = size();
01506 if (static_cast<size_type>(__elemsbefore) < __length / 2) {
01507 iterator __new_start = _M_reserve_elements_at_front(__n);
01508 iterator __old_start = _M_start;
01509 __pos = _M_start + __elemsbefore;
01510 try {
01511 if (__elemsbefore >= difference_type(__n)) {
01512 iterator __start_n = _M_start + difference_type(__n);
01513 uninitialized_copy(_M_start, __start_n, __new_start);
01514 _M_start = __new_start;
01515 copy(__start_n, __pos, __old_start);
01516 copy(__first, __last, __pos - difference_type(__n));
01517 }
01518 else {
01519 _ForwardIterator __mid = __first;
01520 advance(__mid, difference_type(__n) - __elemsbefore);
01521 __uninitialized_copy_copy(_M_start, __pos, __first, __mid,
01522 __new_start);
01523 _M_start = __new_start;
01524 copy(__mid, __last, __old_start);
01525 }
01526 }
01527 catch(...)
01528 {
01529 _M_destroy_nodes(__new_start._M_node, _M_start._M_node);
01530 __throw_exception_again;
01531 }
01532 }
01533 else {
01534 iterator __new_finish = _M_reserve_elements_at_back(__n);
01535 iterator __old_finish = _M_finish;
01536 const difference_type __elemsafter =
01537 difference_type(__length) - __elemsbefore;
01538 __pos = _M_finish - __elemsafter;
01539 try {
01540 if (__elemsafter > difference_type(__n)) {
01541 iterator __finish_n = _M_finish - difference_type(__n);
01542 uninitialized_copy(__finish_n, _M_finish, _M_finish);
01543 _M_finish = __new_finish;
01544 copy_backward(__pos, __finish_n, __old_finish);
01545 copy(__first, __last, __pos);
01546 }
01547 else {
01548 _ForwardIterator __mid = __first;
01549 advance(__mid, __elemsafter);
01550 __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
01551 _M_finish = __new_finish;
01552 copy(__first, __mid, __pos);
01553 }
01554 }
01555 catch(...)
01556 {
01557 _M_destroy_nodes(_M_finish._M_node + 1, __new_finish._M_node + 1);
01558 __throw_exception_again;
01559 }
01560 }
01561 }
01562
01563 template <class _Tp, class _Alloc>
01564 void deque<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems)
01565 {
01566 size_type __new_nodes
01567 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
01568 _M_reserve_map_at_front(__new_nodes);
01569 size_type __i;
01570 try {
01571 for (__i = 1; __i <= __new_nodes; ++__i)
01572 *(_M_start._M_node - __i) = _M_allocate_node();
01573 }
01574 catch(...) {
01575 for (size_type __j = 1; __j < __i; ++__j)
01576 _M_deallocate_node(*(_M_start._M_node - __j));
01577 __throw_exception_again;
01578 }
01579 }
01580
01581 template <class _Tp, class _Alloc>
01582 void deque<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems)
01583 {
01584 size_type __new_nodes
01585 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
01586 _M_reserve_map_at_back(__new_nodes);
01587 size_type __i;
01588 try {
01589 for (__i = 1; __i <= __new_nodes; ++__i)
01590 *(_M_finish._M_node + __i) = _M_allocate_node();
01591 }
01592 catch(...) {
01593 for (size_type __j = 1; __j < __i; ++__j)
01594 _M_deallocate_node(*(_M_finish._M_node + __j));
01595 __throw_exception_again;
01596 }
01597 }
01598
01599 template <class _Tp, class _Alloc>
01600 void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add,
01601 bool __add_at_front)
01602 {
01603 size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1;
01604 size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
01605
01606 _Map_pointer __new_nstart;
01607 if (_M_map_size > 2 * __new_num_nodes) {
01608 __new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2
01609 + (__add_at_front ? __nodes_to_add : 0);
01610 if (__new_nstart < _M_start._M_node)
01611 copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
01612 else
01613 copy_backward(_M_start._M_node, _M_finish._M_node + 1,
01614 __new_nstart + __old_num_nodes);
01615 }
01616 else {
01617 size_type __new_map_size =
01618 _M_map_size + max(_M_map_size, __nodes_to_add) + 2;
01619
01620 _Map_pointer __new_map = _M_allocate_map(__new_map_size);
01621 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
01622 + (__add_at_front ? __nodes_to_add : 0);
01623 copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
01624 _M_deallocate_map(_M_map, _M_map_size);
01625
01626 _M_map = __new_map;
01627 _M_map_size = __new_map_size;
01628 }
01629
01630 _M_start._M_set_node(__new_nstart);
01631 _M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
01632 }
01633
01634
01635
01636
01637 template <class _Tp, class _Alloc>
01638 inline bool operator==(const deque<_Tp, _Alloc>& __x,
01639 const deque<_Tp, _Alloc>& __y) {
01640 return __x.size() == __y.size() &&
01641 equal(__x.begin(), __x.end(), __y.begin());
01642 }
01643
01644 template <class _Tp, class _Alloc>
01645 inline bool operator<(const deque<_Tp, _Alloc>& __x,
01646 const deque<_Tp, _Alloc>& __y) {
01647 return lexicographical_compare(__x.begin(), __x.end(),
01648 __y.begin(), __y.end());
01649 }
01650
01651 template <class _Tp, class _Alloc>
01652 inline bool operator!=(const deque<_Tp, _Alloc>& __x,
01653 const deque<_Tp, _Alloc>& __y) {
01654 return !(__x == __y);
01655 }
01656
01657 template <class _Tp, class _Alloc>
01658 inline bool operator>(const deque<_Tp, _Alloc>& __x,
01659 const deque<_Tp, _Alloc>& __y) {
01660 return __y < __x;
01661 }
01662
01663 template <class _Tp, class _Alloc>
01664 inline bool operator<=(const deque<_Tp, _Alloc>& __x,
01665 const deque<_Tp, _Alloc>& __y) {
01666 return !(__y < __x);
01667 }
01668 template <class _Tp, class _Alloc>
01669 inline bool operator>=(const deque<_Tp, _Alloc>& __x,
01670 const deque<_Tp, _Alloc>& __y) {
01671 return !(__x < __y);
01672 }
01673
01674 template <class _Tp, class _Alloc>
01675 inline void swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y) {
01676 __x.swap(__y);
01677 }
01678
01679 }
01680
01681 #endif
01682