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 #ifndef _DEQUE_H
00062 #define _DEQUE_H 1
00063
00064 #include <bits/concept_check.h>
00065 #include <bits/stl_iterator_base_types.h>
00066 #include <bits/stl_iterator_base_funcs.h>
00067
00068 namespace _GLIBCXX_STD
00069 {
00082 inline size_t
00083 __deque_buf_size(size_t __size)
00084 { return __size < 512 ? size_t(512 / __size) : size_t(1); }
00085
00086
00100 template<typename _Tp, typename _Ref, typename _Ptr>
00101 struct _Deque_iterator
00102 {
00103 typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
00104 typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
00105
00106 static size_t _S_buffer_size()
00107 { return __deque_buf_size(sizeof(_Tp)); }
00108
00109 typedef std::random_access_iterator_tag iterator_category;
00110 typedef _Tp value_type;
00111 typedef _Ptr pointer;
00112 typedef _Ref reference;
00113 typedef size_t size_type;
00114 typedef ptrdiff_t difference_type;
00115 typedef _Tp** _Map_pointer;
00116 typedef _Deque_iterator _Self;
00117
00118 _Tp* _M_cur;
00119 _Tp* _M_first;
00120 _Tp* _M_last;
00121 _Map_pointer _M_node;
00122
00123 _Deque_iterator(_Tp* __x, _Map_pointer __y)
00124 : _M_cur(__x), _M_first(*__y),
00125 _M_last(*__y + _S_buffer_size()), _M_node(__y) {}
00126
00127 _Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
00128
00129 _Deque_iterator(const iterator& __x)
00130 : _M_cur(__x._M_cur), _M_first(__x._M_first),
00131 _M_last(__x._M_last), _M_node(__x._M_node) {}
00132
00133 reference
00134 operator*() const
00135 { return *_M_cur; }
00136
00137 pointer
00138 operator->() const
00139 { return _M_cur; }
00140
00141 _Self&
00142 operator++()
00143 {
00144 ++_M_cur;
00145 if (_M_cur == _M_last)
00146 {
00147 _M_set_node(_M_node + 1);
00148 _M_cur = _M_first;
00149 }
00150 return *this;
00151 }
00152
00153 _Self
00154 operator++(int)
00155 {
00156 _Self __tmp = *this;
00157 ++*this;
00158 return __tmp;
00159 }
00160
00161 _Self&
00162 operator--()
00163 {
00164 if (_M_cur == _M_first)
00165 {
00166 _M_set_node(_M_node - 1);
00167 _M_cur = _M_last;
00168 }
00169 --_M_cur;
00170 return *this;
00171 }
00172
00173 _Self
00174 operator--(int)
00175 {
00176 _Self __tmp = *this;
00177 --*this;
00178 return __tmp;
00179 }
00180
00181 _Self&
00182 operator+=(difference_type __n)
00183 {
00184 const difference_type __offset = __n + (_M_cur - _M_first);
00185 if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
00186 _M_cur += __n;
00187 else
00188 {
00189 const difference_type __node_offset =
00190 __offset > 0 ? __offset / difference_type(_S_buffer_size())
00191 : -difference_type((-__offset - 1)
00192 / _S_buffer_size()) - 1;
00193 _M_set_node(_M_node + __node_offset);
00194 _M_cur = _M_first + (__offset - __node_offset
00195 * difference_type(_S_buffer_size()));
00196 }
00197 return *this;
00198 }
00199
00200 _Self
00201 operator+(difference_type __n) const
00202 {
00203 _Self __tmp = *this;
00204 return __tmp += __n;
00205 }
00206
00207 _Self&
00208 operator-=(difference_type __n)
00209 { return *this += -__n; }
00210
00211 _Self
00212 operator-(difference_type __n) const
00213 {
00214 _Self __tmp = *this;
00215 return __tmp -= __n;
00216 }
00217
00218 reference
00219 operator[](difference_type __n) const
00220 { return *(*this + __n); }
00221
00228 void
00229 _M_set_node(_Map_pointer __new_node)
00230 {
00231 _M_node = __new_node;
00232 _M_first = *__new_node;
00233 _M_last = _M_first + difference_type(_S_buffer_size());
00234 }
00235 };
00236
00237
00238
00239
00240 template<typename _Tp, typename _Ref, typename _Ptr>
00241 inline bool
00242 operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00243 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00244 { return __x._M_cur == __y._M_cur; }
00245
00246 template<typename _Tp, typename _RefL, typename _PtrL,
00247 typename _RefR, typename _PtrR>
00248 inline bool
00249 operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00250 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00251 { return __x._M_cur == __y._M_cur; }
00252
00253 template<typename _Tp, typename _Ref, typename _Ptr>
00254 inline bool
00255 operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00256 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00257 { return !(__x == __y); }
00258
00259 template<typename _Tp, typename _RefL, typename _PtrL,
00260 typename _RefR, typename _PtrR>
00261 inline bool
00262 operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00263 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00264 { return !(__x == __y); }
00265
00266 template<typename _Tp, typename _Ref, typename _Ptr>
00267 inline bool
00268 operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00269 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00270 { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
00271 : (__x._M_node < __y._M_node); }
00272
00273 template<typename _Tp, typename _RefL, typename _PtrL,
00274 typename _RefR, typename _PtrR>
00275 inline bool
00276 operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00277 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00278 { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
00279 : (__x._M_node < __y._M_node); }
00280
00281 template<typename _Tp, typename _Ref, typename _Ptr>
00282 inline bool
00283 operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00284 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00285 { return __y < __x; }
00286
00287 template<typename _Tp, typename _RefL, typename _PtrL,
00288 typename _RefR, typename _PtrR>
00289 inline bool
00290 operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00291 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00292 { return __y < __x; }
00293
00294 template<typename _Tp, typename _Ref, typename _Ptr>
00295 inline bool
00296 operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00297 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00298 { return !(__y < __x); }
00299
00300 template<typename _Tp, typename _RefL, typename _PtrL,
00301 typename _RefR, typename _PtrR>
00302 inline bool
00303 operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00304 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00305 { return !(__y < __x); }
00306
00307 template<typename _Tp, typename _Ref, typename _Ptr>
00308 inline bool
00309 operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00310 const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
00311 { return !(__x < __y); }
00312
00313 template<typename _Tp, typename _RefL, typename _PtrL,
00314 typename _RefR, typename _PtrR>
00315 inline bool
00316 operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00317 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00318 { return !(__x < __y); }
00319
00320
00321
00322
00323
00324 template<typename _Tp, typename _RefL, typename _PtrL,
00325 typename _RefR, typename _PtrR>
00326 inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
00327 operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00328 const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
00329 {
00330 return typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
00331 (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size())
00332 * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
00333 + (__y._M_last - __y._M_cur);
00334 }
00335
00336 template<typename _Tp, typename _Ref, typename _Ptr>
00337 inline _Deque_iterator<_Tp, _Ref, _Ptr>
00338 operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
00339 { return __x + __n; }
00340
00353 template<typename _Tp, typename _Alloc>
00354 class _Deque_base
00355 {
00356 public:
00357 typedef _Alloc allocator_type;
00358
00359 allocator_type
00360 get_allocator() const
00361 { return _M_get_Tp_allocator(); }
00362
00363 typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
00364 typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
00365
00366 _Deque_base(const allocator_type& __a, size_t __num_elements)
00367 : _M_impl(__a)
00368 { _M_initialize_map(__num_elements); }
00369
00370 _Deque_base(const allocator_type& __a)
00371 : _M_impl(__a)
00372 { }
00373
00374 ~_Deque_base();
00375
00376 protected:
00377
00378
00379
00380 typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type;
00381
00382 typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
00383
00384 struct _Deque_impl
00385 : public _Tp_alloc_type
00386 {
00387 _Tp** _M_map;
00388 size_t _M_map_size;
00389 iterator _M_start;
00390 iterator _M_finish;
00391
00392 _Deque_impl(const _Tp_alloc_type& __a)
00393 : _Tp_alloc_type(__a), _M_map(0), _M_map_size(0),
00394 _M_start(), _M_finish()
00395 { }
00396 };
00397
00398 _Tp_alloc_type&
00399 _M_get_Tp_allocator()
00400 { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
00401
00402 const _Tp_alloc_type&
00403 _M_get_Tp_allocator() const
00404 { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
00405
00406 _Map_alloc_type
00407 _M_get_map_allocator() const
00408 { return _M_get_Tp_allocator(); }
00409
00410 _Tp*
00411 _M_allocate_node()
00412 {
00413 return _M_impl._Tp_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));
00414 }
00415
00416 void
00417 _M_deallocate_node(_Tp* __p)
00418 {
00419 _M_impl._Tp_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp)));
00420 }
00421
00422 _Tp**
00423 _M_allocate_map(size_t __n)
00424 { return _M_get_map_allocator().allocate(__n); }
00425
00426 void
00427 _M_deallocate_map(_Tp** __p, size_t __n)
00428 { _M_get_map_allocator().deallocate(__p, __n); }
00429
00430 protected:
00431 void _M_initialize_map(size_t);
00432 void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
00433 void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
00434 enum { _S_initial_map_size = 8 };
00435
00436 _Deque_impl _M_impl;
00437 };
00438
00439 template<typename _Tp, typename _Alloc>
00440 _Deque_base<_Tp, _Alloc>::
00441 ~_Deque_base()
00442 {
00443 if (this->_M_impl._M_map)
00444 {
00445 _M_destroy_nodes(this->_M_impl._M_start._M_node,
00446 this->_M_impl._M_finish._M_node + 1);
00447 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
00448 }
00449 }
00450
00461 template<typename _Tp, typename _Alloc>
00462 void
00463 _Deque_base<_Tp, _Alloc>::
00464 _M_initialize_map(size_t __num_elements)
00465 {
00466 const size_t __num_nodes = (__num_elements/ __deque_buf_size(sizeof(_Tp))
00467 + 1);
00468
00469 this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
00470 size_t(__num_nodes + 2));
00471 this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
00472
00473
00474
00475
00476
00477
00478 _Tp** __nstart = (this->_M_impl._M_map
00479 + (this->_M_impl._M_map_size - __num_nodes) / 2);
00480 _Tp** __nfinish = __nstart + __num_nodes;
00481
00482 try
00483 { _M_create_nodes(__nstart, __nfinish); }
00484 catch(...)
00485 {
00486 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
00487 this->_M_impl._M_map = 0;
00488 this->_M_impl._M_map_size = 0;
00489 __throw_exception_again;
00490 }
00491
00492 this->_M_impl._M_start._M_set_node(__nstart);
00493 this->_M_impl._M_finish._M_set_node(__nfinish - 1);
00494 this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
00495 this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
00496 + __num_elements
00497 % __deque_buf_size(sizeof(_Tp)));
00498 }
00499
00500 template<typename _Tp, typename _Alloc>
00501 void
00502 _Deque_base<_Tp, _Alloc>::
00503 _M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
00504 {
00505 _Tp** __cur;
00506 try
00507 {
00508 for (__cur = __nstart; __cur < __nfinish; ++__cur)
00509 *__cur = this->_M_allocate_node();
00510 }
00511 catch(...)
00512 {
00513 _M_destroy_nodes(__nstart, __cur);
00514 __throw_exception_again;
00515 }
00516 }
00517
00518 template<typename _Tp, typename _Alloc>
00519 void
00520 _Deque_base<_Tp, _Alloc>::
00521 _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
00522 {
00523 for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
00524 _M_deallocate_node(*__n);
00525 }
00526
00611 template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
00612 class deque : protected _Deque_base<_Tp, _Alloc>
00613 {
00614
00615 typedef typename _Alloc::value_type _Alloc_value_type;
00616 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00617 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
00618
00619 typedef _Deque_base<_Tp, _Alloc> _Base;
00620 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
00621
00622 public:
00623 typedef _Tp value_type;
00624 typedef typename _Tp_alloc_type::pointer pointer;
00625 typedef typename _Tp_alloc_type::const_pointer const_pointer;
00626 typedef typename _Tp_alloc_type::reference reference;
00627 typedef typename _Tp_alloc_type::const_reference const_reference;
00628 typedef typename _Base::iterator iterator;
00629 typedef typename _Base::const_iterator const_iterator;
00630 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00631 typedef std::reverse_iterator<iterator> reverse_iterator;
00632 typedef size_t size_type;
00633 typedef ptrdiff_t difference_type;
00634 typedef _Alloc allocator_type;
00635
00636 protected:
00637 typedef pointer* _Map_pointer;
00638
00639 static size_t _S_buffer_size()
00640 { return __deque_buf_size(sizeof(_Tp)); }
00641
00642
00643 using _Base::_M_initialize_map;
00644 using _Base::_M_create_nodes;
00645 using _Base::_M_destroy_nodes;
00646 using _Base::_M_allocate_node;
00647 using _Base::_M_deallocate_node;
00648 using _Base::_M_allocate_map;
00649 using _Base::_M_deallocate_map;
00650 using _Base::_M_get_Tp_allocator;
00651
00657 using _Base::_M_impl;
00658
00659 public:
00660
00661
00665 explicit
00666 deque(const allocator_type& __a = allocator_type())
00667 : _Base(__a, 0) {}
00668
00676 explicit
00677 deque(size_type __n, const value_type& __value = value_type(),
00678 const allocator_type& __a = allocator_type())
00679 : _Base(__a, __n)
00680 { _M_fill_initialize(__value); }
00681
00689 deque(const deque& __x)
00690 : _Base(__x.get_allocator(), __x.size())
00691 { std::__uninitialized_copy_a(__x.begin(), __x.end(),
00692 this->_M_impl._M_start,
00693 _M_get_Tp_allocator()); }
00694
00709 template<typename _InputIterator>
00710 deque(_InputIterator __first, _InputIterator __last,
00711 const allocator_type& __a = allocator_type())
00712 : _Base(__a)
00713 {
00714
00715 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00716 _M_initialize_dispatch(__first, __last, _Integral());
00717 }
00718
00724 ~deque()
00725 { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00726 _M_get_Tp_allocator()); }
00727
00735 deque&
00736 operator=(const deque& __x);
00737
00748 void
00749 assign(size_type __n, const value_type& __val)
00750 { _M_fill_assign(__n, __val); }
00751
00764 template<typename _InputIterator>
00765 void
00766 assign(_InputIterator __first, _InputIterator __last)
00767 {
00768 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00769 _M_assign_dispatch(__first, __last, _Integral());
00770 }
00771
00773 allocator_type
00774 get_allocator() const
00775 { return _Base::get_allocator(); }
00776
00777
00782 iterator
00783 begin()
00784 { return this->_M_impl._M_start; }
00785
00790 const_iterator
00791 begin() const
00792 { return this->_M_impl._M_start; }
00793
00799 iterator
00800 end()
00801 { return this->_M_impl._M_finish; }
00802
00808 const_iterator
00809 end() const
00810 { return this->_M_impl._M_finish; }
00811
00817 reverse_iterator
00818 rbegin()
00819 { return reverse_iterator(this->_M_impl._M_finish); }
00820
00826 const_reverse_iterator
00827 rbegin() const
00828 { return const_reverse_iterator(this->_M_impl._M_finish); }
00829
00835 reverse_iterator
00836 rend() { return reverse_iterator(this->_M_impl._M_start); }
00837
00843 const_reverse_iterator
00844 rend() const
00845 { return const_reverse_iterator(this->_M_impl._M_start); }
00846
00847
00849 size_type
00850 size() const
00851 { return this->_M_impl._M_finish - this->_M_impl._M_start; }
00852
00854 size_type
00855 max_size() const
00856 { return size_type(-1); }
00857
00869 void
00870 resize(size_type __new_size, value_type __x = value_type())
00871 {
00872 const size_type __len = size();
00873 if (__new_size < __len)
00874 erase(this->_M_impl._M_start + __new_size, this->_M_impl._M_finish);
00875 else
00876 insert(this->_M_impl._M_finish, __new_size - __len, __x);
00877 }
00878
00883 bool
00884 empty() const
00885 { return this->_M_impl._M_finish == this->_M_impl._M_start; }
00886
00887
00899 reference
00900 operator[](size_type __n)
00901 { return this->_M_impl._M_start[difference_type(__n)]; }
00902
00914 const_reference
00915 operator[](size_type __n) const
00916 { return this->_M_impl._M_start[difference_type(__n)]; }
00917
00918 protected:
00920 void
00921 _M_range_check(size_type __n) const
00922 {
00923 if (__n >= this->size())
00924 __throw_out_of_range(__N("deque::_M_range_check"));
00925 }
00926
00927 public:
00939 reference
00940 at(size_type __n)
00941 {
00942 _M_range_check(__n);
00943 return (*this)[__n];
00944 }
00945
00957 const_reference
00958 at(size_type __n) const
00959 {
00960 _M_range_check(__n);
00961 return (*this)[__n];
00962 }
00963
00968 reference
00969 front()
00970 { return *begin(); }
00971
00976 const_reference
00977 front() const
00978 { return *begin(); }
00979
00984 reference
00985 back()
00986 {
00987 iterator __tmp = end();
00988 --__tmp;
00989 return *__tmp;
00990 }
00991
00996 const_reference
00997 back() const
00998 {
00999 const_iterator __tmp = end();
01000 --__tmp;
01001 return *__tmp;
01002 }
01003
01004
01014 void
01015 push_front(const value_type& __x)
01016 {
01017 if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
01018 {
01019 this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1, __x);
01020 --this->_M_impl._M_start._M_cur;
01021 }
01022 else
01023 _M_push_front_aux(__x);
01024 }
01025
01035 void
01036 push_back(const value_type& __x)
01037 {
01038 if (this->_M_impl._M_finish._M_cur
01039 != this->_M_impl._M_finish._M_last - 1)
01040 {
01041 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __x);
01042 ++this->_M_impl._M_finish._M_cur;
01043 }
01044 else
01045 _M_push_back_aux(__x);
01046 }
01047
01056 void
01057 pop_front()
01058 {
01059 if (this->_M_impl._M_start._M_cur
01060 != this->_M_impl._M_start._M_last - 1)
01061 {
01062 this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
01063 ++this->_M_impl._M_start._M_cur;
01064 }
01065 else
01066 _M_pop_front_aux();
01067 }
01068
01077 void
01078 pop_back()
01079 {
01080 if (this->_M_impl._M_finish._M_cur
01081 != this->_M_impl._M_finish._M_first)
01082 {
01083 --this->_M_impl._M_finish._M_cur;
01084 this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
01085 }
01086 else
01087 _M_pop_back_aux();
01088 }
01089
01099 iterator
01100 insert(iterator position, const value_type& __x);
01101
01111 void
01112 insert(iterator __position, size_type __n, const value_type& __x)
01113 { _M_fill_insert(__position, __n, __x); }
01114
01125 template<typename _InputIterator>
01126 void
01127 insert(iterator __position, _InputIterator __first,
01128 _InputIterator __last)
01129 {
01130
01131 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
01132 _M_insert_dispatch(__position, __first, __last, _Integral());
01133 }
01134
01148 iterator
01149 erase(iterator __position);
01150
01167 iterator
01168 erase(iterator __first, iterator __last);
01169
01179 void
01180 swap(deque& __x)
01181 {
01182 std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
01183 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
01184 std::swap(this->_M_impl._M_map, __x._M_impl._M_map);
01185 std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size);
01186 }
01187
01194 void clear();
01195
01196 protected:
01197
01198
01199
01200 template<typename _Integer>
01201 void
01202 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
01203 {
01204 _M_initialize_map(__n);
01205 _M_fill_initialize(__x);
01206 }
01207
01208
01209 template<typename _InputIterator>
01210 void
01211 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
01212 __false_type)
01213 {
01214 typedef typename std::iterator_traits<_InputIterator>::
01215 iterator_category _IterCategory;
01216 _M_range_initialize(__first, __last, _IterCategory());
01217 }
01218
01219
01221
01233 template<typename _InputIterator>
01234 void
01235 _M_range_initialize(_InputIterator __first, _InputIterator __last,
01236 std::input_iterator_tag);
01237
01238
01239 template<typename _ForwardIterator>
01240 void
01241 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
01242 std::forward_iterator_tag);
01244
01257 void
01258 _M_fill_initialize(const value_type& __value);
01259
01260
01261
01262
01263
01264 template<typename _Integer>
01265 void
01266 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
01267 {
01268 _M_fill_assign(static_cast<size_type>(__n),
01269 static_cast<value_type>(__val));
01270 }
01271
01272
01273 template<typename _InputIterator>
01274 void
01275 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
01276 __false_type)
01277 {
01278 typedef typename std::iterator_traits<_InputIterator>::
01279 iterator_category _IterCategory;
01280 _M_assign_aux(__first, __last, _IterCategory());
01281 }
01282
01283
01284 template<typename _InputIterator>
01285 void
01286 _M_assign_aux(_InputIterator __first, _InputIterator __last,
01287 std::input_iterator_tag);
01288
01289
01290 template<typename _ForwardIterator>
01291 void
01292 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
01293 std::forward_iterator_tag)
01294 {
01295 const size_type __len = std::distance(__first, __last);
01296 if (__len > size())
01297 {
01298 _ForwardIterator __mid = __first;
01299 std::advance(__mid, size());
01300 std::copy(__first, __mid, begin());
01301 insert(end(), __mid, __last);
01302 }
01303 else
01304 erase(std::copy(__first, __last, begin()), end());
01305 }
01306
01307
01308
01309 void
01310 _M_fill_assign(size_type __n, const value_type& __val)
01311 {
01312 if (__n > size())
01313 {
01314 std::fill(begin(), end(), __val);
01315 insert(end(), __n - size(), __val);
01316 }
01317 else
01318 {
01319 erase(begin() + __n, end());
01320 std::fill(begin(), end(), __val);
01321 }
01322 }
01323
01325
01330 void _M_push_back_aux(const value_type&);
01331 void _M_push_front_aux(const value_type&);
01332 void _M_pop_back_aux();
01333 void _M_pop_front_aux();
01335
01336
01337
01338
01339
01340 template<typename _Integer>
01341 void
01342 _M_insert_dispatch(iterator __pos,
01343 _Integer __n, _Integer __x, __true_type)
01344 {
01345 _M_fill_insert(__pos, static_cast<size_type>(__n),
01346 static_cast<value_type>(__x));
01347 }
01348
01349
01350 template<typename _InputIterator>
01351 void
01352 _M_insert_dispatch(iterator __pos,
01353 _InputIterator __first, _InputIterator __last,
01354 __false_type)
01355 {
01356 typedef typename std::iterator_traits<_InputIterator>::
01357 iterator_category _IterCategory;
01358 _M_range_insert_aux(__pos, __first, __last, _IterCategory());
01359 }
01360
01361
01362 template<typename _InputIterator>
01363 void
01364 _M_range_insert_aux(iterator __pos, _InputIterator __first,
01365 _InputIterator __last, std::input_iterator_tag);
01366
01367
01368 template<typename _ForwardIterator>
01369 void
01370 _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
01371 _ForwardIterator __last, std::forward_iterator_tag);
01372
01373
01374
01375
01376 void
01377 _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
01378
01379
01380 iterator
01381 _M_insert_aux(iterator __pos, const value_type& __x);
01382
01383
01384 void
01385 _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
01386
01387
01388 template<typename _ForwardIterator>
01389 void
01390 _M_insert_aux(iterator __pos,
01391 _ForwardIterator __first, _ForwardIterator __last,
01392 size_type __n);
01393
01395
01401 iterator
01402 _M_reserve_elements_at_front(size_type __n)
01403 {
01404 const size_type __vacancies = this->_M_impl._M_start._M_cur
01405 - this->_M_impl._M_start._M_first;
01406 if (__n > __vacancies)
01407 _M_new_elements_at_front(__n - __vacancies);
01408 return this->_M_impl._M_start - difference_type(__n);
01409 }
01410
01411 iterator
01412 _M_reserve_elements_at_back(size_type __n)
01413 {
01414 const size_type __vacancies = (this->_M_impl._M_finish._M_last
01415 - this->_M_impl._M_finish._M_cur) - 1;
01416 if (__n > __vacancies)
01417 _M_new_elements_at_back(__n - __vacancies);
01418 return this->_M_impl._M_finish + difference_type(__n);
01419 }
01420
01421 void
01422 _M_new_elements_at_front(size_type __new_elements);
01423
01424 void
01425 _M_new_elements_at_back(size_type __new_elements);
01427
01428
01430
01439 void
01440 _M_reserve_map_at_back (size_type __nodes_to_add = 1)
01441 {
01442 if (__nodes_to_add + 1 > this->_M_impl._M_map_size
01443 - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
01444 _M_reallocate_map(__nodes_to_add, false);
01445 }
01446
01447 void
01448 _M_reserve_map_at_front (size_type __nodes_to_add = 1)
01449 {
01450 if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
01451 - this->_M_impl._M_map))
01452 _M_reallocate_map(__nodes_to_add, true);
01453 }
01454
01455 void
01456 _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
01458 };
01459
01460
01471 template<typename _Tp, typename _Alloc>
01472 inline bool
01473 operator==(const deque<_Tp, _Alloc>& __x,
01474 const deque<_Tp, _Alloc>& __y)
01475 { return __x.size() == __y.size()
01476 && std::equal(__x.begin(), __x.end(), __y.begin()); }
01477
01489 template<typename _Tp, typename _Alloc>
01490 inline bool
01491 operator<(const deque<_Tp, _Alloc>& __x,
01492 const deque<_Tp, _Alloc>& __y)
01493 { return lexicographical_compare(__x.begin(), __x.end(),
01494 __y.begin(), __y.end()); }
01495
01497 template<typename _Tp, typename _Alloc>
01498 inline bool
01499 operator!=(const deque<_Tp, _Alloc>& __x,
01500 const deque<_Tp, _Alloc>& __y)
01501 { return !(__x == __y); }
01502
01504 template<typename _Tp, typename _Alloc>
01505 inline bool
01506 operator>(const deque<_Tp, _Alloc>& __x,
01507 const deque<_Tp, _Alloc>& __y)
01508 { return __y < __x; }
01509
01511 template<typename _Tp, typename _Alloc>
01512 inline bool
01513 operator<=(const deque<_Tp, _Alloc>& __x,
01514 const deque<_Tp, _Alloc>& __y)
01515 { return !(__y < __x); }
01516
01518 template<typename _Tp, typename _Alloc>
01519 inline bool
01520 operator>=(const deque<_Tp, _Alloc>& __x,
01521 const deque<_Tp, _Alloc>& __y)
01522 { return !(__x < __y); }
01523
01525 template<typename _Tp, typename _Alloc>
01526 inline void
01527 swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y)
01528 { __x.swap(__y); }
01529 }
01530
01531 #endif