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