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
00056
00057
00058
00059
00060 #include <bits/concept_check.h>
00061 #include <bits/stl_iterator_base_types.h>
00062 #include <bits/stl_iterator_base_funcs.h>
00063
00064 #ifndef __SGI_STL_INTERNAL_DEQUE_H
00065 #define __SGI_STL_INTERNAL_DEQUE_H
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101 namespace std
00102 {
00103
00104
00105
00106 inline size_t __deque_buf_size(size_t __size) {
00107 return __size < 512 ? size_t(512 / __size) : size_t(1);
00108 }
00109
00110 template <class _Tp, class _Ref, class _Ptr>
00111 struct _Deque_iterator {
00112 typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
00113 typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
00114 static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
00115
00116 typedef random_access_iterator_tag iterator_category;
00117 typedef _Tp value_type;
00118 typedef _Ptr pointer;
00119 typedef _Ref reference;
00120 typedef size_t size_type;
00121 typedef ptrdiff_t difference_type;
00122 typedef _Tp** _Map_pointer;
00123
00124 typedef _Deque_iterator _Self;
00125
00126 _Tp* _M_cur;
00127 _Tp* _M_first;
00128 _Tp* _M_last;
00129 _Map_pointer _M_node;
00130
00131 _Deque_iterator(_Tp* __x, _Map_pointer __y)
00132 : _M_cur(__x), _M_first(*__y),
00133 _M_last(*__y + _S_buffer_size()), _M_node(__y) {}
00134 _Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
00135 _Deque_iterator(const iterator& __x)
00136 : _M_cur(__x._M_cur), _M_first(__x._M_first),
00137 _M_last(__x._M_last), _M_node(__x._M_node) {}
00138
00139 reference operator*() const { return *_M_cur; }
00140 pointer operator->() const { return _M_cur; }
00141
00142 difference_type operator-(const _Self& __x) const {
00143 return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +
00144 (_M_cur - _M_first) + (__x._M_last - __x._M_cur);
00145 }
00146
00147 _Self& operator++() {
00148 ++_M_cur;
00149 if (_M_cur == _M_last) {
00150 _M_set_node(_M_node + 1);
00151 _M_cur = _M_first;
00152 }
00153 return *this;
00154 }
00155 _Self operator++(int) {
00156 _Self __tmp = *this;
00157 ++*this;
00158 return __tmp;
00159 }
00160
00161 _Self& operator--() {
00162 if (_M_cur == _M_first) {
00163 _M_set_node(_M_node - 1);
00164 _M_cur = _M_last;
00165 }
00166 --_M_cur;
00167 return *this;
00168 }
00169 _Self operator--(int) {
00170 _Self __tmp = *this;
00171 --*this;
00172 return __tmp;
00173 }
00174
00175 _Self& operator+=(difference_type __n)
00176 {
00177 difference_type __offset = __n + (_M_cur - _M_first);
00178 if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
00179 _M_cur += __n;
00180 else {
00181 difference_type __node_offset =
00182 __offset > 0 ? __offset / difference_type(_S_buffer_size())
00183 : -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
00184 _M_set_node(_M_node + __node_offset);
00185 _M_cur = _M_first +
00186 (__offset - __node_offset * difference_type(_S_buffer_size()));
00187 }
00188 return *this;
00189 }
00190
00191 _Self operator+(difference_type __n) const
00192 {
00193 _Self __tmp = *this;
00194 return __tmp += __n;
00195 }
00196
00197 _Self& operator-=(difference_type __n) { return *this += -__n; }
00198
00199 _Self operator-(difference_type __n) const {
00200 _Self __tmp = *this;
00201 return __tmp -= __n;
00202 }
00203
00204 reference operator[](difference_type __n) const { return *(*this + __n); }
00205
00206 bool operator==(const _Self& __x) const { return _M_cur == __x._M_cur; }
00207 bool operator!=(const _Self& __x) const { return !(*this == __x); }
00208 bool operator<(const _Self& __x) const {
00209 return (_M_node == __x._M_node) ?
00210 (_M_cur < __x._M_cur) : (_M_node < __x._M_node);
00211 }
00212 bool operator>(const _Self& __x) const { return __x < *this; }
00213 bool operator<=(const _Self& __x) const { return !(__x < *this); }
00214 bool operator>=(const _Self& __x) const { return !(*this < __x); }
00215
00216 void _M_set_node(_Map_pointer __new_node) {
00217 _M_node = __new_node;
00218 _M_first = *__new_node;
00219 _M_last = _M_first + difference_type(_S_buffer_size());
00220 }
00221 };
00222
00223 template <class _Tp, class _Ref, class _Ptr>
00224 inline _Deque_iterator<_Tp, _Ref, _Ptr>
00225 operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
00226 {
00227 return __x + __n;
00228 }
00229
00230
00231
00232
00233
00234
00235
00236
00237
00238 template <class _Tp, class _Alloc, bool __is_static>
00239 class _Deque_alloc_base {
00240 public:
00241 typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
00242 allocator_type get_allocator() const { return _M_node_allocator; }
00243
00244 _Deque_alloc_base(const allocator_type& __a)
00245 : _M_node_allocator(__a), _M_map_allocator(__a),
00246 _M_map(0), _M_map_size(0)
00247 {}
00248
00249 protected:
00250 typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type
00251 _Map_allocator_type;
00252
00253 allocator_type _M_node_allocator;
00254 _Map_allocator_type _M_map_allocator;
00255
00256 _Tp* _M_allocate_node() {
00257 return _M_node_allocator.allocate(__deque_buf_size(sizeof(_Tp)));
00258 }
00259 void _M_deallocate_node(_Tp* __p) {
00260 _M_node_allocator.deallocate(__p, __deque_buf_size(sizeof(_Tp)));
00261 }
00262 _Tp** _M_allocate_map(size_t __n)
00263 { return _M_map_allocator.allocate(__n); }
00264 void _M_deallocate_map(_Tp** __p, size_t __n)
00265 { _M_map_allocator.deallocate(__p, __n); }
00266
00267 _Tp** _M_map;
00268 size_t _M_map_size;
00269 };
00270
00271
00272 template <class _Tp, class _Alloc>
00273 class _Deque_alloc_base<_Tp, _Alloc, true>
00274 {
00275 public:
00276 typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
00277 allocator_type get_allocator() const { return allocator_type(); }
00278
00279 _Deque_alloc_base(const allocator_type&) : _M_map(0), _M_map_size(0) {}
00280
00281 protected:
00282 typedef typename _Alloc_traits<_Tp, _Alloc>::_Alloc_type _Node_alloc_type;
00283 typedef typename _Alloc_traits<_Tp*, _Alloc>::_Alloc_type _Map_alloc_type;
00284
00285 _Tp* _M_allocate_node() {
00286 return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));
00287 }
00288 void _M_deallocate_node(_Tp* __p) {
00289 _Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp)));
00290 }
00291 _Tp** _M_allocate_map(size_t __n)
00292 { return _Map_alloc_type::allocate(__n); }
00293 void _M_deallocate_map(_Tp** __p, size_t __n)
00294 { _Map_alloc_type::deallocate(__p, __n); }
00295
00296 _Tp** _M_map;
00297 size_t _M_map_size;
00298 };
00299
00300 template <class _Tp, class _Alloc>
00301 class _Deque_base
00302 : public _Deque_alloc_base<_Tp,_Alloc,
00303 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00304 {
00305 public:
00306 typedef _Deque_alloc_base<_Tp,_Alloc,
00307 _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
00308 _Base;
00309 typedef typename _Base::allocator_type allocator_type;
00310 typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator;
00311 typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
00312
00313 _Deque_base(const allocator_type& __a, size_t __num_elements)
00314 : _Base(__a), _M_start(), _M_finish()
00315 { _M_initialize_map(__num_elements); }
00316 _Deque_base(const allocator_type& __a)
00317 : _Base(__a), _M_start(), _M_finish() {}
00318 ~_Deque_base();
00319
00320 protected:
00321 void _M_initialize_map(size_t);
00322 void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
00323 void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
00324 enum { _S_initial_map_size = 8 };
00325
00326 protected:
00327 iterator _M_start;
00328 iterator _M_finish;
00329 };
00330
00331
00332
00333 template <class _Tp, class _Alloc>
00334 _Deque_base<_Tp,_Alloc>::~_Deque_base() {
00335 if (_M_map) {
00336 _M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1);
00337 _M_deallocate_map(_M_map, _M_map_size);
00338 }
00339 }
00340
00341 template <class _Tp, class _Alloc>
00342 void
00343 _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
00344 {
00345 size_t __num_nodes =
00346 __num_elements / __deque_buf_size(sizeof(_Tp)) + 1;
00347
00348 _M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2);
00349 _M_map = _M_allocate_map(_M_map_size);
00350
00351 _Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2;
00352 _Tp** __nfinish = __nstart + __num_nodes;
00353
00354 __STL_TRY {
00355 _M_create_nodes(__nstart, __nfinish);
00356 }
00357 __STL_UNWIND((_M_deallocate_map(_M_map, _M_map_size),
00358 _M_map = 0, _M_map_size = 0));
00359 _M_start._M_set_node(__nstart);
00360 _M_finish._M_set_node(__nfinish - 1);
00361 _M_start._M_cur = _M_start._M_first;
00362 _M_finish._M_cur = _M_finish._M_first +
00363 __num_elements % __deque_buf_size(sizeof(_Tp));
00364 }
00365
00366 template <class _Tp, class _Alloc>
00367 void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
00368 {
00369 _Tp** __cur;
00370 __STL_TRY {
00371 for (__cur = __nstart; __cur < __nfinish; ++__cur)
00372 *__cur = _M_allocate_node();
00373 }
00374 __STL_UNWIND(_M_destroy_nodes(__nstart, __cur));
00375 }
00376
00377 template <class _Tp, class _Alloc>
00378 void
00379 _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
00380 {
00381 for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
00382 _M_deallocate_node(*__n);
00383 }
00384
00385 template <class _Tp, class _Alloc = allocator<_Tp> >
00386 class deque : protected _Deque_base<_Tp, _Alloc> {
00387
00388
00389 __glibcpp_class_requires(_Tp, _SGIAssignableConcept);
00390
00391 typedef _Deque_base<_Tp, _Alloc> _Base;
00392 public:
00393 typedef _Tp value_type;
00394 typedef value_type* pointer;
00395 typedef const value_type* const_pointer;
00396 typedef value_type& reference;
00397 typedef const value_type& const_reference;
00398 typedef size_t size_type;
00399 typedef ptrdiff_t difference_type;
00400
00401 typedef typename _Base::allocator_type allocator_type;
00402 allocator_type get_allocator() const { return _Base::get_allocator(); }
00403
00404 public:
00405 typedef typename _Base::iterator iterator;
00406 typedef typename _Base::const_iterator const_iterator;
00407
00408 typedef reverse_iterator<const_iterator> const_reverse_iterator;
00409 typedef reverse_iterator<iterator> reverse_iterator;
00410
00411 protected:
00412 typedef pointer* _Map_pointer;
00413 static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
00414
00415 protected:
00416 using _Base::_M_initialize_map;
00417 using _Base::_M_create_nodes;
00418 using _Base::_M_destroy_nodes;
00419 using _Base::_M_allocate_node;
00420 using _Base::_M_deallocate_node;
00421 using _Base::_M_allocate_map;
00422 using _Base::_M_deallocate_map;
00423
00424 using _Base::_M_map;
00425 using _Base::_M_map_size;
00426 using _Base::_M_start;
00427 using _Base::_M_finish;
00428
00429 public:
00430 iterator begin() { return _M_start; }
00431 iterator end() { return _M_finish; }
00432 const_iterator begin() const { return _M_start; }
00433 const_iterator end() const { return _M_finish; }
00434
00435 reverse_iterator rbegin() { return reverse_iterator(_M_finish); }
00436 reverse_iterator rend() { return reverse_iterator(_M_start); }
00437 const_reverse_iterator rbegin() const
00438 { return const_reverse_iterator(_M_finish); }
00439 const_reverse_iterator rend() const
00440 { return const_reverse_iterator(_M_start); }
00441
00442 reference operator[](size_type __n)
00443 { return _M_start[difference_type(__n)]; }
00444 const_reference operator[](size_type __n) const
00445 { return _M_start[difference_type(__n)]; }
00446
00447 void _M_range_check(size_type __n) const {
00448 if (__n >= this->size())
00449 __throw_range_error("deque");
00450 }
00451
00452 reference at(size_type __n)
00453 { _M_range_check(__n); return (*this)[__n]; }
00454 const_reference at(size_type __n) const
00455 { _M_range_check(__n); return (*this)[__n]; }
00456
00457 reference front() { return *_M_start; }
00458 reference back() {
00459 iterator __tmp = _M_finish;
00460 --__tmp;
00461 return *__tmp;
00462 }
00463 const_reference front() const { return *_M_start; }
00464 const_reference back() const {
00465 const_iterator __tmp = _M_finish;
00466 --__tmp;
00467 return *__tmp;
00468 }
00469
00470 size_type size() const { return _M_finish - _M_start; }
00471 size_type max_size() const { return size_type(-1); }
00472 bool empty() const { return _M_finish == _M_start; }
00473
00474 public:
00475 explicit deque(const allocator_type& __a = allocator_type())
00476 : _Base(__a, 0) {}
00477 deque(const deque& __x) : _Base(__x.get_allocator(), __x.size())
00478 { uninitialized_copy(__x.begin(), __x.end(), _M_start); }
00479 deque(size_type __n, const value_type& __value,
00480 const allocator_type& __a = allocator_type()) : _Base(__a, __n)
00481 { _M_fill_initialize(__value); }
00482 explicit deque(size_type __n) : _Base(allocator_type(), __n)
00483 { _M_fill_initialize(value_type()); }
00484
00485
00486 template <class _InputIterator>
00487 deque(_InputIterator __first, _InputIterator __last,
00488 const allocator_type& __a = allocator_type()) : _Base(__a) {
00489 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00490 _M_initialize_dispatch(__first, __last, _Integral());
00491 }
00492
00493 template <class _Integer>
00494 void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) {
00495 _M_initialize_map(__n);
00496 _M_fill_initialize(__x);
00497 }
00498
00499 template <class _InputIter>
00500 void _M_initialize_dispatch(_InputIter __first, _InputIter __last,
00501 __false_type) {
00502 _M_range_initialize(__first, __last, __iterator_category(__first));
00503 }
00504
00505 ~deque() { destroy(_M_start, _M_finish); }
00506
00507 deque& operator= (const deque& __x) {
00508 const size_type __len = size();
00509 if (&__x != this) {
00510 if (__len >= __x.size())
00511 erase(copy(__x.begin(), __x.end(), _M_start), _M_finish);
00512 else {
00513 const_iterator __mid = __x.begin() + difference_type(__len);
00514 copy(__x.begin(), __mid, _M_start);
00515 insert(_M_finish, __mid, __x.end());
00516 }
00517 }
00518 return *this;
00519 }
00520
00521 void swap(deque& __x) {
00522 std::swap(_M_start, __x._M_start);
00523 std::swap(_M_finish, __x._M_finish);
00524 std::swap(_M_map, __x._M_map);
00525 std::swap(_M_map_size, __x._M_map_size);
00526 }
00527
00528 public:
00529
00530
00531
00532
00533
00534 void _M_fill_assign(size_type __n, const _Tp& __val) {
00535 if (__n > size()) {
00536 fill(begin(), end(), __val);
00537 insert(end(), __n - size(), __val);
00538 }
00539 else {
00540 erase(begin() + __n, end());
00541 fill(begin(), end(), __val);
00542 }
00543 }
00544
00545 void assign(size_type __n, const _Tp& __val) {
00546 _M_fill_assign(__n, __val);
00547 }
00548
00549 template <class _InputIterator>
00550 void assign(_InputIterator __first, _InputIterator __last) {
00551 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00552 _M_assign_dispatch(__first, __last, _Integral());
00553 }
00554
00555 private:
00556
00557 template <class _Integer>
00558 void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
00559 { _M_fill_assign((size_type) __n, (_Tp) __val); }
00560
00561 template <class _InputIterator>
00562 void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
00563 __false_type) {
00564 _M_assign_aux(__first, __last, __iterator_category(__first));
00565 }
00566
00567 template <class _InputIterator>
00568 void _M_assign_aux(_InputIterator __first, _InputIterator __last,
00569 input_iterator_tag);
00570
00571 template <class _ForwardIterator>
00572 void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
00573 forward_iterator_tag) {
00574 size_type __len = 0;
00575 distance(__first, __last, __len);
00576 if (__len > size()) {
00577 _ForwardIterator __mid = __first;
00578 advance(__mid, size());
00579 copy(__first, __mid, begin());
00580 insert(end(), __mid, __last);
00581 }
00582 else
00583 erase(copy(__first, __last, begin()), end());
00584 }
00585
00586 public:
00587
00588 void push_back(const value_type& __t) {
00589 if (_M_finish._M_cur != _M_finish._M_last - 1) {
00590 construct(_M_finish._M_cur, __t);
00591 ++_M_finish._M_cur;
00592 }
00593 else
00594 _M_push_back_aux(__t);
00595 }
00596
00597 void push_back() {
00598 if (_M_finish._M_cur != _M_finish._M_last - 1) {
00599 construct(_M_finish._M_cur);
00600 ++_M_finish._M_cur;
00601 }
00602 else
00603 _M_push_back_aux();
00604 }
00605
00606 void push_front(const value_type& __t) {
00607 if (_M_start._M_cur != _M_start._M_first) {
00608 construct(_M_start._M_cur - 1, __t);
00609 --_M_start._M_cur;
00610 }
00611 else
00612 _M_push_front_aux(__t);
00613 }
00614
00615 void push_front() {
00616 if (_M_start._M_cur != _M_start._M_first) {
00617 construct(_M_start._M_cur - 1);
00618 --_M_start._M_cur;
00619 }
00620 else
00621 _M_push_front_aux();
00622 }
00623
00624
00625 void pop_back() {
00626 if (_M_finish._M_cur != _M_finish._M_first) {
00627 --_M_finish._M_cur;
00628 destroy(_M_finish._M_cur);
00629 }
00630 else
00631 _M_pop_back_aux();
00632 }
00633
00634 void pop_front() {
00635 if (_M_start._M_cur != _M_start._M_last - 1) {
00636 destroy(_M_start._M_cur);
00637 ++_M_start._M_cur;
00638 }
00639 else
00640 _M_pop_front_aux();
00641 }
00642
00643 public:
00644
00645 iterator insert(iterator position, const value_type& __x) {
00646 if (position._M_cur == _M_start._M_cur) {
00647 push_front(__x);
00648 return _M_start;
00649 }
00650 else if (position._M_cur == _M_finish._M_cur) {
00651 push_back(__x);
00652 iterator __tmp = _M_finish;
00653 --__tmp;
00654 return __tmp;
00655 }
00656 else {
00657 return _M_insert_aux(position, __x);
00658 }
00659 }
00660
00661 iterator insert(iterator __position)
00662 { return insert(__position, value_type()); }
00663
00664 void insert(iterator __pos, size_type __n, const value_type& __x)
00665 { _M_fill_insert(__pos, __n, __x); }
00666
00667 void _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
00668
00669
00670 template <class _InputIterator>
00671 void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
00672 typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00673 _M_insert_dispatch(__pos, __first, __last, _Integral());
00674 }
00675
00676 template <class _Integer>
00677 void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
00678 __true_type) {
00679 _M_fill_insert(__pos, (size_type) __n, (value_type) __x);
00680 }
00681
00682 template <class _InputIterator>
00683 void _M_insert_dispatch(iterator __pos,
00684 _InputIterator __first, _InputIterator __last,
00685 __false_type) {
00686 insert(__pos, __first, __last, __iterator_category(__first));
00687 }
00688
00689 void resize(size_type __new_size, const value_type& __x) {
00690 const size_type __len = size();
00691 if (__new_size < __len)
00692 erase(_M_start + __new_size, _M_finish);
00693 else
00694 insert(_M_finish, __new_size - __len, __x);
00695 }
00696
00697 void resize(size_type new_size) { resize(new_size, value_type()); }
00698
00699 public:
00700 iterator erase(iterator __pos) {
00701 iterator __next = __pos;
00702 ++__next;
00703 size_type __index = __pos - _M_start;
00704 if (__index < (size() >> 1)) {
00705 copy_backward(_M_start, __pos, __next);
00706 pop_front();
00707 }
00708 else {
00709 copy(__next, _M_finish, __pos);
00710 pop_back();
00711 }
00712 return _M_start + __index;
00713 }
00714
00715 iterator erase(iterator __first, iterator __last);
00716 void clear();
00717
00718 protected:
00719
00720 void _M_fill_initialize(const value_type& __value);
00721
00722 template <class _InputIterator>
00723 void _M_range_initialize(_InputIterator __first, _InputIterator __last,
00724 input_iterator_tag);
00725
00726 template <class _ForwardIterator>
00727 void _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
00728 forward_iterator_tag);
00729
00730 protected:
00731
00732 void _M_push_back_aux(const value_type&);
00733 void _M_push_back_aux();
00734 void _M_push_front_aux(const value_type&);
00735 void _M_push_front_aux();
00736 void _M_pop_back_aux();
00737 void _M_pop_front_aux();
00738
00739 protected:
00740
00741 template <class _InputIterator>
00742 void insert(iterator __pos, _InputIterator __first, _InputIterator __last,
00743 input_iterator_tag);
00744
00745 template <class _ForwardIterator>
00746 void insert(iterator __pos,
00747 _ForwardIterator __first, _ForwardIterator __last,
00748 forward_iterator_tag);
00749
00750 iterator _M_insert_aux(iterator __pos, const value_type& __x);
00751 iterator _M_insert_aux(iterator __pos);
00752 void _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
00753
00754 template <class _ForwardIterator>
00755 void _M_insert_aux(iterator __pos,
00756 _ForwardIterator __first, _ForwardIterator __last,
00757 size_type __n);
00758
00759 iterator _M_reserve_elements_at_front(size_type __n) {
00760 size_type __vacancies = _M_start._M_cur - _M_start._M_first;
00761 if (__n > __vacancies)
00762 _M_new_elements_at_front(__n - __vacancies);
00763 return _M_start - difference_type(__n);
00764 }
00765
00766 iterator _M_reserve_elements_at_back(size_type __n) {
00767 size_type __vacancies = (_M_finish._M_last - _M_finish._M_cur) - 1;
00768 if (__n > __vacancies)
00769 _M_new_elements_at_back(__n - __vacancies);
00770 return _M_finish + difference_type(__n);
00771 }
00772
00773 void _M_new_elements_at_front(size_type __new_elements);
00774 void _M_new_elements_at_back(size_type __new_elements);
00775
00776 protected:
00777
00778
00779
00780
00781
00782 void _M_reserve_map_at_back (size_type __nodes_to_add = 1) {
00783 if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map))
00784 _M_reallocate_map(__nodes_to_add, false);
00785 }
00786
00787 void _M_reserve_map_at_front (size_type __nodes_to_add = 1) {
00788 if (__nodes_to_add > size_type(_M_start._M_node - _M_map))
00789 _M_reallocate_map(__nodes_to_add, true);
00790 }
00791
00792 void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
00793 };
00794
00795
00796
00797 template <class _Tp, class _Alloc>
00798 template <class _InputIter>
00799 void deque<_Tp, _Alloc>
00800 ::_M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag)
00801 {
00802 iterator __cur = begin();
00803 for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
00804 *__cur = *__first;
00805 if (__first == __last)
00806 erase(__cur, end());
00807 else
00808 insert(end(), __first, __last);
00809 }
00810
00811 template <class _Tp, class _Alloc>
00812 void deque<_Tp, _Alloc>::_M_fill_insert(iterator __pos,
00813 size_type __n, const value_type& __x)
00814 {
00815 if (__pos._M_cur == _M_start._M_cur) {
00816 iterator __new_start = _M_reserve_elements_at_front(__n);
00817 __STL_TRY {
00818 uninitialized_fill(__new_start, _M_start, __x);
00819 _M_start = __new_start;
00820 }
00821 __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
00822 }
00823 else if (__pos._M_cur == _M_finish._M_cur) {
00824 iterator __new_finish = _M_reserve_elements_at_back(__n);
00825 __STL_TRY {
00826 uninitialized_fill(_M_finish, __new_finish, __x);
00827 _M_finish = __new_finish;
00828 }
00829 __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
00830 __new_finish._M_node + 1));
00831 }
00832 else
00833 _M_insert_aux(__pos, __n, __x);
00834 }
00835
00836 template <class _Tp, class _Alloc>
00837 typename deque<_Tp,_Alloc>::iterator
00838 deque<_Tp,_Alloc>::erase(iterator __first, iterator __last)
00839 {
00840 if (__first == _M_start && __last == _M_finish) {
00841 clear();
00842 return _M_finish;
00843 }
00844 else {
00845 difference_type __n = __last - __first;
00846 difference_type __elems_before = __first - _M_start;
00847 if (static_cast<size_type>(__elems_before) < (size() - __n) / 2) {
00848 copy_backward(_M_start, __first, __last);
00849 iterator __new_start = _M_start + __n;
00850 destroy(_M_start, __new_start);
00851 _M_destroy_nodes(_M_start._M_node, __new_start._M_node);
00852 _M_start = __new_start;
00853 }
00854 else {
00855 copy(__last, _M_finish, __first);
00856 iterator __new_finish = _M_finish - __n;
00857 destroy(__new_finish, _M_finish);
00858 _M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1);
00859 _M_finish = __new_finish;
00860 }
00861 return _M_start + __elems_before;
00862 }
00863 }
00864
00865 template <class _Tp, class _Alloc>
00866 void deque<_Tp,_Alloc>::clear()
00867 {
00868 for (_Map_pointer __node = _M_start._M_node + 1;
00869 __node < _M_finish._M_node;
00870 ++__node) {
00871 destroy(*__node, *__node + _S_buffer_size());
00872 _M_deallocate_node(*__node);
00873 }
00874
00875 if (_M_start._M_node != _M_finish._M_node) {
00876 destroy(_M_start._M_cur, _M_start._M_last);
00877 destroy(_M_finish._M_first, _M_finish._M_cur);
00878 _M_deallocate_node(_M_finish._M_first);
00879 }
00880 else
00881 destroy(_M_start._M_cur, _M_finish._M_cur);
00882
00883 _M_finish = _M_start;
00884 }
00885
00886
00887
00888 template <class _Tp, class _Alloc>
00889 void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __value) {
00890 _Map_pointer __cur;
00891 __STL_TRY {
00892 for (__cur = _M_start._M_node; __cur < _M_finish._M_node; ++__cur)
00893 uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value);
00894 uninitialized_fill(_M_finish._M_first, _M_finish._M_cur, __value);
00895 }
00896 __STL_UNWIND(destroy(_M_start, iterator(*__cur, __cur)));
00897 }
00898
00899 template <class _Tp, class _Alloc> template <class _InputIterator>
00900 void deque<_Tp,_Alloc>::_M_range_initialize(_InputIterator __first,
00901 _InputIterator __last,
00902 input_iterator_tag)
00903 {
00904 _M_initialize_map(0);
00905 __STL_TRY {
00906 for ( ; __first != __last; ++__first)
00907 push_back(*__first);
00908 }
00909 __STL_UNWIND(clear());
00910 }
00911
00912 template <class _Tp, class _Alloc> template <class _ForwardIterator>
00913 void deque<_Tp,_Alloc>::_M_range_initialize(_ForwardIterator __first,
00914 _ForwardIterator __last,
00915 forward_iterator_tag)
00916 {
00917 size_type __n = 0;
00918 distance(__first, __last, __n);
00919 _M_initialize_map(__n);
00920
00921 _Map_pointer __cur_node;
00922 __STL_TRY {
00923 for (__cur_node = _M_start._M_node;
00924 __cur_node < _M_finish._M_node;
00925 ++__cur_node) {
00926 _ForwardIterator __mid = __first;
00927 advance(__mid, _S_buffer_size());
00928 uninitialized_copy(__first, __mid, *__cur_node);
00929 __first = __mid;
00930 }
00931 uninitialized_copy(__first, __last, _M_finish._M_first);
00932 }
00933 __STL_UNWIND(destroy(_M_start, iterator(*__cur_node, __cur_node)));
00934 }
00935
00936
00937 template <class _Tp, class _Alloc>
00938 void deque<_Tp,_Alloc>::_M_push_back_aux(const value_type& __t)
00939 {
00940 value_type __t_copy = __t;
00941 _M_reserve_map_at_back();
00942 *(_M_finish._M_node + 1) = _M_allocate_node();
00943 __STL_TRY {
00944 construct(_M_finish._M_cur, __t_copy);
00945 _M_finish._M_set_node(_M_finish._M_node + 1);
00946 _M_finish._M_cur = _M_finish._M_first;
00947 }
00948 __STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));
00949 }
00950
00951
00952 template <class _Tp, class _Alloc>
00953 void deque<_Tp,_Alloc>::_M_push_back_aux()
00954 {
00955 _M_reserve_map_at_back();
00956 *(_M_finish._M_node + 1) = _M_allocate_node();
00957 __STL_TRY {
00958 construct(_M_finish._M_cur);
00959 _M_finish._M_set_node(_M_finish._M_node + 1);
00960 _M_finish._M_cur = _M_finish._M_first;
00961 }
00962 __STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));
00963 }
00964
00965
00966 template <class _Tp, class _Alloc>
00967 void deque<_Tp,_Alloc>::_M_push_front_aux(const value_type& __t)
00968 {
00969 value_type __t_copy = __t;
00970 _M_reserve_map_at_front();
00971 *(_M_start._M_node - 1) = _M_allocate_node();
00972 __STL_TRY {
00973 _M_start._M_set_node(_M_start._M_node - 1);
00974 _M_start._M_cur = _M_start._M_last - 1;
00975 construct(_M_start._M_cur, __t_copy);
00976 }
00977 __STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1))));
00978 }
00979
00980
00981 template <class _Tp, class _Alloc>
00982 void deque<_Tp,_Alloc>::_M_push_front_aux()
00983 {
00984 _M_reserve_map_at_front();
00985 *(_M_start._M_node - 1) = _M_allocate_node();
00986 __STL_TRY {
00987 _M_start._M_set_node(_M_start._M_node - 1);
00988 _M_start._M_cur = _M_start._M_last - 1;
00989 construct(_M_start._M_cur);
00990 }
00991 __STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1))));
00992 }
00993
00994
00995 template <class _Tp, class _Alloc>
00996 void deque<_Tp,_Alloc>::_M_pop_back_aux()
00997 {
00998 _M_deallocate_node(_M_finish._M_first);
00999 _M_finish._M_set_node(_M_finish._M_node - 1);
01000 _M_finish._M_cur = _M_finish._M_last - 1;
01001 destroy(_M_finish._M_cur);
01002 }
01003
01004
01005
01006
01007
01008 template <class _Tp, class _Alloc>
01009 void deque<_Tp,_Alloc>::_M_pop_front_aux()
01010 {
01011 destroy(_M_start._M_cur);
01012 _M_deallocate_node(_M_start._M_first);
01013 _M_start._M_set_node(_M_start._M_node + 1);
01014 _M_start._M_cur = _M_start._M_first;
01015 }
01016
01017 template <class _Tp, class _Alloc> template <class _InputIterator>
01018 void deque<_Tp,_Alloc>::insert(iterator __pos,
01019 _InputIterator __first, _InputIterator __last,
01020 input_iterator_tag)
01021 {
01022 copy(__first, __last, inserter(*this, __pos));
01023 }
01024
01025 template <class _Tp, class _Alloc> template <class _ForwardIterator>
01026 void
01027 deque<_Tp,_Alloc>::insert(iterator __pos,
01028 _ForwardIterator __first, _ForwardIterator __last,
01029 forward_iterator_tag) {
01030 size_type __n = 0;
01031 distance(__first, __last, __n);
01032 if (__pos._M_cur == _M_start._M_cur) {
01033 iterator __new_start = _M_reserve_elements_at_front(__n);
01034 __STL_TRY {
01035 uninitialized_copy(__first, __last, __new_start);
01036 _M_start = __new_start;
01037 }
01038 __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
01039 }
01040 else if (__pos._M_cur == _M_finish._M_cur) {
01041 iterator __new_finish = _M_reserve_elements_at_back(__n);
01042 __STL_TRY {
01043 uninitialized_copy(__first, __last, _M_finish);
01044 _M_finish = __new_finish;
01045 }
01046 __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
01047 __new_finish._M_node + 1));
01048 }
01049 else
01050 _M_insert_aux(__pos, __first, __last, __n);
01051 }
01052
01053 template <class _Tp, class _Alloc>
01054 typename deque<_Tp, _Alloc>::iterator
01055 deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, const value_type& __x)
01056 {
01057 difference_type __index = __pos - _M_start;
01058 value_type __x_copy = __x;
01059 if (static_cast<size_type>(__index) < size() / 2) {
01060 push_front(front());
01061 iterator __front1 = _M_start;
01062 ++__front1;
01063 iterator __front2 = __front1;
01064 ++__front2;
01065 __pos = _M_start + __index;
01066 iterator __pos1 = __pos;
01067 ++__pos1;
01068 copy(__front2, __pos1, __front1);
01069 }
01070 else {
01071 push_back(back());
01072 iterator __back1 = _M_finish;
01073 --__back1;
01074 iterator __back2 = __back1;
01075 --__back2;
01076 __pos = _M_start + __index;
01077 copy_backward(__pos, __back2, __back1);
01078 }
01079 *__pos = __x_copy;
01080 return __pos;
01081 }
01082
01083 template <class _Tp, class _Alloc>
01084 typename deque<_Tp,_Alloc>::iterator
01085 deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos)
01086 {
01087 difference_type __index = __pos - _M_start;
01088 if (static_cast<size_type>(__index) < size() / 2) {
01089 push_front(front());
01090 iterator __front1 = _M_start;
01091 ++__front1;
01092 iterator __front2 = __front1;
01093 ++__front2;
01094 __pos = _M_start + __index;
01095 iterator __pos1 = __pos;
01096 ++__pos1;
01097 copy(__front2, __pos1, __front1);
01098 }
01099 else {
01100 push_back(back());
01101 iterator __back1 = _M_finish;
01102 --__back1;
01103 iterator __back2 = __back1;
01104 --__back2;
01105 __pos = _M_start + __index;
01106 copy_backward(__pos, __back2, __back1);
01107 }
01108 *__pos = value_type();
01109 return __pos;
01110 }
01111
01112 template <class _Tp, class _Alloc>
01113 void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
01114 size_type __n,
01115 const value_type& __x)
01116 {
01117 const difference_type __elems_before = __pos - _M_start;
01118 size_type __length = this->size();
01119 value_type __x_copy = __x;
01120 if (__elems_before < difference_type(__length / 2)) {
01121 iterator __new_start = _M_reserve_elements_at_front(__n);
01122 iterator __old_start = _M_start;
01123 __pos = _M_start + __elems_before;
01124 __STL_TRY {
01125 if (__elems_before >= difference_type(__n)) {
01126 iterator __start_n = _M_start + difference_type(__n);
01127 uninitialized_copy(_M_start, __start_n, __new_start);
01128 _M_start = __new_start;
01129 copy(__start_n, __pos, __old_start);
01130 fill(__pos - difference_type(__n), __pos, __x_copy);
01131 }
01132 else {
01133 __uninitialized_copy_fill(_M_start, __pos, __new_start,
01134 _M_start, __x_copy);
01135 _M_start = __new_start;
01136 fill(__old_start, __pos, __x_copy);
01137 }
01138 }
01139 __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
01140 }
01141 else {
01142 iterator __new_finish = _M_reserve_elements_at_back(__n);
01143 iterator __old_finish = _M_finish;
01144 const difference_type __elems_after =
01145 difference_type(__length) - __elems_before;
01146 __pos = _M_finish - __elems_after;
01147 __STL_TRY {
01148 if (__elems_after > difference_type(__n)) {
01149 iterator __finish_n = _M_finish - difference_type(__n);
01150 uninitialized_copy(__finish_n, _M_finish, _M_finish);
01151 _M_finish = __new_finish;
01152 copy_backward(__pos, __finish_n, __old_finish);
01153 fill(__pos, __pos + difference_type(__n), __x_copy);
01154 }
01155 else {
01156 __uninitialized_fill_copy(_M_finish, __pos + difference_type(__n),
01157 __x_copy, __pos, _M_finish);
01158 _M_finish = __new_finish;
01159 fill(__pos, __old_finish, __x_copy);
01160 }
01161 }
01162 __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
01163 __new_finish._M_node + 1));
01164 }
01165 }
01166
01167 template <class _Tp, class _Alloc> template <class _ForwardIterator>
01168 void deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos,
01169 _ForwardIterator __first,
01170 _ForwardIterator __last,
01171 size_type __n)
01172 {
01173 const difference_type __elemsbefore = __pos - _M_start;
01174 size_type __length = size();
01175 if (static_cast<size_type>(__elemsbefore) < __length / 2) {
01176 iterator __new_start = _M_reserve_elements_at_front(__n);
01177 iterator __old_start = _M_start;
01178 __pos = _M_start + __elemsbefore;
01179 __STL_TRY {
01180 if (__elemsbefore >= difference_type(__n)) {
01181 iterator __start_n = _M_start + difference_type(__n);
01182 uninitialized_copy(_M_start, __start_n, __new_start);
01183 _M_start = __new_start;
01184 copy(__start_n, __pos, __old_start);
01185 copy(__first, __last, __pos - difference_type(__n));
01186 }
01187 else {
01188 _ForwardIterator __mid = __first;
01189 advance(__mid, difference_type(__n) - __elemsbefore);
01190 __uninitialized_copy_copy(_M_start, __pos, __first, __mid,
01191 __new_start);
01192 _M_start = __new_start;
01193 copy(__mid, __last, __old_start);
01194 }
01195 }
01196 __STL_UNWIND(_M_destroy_nodes(__new_start._M_node, _M_start._M_node));
01197 }
01198 else {
01199 iterator __new_finish = _M_reserve_elements_at_back(__n);
01200 iterator __old_finish = _M_finish;
01201 const difference_type __elemsafter =
01202 difference_type(__length) - __elemsbefore;
01203 __pos = _M_finish - __elemsafter;
01204 __STL_TRY {
01205 if (__elemsafter > difference_type(__n)) {
01206 iterator __finish_n = _M_finish - difference_type(__n);
01207 uninitialized_copy(__finish_n, _M_finish, _M_finish);
01208 _M_finish = __new_finish;
01209 copy_backward(__pos, __finish_n, __old_finish);
01210 copy(__first, __last, __pos);
01211 }
01212 else {
01213 _ForwardIterator __mid = __first;
01214 advance(__mid, __elemsafter);
01215 __uninitialized_copy_copy(__mid, __last, __pos, _M_finish, _M_finish);
01216 _M_finish = __new_finish;
01217 copy(__first, __mid, __pos);
01218 }
01219 }
01220 __STL_UNWIND(_M_destroy_nodes(_M_finish._M_node + 1,
01221 __new_finish._M_node + 1));
01222 }
01223 }
01224
01225 template <class _Tp, class _Alloc>
01226 void deque<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems)
01227 {
01228 size_type __new_nodes
01229 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
01230 _M_reserve_map_at_front(__new_nodes);
01231 size_type __i;
01232 __STL_TRY {
01233 for (__i = 1; __i <= __new_nodes; ++__i)
01234 *(_M_start._M_node - __i) = _M_allocate_node();
01235 }
01236 # ifdef __STL_USE_EXCEPTIONS
01237 catch(...) {
01238 for (size_type __j = 1; __j < __i; ++__j)
01239 _M_deallocate_node(*(_M_start._M_node - __j));
01240 throw;
01241 }
01242 # endif
01243 }
01244
01245 template <class _Tp, class _Alloc>
01246 void deque<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems)
01247 {
01248 size_type __new_nodes
01249 = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size();
01250 _M_reserve_map_at_back(__new_nodes);
01251 size_type __i;
01252 __STL_TRY {
01253 for (__i = 1; __i <= __new_nodes; ++__i)
01254 *(_M_finish._M_node + __i) = _M_allocate_node();
01255 }
01256 # ifdef __STL_USE_EXCEPTIONS
01257 catch(...) {
01258 for (size_type __j = 1; __j < __i; ++__j)
01259 _M_deallocate_node(*(_M_finish._M_node + __j));
01260 throw;
01261 }
01262 # endif
01263 }
01264
01265 template <class _Tp, class _Alloc>
01266 void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add,
01267 bool __add_at_front)
01268 {
01269 size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1;
01270 size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
01271
01272 _Map_pointer __new_nstart;
01273 if (_M_map_size > 2 * __new_num_nodes) {
01274 __new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2
01275 + (__add_at_front ? __nodes_to_add : 0);
01276 if (__new_nstart < _M_start._M_node)
01277 copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
01278 else
01279 copy_backward(_M_start._M_node, _M_finish._M_node + 1,
01280 __new_nstart + __old_num_nodes);
01281 }
01282 else {
01283 size_type __new_map_size =
01284 _M_map_size + max(_M_map_size, __nodes_to_add) + 2;
01285
01286 _Map_pointer __new_map = _M_allocate_map(__new_map_size);
01287 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
01288 + (__add_at_front ? __nodes_to_add : 0);
01289 copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
01290 _M_deallocate_map(_M_map, _M_map_size);
01291
01292 _M_map = __new_map;
01293 _M_map_size = __new_map_size;
01294 }
01295
01296 _M_start._M_set_node(__new_nstart);
01297 _M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
01298 }
01299
01300
01301
01302
01303 template <class _Tp, class _Alloc>
01304 inline bool operator==(const deque<_Tp, _Alloc>& __x,
01305 const deque<_Tp, _Alloc>& __y) {
01306 return __x.size() == __y.size() &&
01307 equal(__x.begin(), __x.end(), __y.begin());
01308 }
01309
01310 template <class _Tp, class _Alloc>
01311 inline bool operator<(const deque<_Tp, _Alloc>& __x,
01312 const deque<_Tp, _Alloc>& __y) {
01313 return lexicographical_compare(__x.begin(), __x.end(),
01314 __y.begin(), __y.end());
01315 }
01316
01317 template <class _Tp, class _Alloc>
01318 inline bool operator!=(const deque<_Tp, _Alloc>& __x,
01319 const deque<_Tp, _Alloc>& __y) {
01320 return !(__x == __y);
01321 }
01322
01323 template <class _Tp, class _Alloc>
01324 inline bool operator>(const deque<_Tp, _Alloc>& __x,
01325 const deque<_Tp, _Alloc>& __y) {
01326 return __y < __x;
01327 }
01328
01329 template <class _Tp, class _Alloc>
01330 inline bool operator<=(const deque<_Tp, _Alloc>& __x,
01331 const deque<_Tp, _Alloc>& __y) {
01332 return !(__y < __x);
01333 }
01334 template <class _Tp, class _Alloc>
01335 inline bool operator>=(const deque<_Tp, _Alloc>& __x,
01336 const deque<_Tp, _Alloc>& __y) {
01337 return !(__x < __y);
01338 }
01339
01340 template <class _Tp, class _Alloc>
01341 inline void swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y) {
01342 __x.swap(__y);
01343 }
01344
01345 }
01346
01347 #endif
01348
01349
01350
01351