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