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