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