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 {
00382 _Tp** _M_map;
00383 size_t _M_map_size;
00384 iterator _M_start;
00385 iterator _M_finish;
00386
00387 _Deque_impl(
const _Alloc& __a)
00388 : _Alloc(__a), _M_map(0), _M_map_size(0), _M_start(), _M_finish()
00389 { }
00390 };
00391
00392
typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type;
00393 _Map_alloc_type _M_get_map_allocator()
const
00394
{
return _Map_alloc_type(this->get_allocator()); }
00395
00396 _Tp*
00397 _M_allocate_node()
00398 {
return _M_impl._Alloc::allocate(__deque_buf_size(
sizeof(_Tp))); }
00399
00400
void
00401 _M_deallocate_node(_Tp* __p)
00402 { _M_impl._Alloc::deallocate(__p, __deque_buf_size(
sizeof(_Tp))); }
00403
00404 _Tp**
00405 _M_allocate_map(size_t __n)
00406 {
return _M_get_map_allocator().allocate(__n); }
00407
00408
void
00409 _M_deallocate_map(_Tp** __p, size_t __n)
00410 { _M_get_map_allocator().deallocate(__p, __n); }
00411
00412
protected:
00413
void _M_initialize_map(size_t);
00414
void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
00415
void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
00416
enum { _S_initial_map_size = 8 };
00417
00418 _Deque_impl _M_impl;
00419 };
00420
00421
template<
typename _Tp,
typename _Alloc>
00422 _Deque_base<_Tp, _Alloc>::
00423 ~_Deque_base()
00424 {
00425
if (this->_M_impl._M_map)
00426 {
00427 _M_destroy_nodes(this->_M_impl._M_start._M_node,
00428 this->_M_impl._M_finish._M_node + 1);
00429 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
00430 }
00431 }
00432
00433
00434
00435
00436
00437
00438
00439
00440
00441
00442
00443
template<
typename _Tp,
typename _Alloc>
00444
void
00445 _Deque_base<_Tp, _Alloc>::
00446 _M_initialize_map(size_t __num_elements)
00447 {
00448
const size_t __num_nodes = (__num_elements / __deque_buf_size(
sizeof(_Tp))
00449 + 1);
00450
00451 this->_M_impl._M_map_size =
std::max((size_t) _S_initial_map_size,
00452 size_t(__num_nodes + 2));
00453 this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
00454
00455
00456
00457
00458
00459
00460 _Tp** __nstart = (this->_M_impl._M_map
00461 + (this->_M_impl._M_map_size - __num_nodes) / 2);
00462 _Tp** __nfinish = __nstart + __num_nodes;
00463
00464
try
00465 { _M_create_nodes(__nstart, __nfinish); }
00466
catch(...)
00467 {
00468 _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
00469 this->_M_impl._M_map = 0;
00470 this->_M_impl._M_map_size = 0;
00471 __throw_exception_again;
00472 }
00473
00474 this->_M_impl._M_start._M_set_node(__nstart);
00475 this->_M_impl._M_finish._M_set_node(__nfinish - 1);
00476 this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
00477 this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
00478 + __num_elements
00479 % __deque_buf_size(
sizeof(_Tp)));
00480 }
00481
00482
template<
typename _Tp,
typename _Alloc>
00483
void
00484 _Deque_base<_Tp, _Alloc>::
00485 _M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
00486 {
00487 _Tp** __cur;
00488
try
00489 {
00490
for (__cur = __nstart; __cur < __nfinish; ++__cur)
00491 *__cur = this->_M_allocate_node();
00492 }
00493
catch(...)
00494 {
00495 _M_destroy_nodes(__nstart, __cur);
00496 __throw_exception_again;
00497 }
00498 }
00499
00500
template<
typename _Tp,
typename _Alloc>
00501
void
00502 _Deque_base<_Tp, _Alloc>::
00503 _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
00504 {
00505
for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
00506 _M_deallocate_node(*__n);
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
00585
00586
00587
00588
00589
00590
00591
00592
00593
template<
typename _Tp,
typename _Alloc = allocator<_Tp> >
00594
class deque :
protected _Deque_base<_Tp, _Alloc>
00595 {
00596
00597 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00598
00599
typedef _Deque_base<_Tp, _Alloc> _Base;
00600
00601
public:
00602
typedef _Tp value_type;
00603
typedef typename _Alloc::pointer pointer;
00604
typedef typename _Alloc::const_pointer const_pointer;
00605
typedef typename _Alloc::reference reference;
00606
typedef typename _Alloc::const_reference const_reference;
00607
typedef typename _Base::iterator iterator;
00608
typedef typename _Base::const_iterator const_iterator;
00609
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00610
typedef std::reverse_iterator<iterator> reverse_iterator;
00611
typedef size_t size_type;
00612
typedef ptrdiff_t difference_type;
00613
typedef typename _Base::allocator_type allocator_type;
00614
00615
protected:
00616
typedef pointer* _Map_pointer;
00617
00618
static size_t _S_buffer_size()
00619 {
return __deque_buf_size(
sizeof(_Tp)); }
00620
00621
00622
using _Base::_M_initialize_map;
00623
using _Base::_M_create_nodes;
00624
using _Base::_M_destroy_nodes;
00625
using _Base::_M_allocate_node;
00626
using _Base::_M_deallocate_node;
00627
using _Base::_M_allocate_map;
00628
using _Base::_M_deallocate_map;
00629
00630
00631
00632
00633
00634
00635
using _Base::_M_impl;
00636
00637
public:
00638
00639
00640
00641
00642
00643
explicit
00644
deque(
const allocator_type& __a = allocator_type())
00645 : _Base(__a, 0) {}
00646
00647
00648
00649
00650
00651
00652
00653
00654
deque(size_type __n,
const value_type& __value,
00655
const allocator_type& __a = allocator_type())
00656 : _Base(__a, __n)
00657 { _M_fill_initialize(__value); }
00658
00659
00660
00661
00662
00663
00664
00665
00666
explicit
00667
deque(size_type __n)
00668 : _Base(allocator_type(), __n)
00669 { _M_fill_initialize(value_type()); }
00670
00671
00672
00673
00674
00675
00676
00677
00678
deque(
const deque& __x)
00679 : _Base(__x.
get_allocator(), __x.
size())
00680 { std::__uninitialized_copy_a(__x.
begin(), __x.
end(), this->_M_impl._M_start,
00681 this->
get_allocator()); }
00682
00683
00684
00685
00686
00687
00688
00689
00690
00691
00692
00693
00694
00695
00696
00697
template<
typename _InputIterator>
00698
deque(_InputIterator __first, _InputIterator __last,
00699
const allocator_type& __a = allocator_type())
00700 : _Base(__a)
00701 {
00702
00703
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00704 _M_initialize_dispatch(__first, __last, _Integral());
00705 }
00706
00707
00708
00709
00710
00711
00712
~deque()
00713 { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
00714 this->get_allocator()); }
00715
00716
00717
00718
00719
00720
00721
00722
00723
deque&
00724
operator=(
const deque& __x);
00725
00726
00727
00728
00729
00730
00731
00732
00733
00734
00735
00736
void
00737
assign(size_type __n,
const value_type& __val)
00738 { _M_fill_assign(__n, __val); }
00739
00740
00741
00742
00743
00744
00745
00746
00747
00748
00749
00750
00751
00752
template<
typename _InputIterator>
00753
void
00754
assign(_InputIterator __first, _InputIterator __last)
00755 {
00756
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00757 _M_assign_dispatch(__first, __last, _Integral());
00758 }
00759
00760
00761 allocator_type
00762
get_allocator()
const
00763
{
return _Base::get_allocator(); }
00764
00765
00766
00767
00768
00769
00770 iterator
00771
begin()
00772 {
return this->_M_impl._M_start; }
00773
00774
00775
00776
00777
00778 const_iterator
00779
begin()
const
00780
{
return this->_M_impl._M_start; }
00781
00782
00783
00784
00785
00786 iterator
00787
end()
00788 {
return this->_M_impl._M_finish; }
00789
00790
00791
00792
00793
00794 const_iterator
00795
end()
const
00796
{
return this->_M_impl._M_finish; }
00797
00798
00799
00800
00801
00802
reverse_iterator
00803
rbegin()
00804 {
return reverse_iterator(this->_M_impl._M_finish); }
00805
00806
00807
00808
00809
00810
00811
const_reverse_iterator
00812
rbegin()
const
00813
{
return const_reverse_iterator(this->_M_impl._M_finish); }
00814
00815
00816
00817
00818
00819
00820
reverse_iterator
00821
rend() {
return reverse_iterator(this->_M_impl._M_start); }
00822
00823
00824
00825
00826
00827
00828
const_reverse_iterator
00829
rend()
const
00830
{
return const_reverse_iterator(this->_M_impl._M_start); }
00831
00832
00833
00834 size_type
00835
size()
const
00836 {
return this->_M_impl._M_finish - this->_M_impl._M_start; }
00837
00838
00839 size_type
00840
max_size()
const
00841
{
return size_type(-1); }
00842
00843
00844
00845
00846
00847
00848
00849
00850
00851
00852
00853
void
00854
resize(size_type __new_size,
const value_type& __x)
00855 {
00856
const size_type __len =
size();
00857
if (__new_size < __len)
00858
erase(this->_M_impl._M_start + __new_size, this->_M_impl._M_finish);
00859
else
00860
insert(this->_M_impl._M_finish, __new_size - __len, __x);
00861 }
00862
00863
00864
00865
00866
00867
00868
00869
00870
00871
00872
void
00873
resize(size_type new_size)
00874 {
resize(new_size, value_type()); }
00875
00876
00877
00878
00879
bool
00880
empty()
const
00881
{
return this->_M_impl._M_finish == this->_M_impl._M_start; }
00882
00883
00884
00885
00886
00887
00888
00889
00890
00891
00892
00893 reference
00894
operator[](size_type __n)
00895 {
return this->_M_impl._M_start[difference_type(__n)]; }
00896
00897
00898
00899
00900
00901
00902
00903
00904
00905
00906 const_reference
00907
operator[](size_type __n)
const
00908
{
return this->_M_impl._M_start[difference_type(__n)]; }
00909
00910
protected:
00911
00912
void
00913 _M_range_check(size_type __n)
const
00914
{
00915
if (__n >= this->
size())
00916 __throw_out_of_range(__N(
"deque::_M_range_check"));
00917 }
00918
00919
public:
00920
00921
00922
00923
00924
00925
00926
00927
00928
00929
00930 reference
00931
at(size_type __n)
00932 {
00933 _M_range_check(__n);
00934
return (*this)[__n];
00935 }
00936
00937
00938
00939
00940
00941
00942
00943
00944
00945
00946
00947 const_reference
00948
at(size_type __n)
const
00949
{
00950 _M_range_check(__n);
00951
return (*this)[__n];
00952 }
00953
00954
00955
00956
00957
00958 reference
00959
front()
00960 {
return *this->_M_impl._M_start; }
00961
00962
00963
00964
00965
00966 const_reference
00967
front()
const
00968
{
return *this->_M_impl._M_start; }
00969
00970
00971
00972
00973
00974 reference
00975
back()
00976 {
00977 iterator __tmp = this->_M_impl._M_finish;
00978 --__tmp;
00979
return *__tmp;
00980 }
00981
00982
00983
00984
00985
00986 const_reference
00987
back()
const
00988
{
00989 const_iterator __tmp = this->_M_impl._M_finish;
00990 --__tmp;
00991
return *__tmp;
00992 }
00993
00994
00995
00996
00997
00998
00999
01000
01001
01002
01003
void
01004
push_front(
const value_type& __x)
01005 {
01006
if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
01007 {
01008 this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1, __x);
01009 --this->_M_impl._M_start._M_cur;
01010 }
01011
else
01012 _M_push_front_aux(__x);
01013 }
01014
01015
01016
01017
01018
01019
01020
01021
01022
01023
void
01024
push_back(
const value_type& __x)
01025 {
01026
if (this->_M_impl._M_finish._M_cur
01027 != this->_M_impl._M_finish._M_last - 1)
01028 {
01029 this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __x);
01030 ++this->_M_impl._M_finish._M_cur;
01031 }
01032
else
01033 _M_push_back_aux(__x);
01034 }
01035
01036
01037
01038
01039
01040
01041
01042
01043
01044
void
01045
pop_front()
01046 {
01047
if (this->_M_impl._M_start._M_cur
01048 != this->_M_impl._M_start._M_last - 1)
01049 {
01050 this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
01051 ++this->_M_impl._M_start._M_cur;
01052 }
01053
else
01054 _M_pop_front_aux();
01055 }
01056
01057
01058
01059
01060
01061
01062
01063
01064
01065
void
01066
pop_back()
01067 {
01068
if (this->_M_impl._M_finish._M_cur
01069 != this->_M_impl._M_finish._M_first)
01070 {
01071 --this->_M_impl._M_finish._M_cur;
01072 this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
01073 }
01074
else
01075 _M_pop_back_aux();
01076 }
01077
01078
01079
01080
01081
01082
01083
01084
01085
01086
01087
iterator
01088
insert(
iterator position,
const value_type& __x);
01089
01090
01091
01092
01093
01094
01095
01096
01097
01098
01099
void
01100
insert(iterator __position, size_type __n,
const value_type& __x)
01101 { _M_fill_insert(__position, __n, __x); }
01102
01103
01104
01105
01106
01107
01108
01109
01110
01111
01112
01113
template<
typename _InputIterator>
01114
void
01115
insert(iterator __position, _InputIterator __first,
01116 _InputIterator __last)
01117 {
01118
01119
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
01120 _M_insert_dispatch(__position, __first, __last, _Integral());
01121 }
01122
01123
01124
01125
01126
01127
01128
01129
01130
01131
01132
01133
01134
01135
01136
iterator
01137
erase(
iterator __position);
01138
01139
01140
01141
01142
01143
01144
01145
01146
01147
01148
01149
01150
01151
01152
01153
01154
01155
iterator
01156
erase(
iterator __first,
iterator __last);
01157
01158
01159
01160
01161
01162
01163
01164
01165
01166
01167
void
01168
swap(
deque& __x)
01169 {
01170
std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
01171
std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
01172
std::swap(this->_M_impl._M_map, __x._M_impl._M_map);
01173
std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size);
01174 }
01175
01176
01177
01178
01179
01180
01181
01182
void clear();
01183
01184
protected:
01185
01186
01187
01188
template<
typename _Integer>
01189
void
01190 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
01191 {
01192 _M_initialize_map(__n);
01193 _M_fill_initialize(__x);
01194 }
01195
01196
01197
template<
typename _InputIterator>
01198
void
01199 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
01200 __false_type)
01201 {
01202
typedef typename iterator_traits<_InputIterator>::iterator_category
01203 _IterCategory;
01204 _M_range_initialize(__first, __last, _IterCategory());
01205 }
01206
01207
01208
01209
01210
01211
01212
01213
01214
01215
01216
01217
01218
01219
01220
01221
template<
typename _InputIterator>
01222
void
01223 _M_range_initialize(_InputIterator __first, _InputIterator __last,
01224 input_iterator_tag);
01225
01226
01227
template<
typename _ForwardIterator>
01228
void
01229 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
01230 forward_iterator_tag);
01231
01232
01233
01234
01235
01236
01237
01238
01239
01240
01241
01242
01243
01244
01245
void
01246 _M_fill_initialize(
const value_type& __value);
01247
01248
01249
01250
01251
01252
template<
typename _Integer>
01253
void
01254 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
01255 {
01256 _M_fill_assign(static_cast<size_type>(__n),
01257 static_cast<value_type>(__val));
01258 }
01259
01260
01261
template<
typename _InputIterator>
01262
void
01263 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
01264 __false_type)
01265 {
01266
typedef typename iterator_traits<_InputIterator>::iterator_category
01267 _IterCategory;
01268 _M_assign_aux(__first, __last, _IterCategory());
01269 }
01270
01271
01272
template<
typename _InputIterator>
01273
void
01274 _M_assign_aux(_InputIterator __first, _InputIterator __last,
01275 input_iterator_tag);
01276
01277
01278
template<
typename _ForwardIterator>
01279
void
01280 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
01281 forward_iterator_tag)
01282 {
01283
const size_type __len =
std::distance(__first, __last);
01284
if (__len >
size())
01285 {
01286 _ForwardIterator __mid = __first;
01287
std::advance(__mid,
size());
01288
std::copy(__first, __mid,
begin());
01289
insert(
end(), __mid, __last);
01290 }
01291
else
01292
erase(std::copy(__first, __last,
begin()),
end());
01293 }
01294
01295
01296
01297
void
01298 _M_fill_assign(size_type __n,
const value_type& __val)
01299 {
01300
if (__n >
size())
01301 {
01302
std::fill(
begin(),
end(), __val);
01303
insert(
end(), __n -
size(), __val);
01304 }
01305
else
01306 {
01307
erase(
begin() + __n,
end());
01308
std::fill(
begin(),
end(), __val);
01309 }
01310 }
01311
01312
01313
01314
01315
01316
01317
01318
void _M_push_back_aux(
const value_type&);
01319
void _M_push_front_aux(
const value_type&);
01320
void _M_pop_back_aux();
01321
void _M_pop_front_aux();
01322
01323
01324
01325
01326
01327
01328
template<
typename _Integer>
01329
void
01330 _M_insert_dispatch(iterator __pos,
01331 _Integer __n, _Integer __x, __true_type)
01332 {
01333 _M_fill_insert(__pos, static_cast<size_type>(__n),
01334 static_cast<value_type>(__x));
01335 }
01336
01337
01338
template<
typename _InputIterator>
01339
void
01340 _M_insert_dispatch(iterator __pos,
01341 _InputIterator __first, _InputIterator __last,
01342 __false_type)
01343 {
01344
typedef typename iterator_traits<_InputIterator>::iterator_category
01345 _IterCategory;
01346 _M_range_insert_aux(__pos, __first, __last, _IterCategory());
01347 }
01348
01349
01350
template<
typename _InputIterator>
01351
void
01352 _M_range_insert_aux(iterator __pos, _InputIterator __first,
01353 _InputIterator __last, input_iterator_tag);
01354
01355
01356
template<
typename _ForwardIterator>
01357
void
01358 _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
01359 _ForwardIterator __last, forward_iterator_tag);
01360
01361
01362
01363
01364
void
01365 _M_fill_insert(iterator __pos, size_type __n,
const value_type& __x);
01366
01367
01368 iterator
01369 _M_insert_aux(iterator __pos,
const value_type& __x);
01370
01371
01372
void
01373 _M_insert_aux(iterator __pos, size_type __n,
const value_type& __x);
01374
01375
01376
template<
typename _ForwardIterator>
01377
void
01378 _M_insert_aux(iterator __pos,
01379 _ForwardIterator __first, _ForwardIterator __last,
01380 size_type __n);
01381
01382
01383
01384
01385
01386
01387
01388
01389 iterator
01390 _M_reserve_elements_at_front(size_type __n)
01391 {
01392
const size_type __vacancies = this->_M_impl._M_start._M_cur
01393 - this->_M_impl._M_start._M_first;
01394
if (__n > __vacancies)
01395 _M_new_elements_at_front(__n - __vacancies);
01396
return this->_M_impl._M_start - difference_type(__n);
01397 }
01398
01399 iterator
01400 _M_reserve_elements_at_back(size_type __n)
01401 {
01402
const size_type __vacancies = (this->_M_impl._M_finish._M_last
01403 - this->_M_impl._M_finish._M_cur) - 1;
01404
if (__n > __vacancies)
01405 _M_new_elements_at_back(__n - __vacancies);
01406
return this->_M_impl._M_finish + difference_type(__n);
01407 }
01408
01409
void
01410 _M_new_elements_at_front(size_type __new_elements);
01411
01412
void
01413 _M_new_elements_at_back(size_type __new_elements);
01414
01415
01416
01417
01418
01419
01420
01421
01422
01423
01424
01425
01426
01427
void
01428 _M_reserve_map_at_back (size_type __nodes_to_add = 1)
01429 {
01430
if (__nodes_to_add + 1 > this->_M_impl._M_map_size
01431 - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
01432 _M_reallocate_map(__nodes_to_add,
false);
01433 }
01434
01435
void
01436 _M_reserve_map_at_front (size_type __nodes_to_add = 1)
01437 {
01438
if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
01439 - this->_M_impl._M_map))
01440 _M_reallocate_map(__nodes_to_add,
true);
01441 }
01442
01443
void
01444 _M_reallocate_map(size_type __nodes_to_add,
bool __add_at_front);
01445
01446 };
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 __x.
size() == __y.
size()
01464 &&
std::equal(__x.
begin(), __x.
end(), __y.
begin()); }
01465
01466
01467
01468
01469
01470
01471
01472
01473
01474
01475
01476
01477
template<
typename _Tp,
typename _Alloc>
01478
inline bool
01479 operator<(const deque<_Tp, _Alloc>& __x,
01480
const deque<_Tp, _Alloc>& __y)
01481 {
return lexicographical_compare(__x.begin(), __x.end(),
01482 __y.begin(), __y.end()); }
01483
01484
01485
template<
typename _Tp,
typename _Alloc>
01486
inline bool
01487
operator!=(
const deque<_Tp, _Alloc>& __x,
01488
const deque<_Tp, _Alloc>& __y)
01489 {
return !(__x == __y); }
01490
01491
01492
template<
typename _Tp,
typename _Alloc>
01493
inline bool
01494
operator>(
const deque<_Tp, _Alloc>& __x,
01495
const deque<_Tp, _Alloc>& __y)
01496 {
return __y < __x; }
01497
01498
01499
template<
typename _Tp,
typename _Alloc>
01500
inline bool
01501 operator<=(const deque<_Tp, _Alloc>& __x,
01502
const deque<_Tp, _Alloc>& __y)
01503 {
return !(__y < __x); }
01504
01505
01506
template<
typename _Tp,
typename _Alloc>
01507
inline bool
01508
operator>=(
const deque<_Tp, _Alloc>& __x,
01509
const deque<_Tp, _Alloc>& __y)
01510 {
return !(__x < __y); }
01511
01512
01513
template<
typename _Tp,
typename _Alloc>
01514
inline void
01515
swap(
deque<_Tp,_Alloc>& __x,
deque<_Tp,_Alloc>& __y)
01516 { __x.
swap(__y); }
01517 }
01518
01519
#endif