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