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