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