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