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