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(__x.
begin(), __x.
end(),
00681 this->_M_impl._M_start); }
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
00715
00716
00717
00718
00719
00720
00721
00722
deque&
00723 operator=(
const deque& __x);
00724
00725
00726
00727
00728
00729
00730
00731
00732
00733
00734
00735
void
00736
assign(size_type __n,
const value_type& __val)
00737 { _M_fill_assign(__n, __val); }
00738
00739
00740
00741
00742
00743
00744
00745
00746
00747
00748
00749
00750
00751
template<
typename _InputIterator>
00752
void
00753 assign(_InputIterator __first, _InputIterator __last)
00754 {
00755
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00756 _M_assign_dispatch(__first, __last, _Integral());
00757 }
00758
00759
00760 allocator_type
00761
get_allocator()
const
00762
{
return _Base::get_allocator(); }
00763
00764
00765
00766
00767
00768
00769 iterator
00770
begin()
00771 {
return this->_M_impl._M_start; }
00772
00773
00774
00775
00776
00777 const_iterator
00778
begin()
const
00779
{
return this->_M_impl._M_start; }
00780
00781
00782
00783
00784
00785 iterator
00786
end()
00787 {
return this->_M_impl._M_finish; }
00788
00789
00790
00791
00792
00793 const_iterator
00794
end()
const
00795
{
return this->_M_impl._M_finish; }
00796
00797
00798
00799
00800
00801
reverse_iterator
00802
rbegin()
00803 {
return reverse_iterator(this->_M_impl._M_finish); }
00804
00805
00806
00807
00808
00809
00810
const_reverse_iterator
00811
rbegin()
const
00812
{
return const_reverse_iterator(this->_M_impl._M_finish); }
00813
00814
00815
00816
00817
00818
00819
reverse_iterator
00820
rend() {
return reverse_iterator(this->_M_impl._M_start); }
00821
00822
00823
00824
00825
00826
00827
const_reverse_iterator
00828
rend()
const
00829
{
return const_reverse_iterator(this->_M_impl._M_start); }
00830
00831
00832
00833 size_type
00834
size()
const
00835 {
return this->_M_impl._M_finish - this->_M_impl._M_start; }
00836
00837
00838 size_type
00839
max_size()
const
00840
{
return size_type(-1); }
00841
00842
00843
00844
00845
00846
00847
00848
00849
00850
00851
00852
void
00853
resize(size_type __new_size,
const value_type& __x)
00854 {
00855
const size_type __len =
size();
00856
if (__new_size < __len)
00857
erase(this->_M_impl._M_start + __new_size, this->_M_impl._M_finish);
00858
else
00859
insert(this->_M_impl._M_finish, __new_size - __len, __x);
00860 }
00861
00862
00863
00864
00865
00866
00867
00868
00869
00870
00871
void
00872 resize(size_type new_size)
00873 { resize(new_size, value_type()); }
00874
00875
00876
00877
00878
bool
00879
empty()
const
00880
{
return this->_M_impl._M_finish == this->_M_impl._M_start; }
00881
00882
00883
00884
00885
00886
00887
00888
00889
00890
00891
00892 reference
00893
operator[](size_type __n)
00894 {
return this->_M_impl._M_start[difference_type(__n)]; }
00895
00896
00897
00898
00899
00900
00901
00902
00903
00904
00905 const_reference
00906
operator[](size_type __n)
const
00907
{
return this->_M_impl._M_start[difference_type(__n)]; }
00908
00909
protected:
00910
00911
void
00912 _M_range_check(size_type __n)
const
00913
{
00914
if (__n >= this->
size())
00915 __throw_out_of_range(__N(
"deque::_M_range_check"));
00916 }
00917
00918
public:
00919
00920
00921
00922
00923
00924
00925
00926
00927
00928
00929 reference
00930
at(size_type __n)
00931 {
00932 _M_range_check(__n);
00933
return (*this)[__n];
00934 }
00935
00936
00937
00938
00939
00940
00941
00942
00943
00944
00945
00946 const_reference
00947 at(size_type __n)
const
00948
{
00949 _M_range_check(__n);
00950
return (*this)[__n];
00951 }
00952
00953
00954
00955
00956
00957 reference
00958
front()
00959 {
return *this->_M_impl._M_start; }
00960
00961
00962
00963
00964
00965 const_reference
00966
front()
const
00967
{
return *this->_M_impl._M_start; }
00968
00969
00970
00971
00972
00973 reference
00974
back()
00975 {
00976 iterator __tmp = this->_M_impl._M_finish;
00977 --__tmp;
00978
return *__tmp;
00979 }
00980
00981
00982
00983
00984
00985 const_reference
00986
back()
const
00987
{
00988 const_iterator __tmp = this->_M_impl._M_finish;
00989 --__tmp;
00990
return *__tmp;
00991 }
00992
00993
00994
00995
00996
00997
00998
00999
01000
01001
01002
void
01003
push_front(
const value_type& __x)
01004 {
01005
if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
01006 {
01007 std::_Construct(this->_M_impl._M_start._M_cur - 1, __x);
01008 --this->_M_impl._M_start._M_cur;
01009 }
01010
else
01011 _M_push_front_aux(__x);
01012 }
01013
01014
01015
01016
01017
01018
01019
01020
01021
01022
void
01023
push_back(
const value_type& __x)
01024 {
01025
if (this->_M_impl._M_finish._M_cur
01026 != this->_M_impl._M_finish._M_last - 1)
01027 {
01028 std::_Construct(this->_M_impl._M_finish._M_cur, __x);
01029 ++this->_M_impl._M_finish._M_cur;
01030 }
01031
else
01032 _M_push_back_aux(__x);
01033 }
01034
01035
01036
01037
01038
01039
01040
01041
01042
01043
void
01044
pop_front()
01045 {
01046
if (this->_M_impl._M_start._M_cur
01047 != this->_M_impl._M_start._M_last - 1)
01048 {
01049 std::_Destroy(this->_M_impl._M_start._M_cur);
01050 ++this->_M_impl._M_start._M_cur;
01051 }
01052
else
01053 _M_pop_front_aux();
01054 }
01055
01056
01057
01058
01059
01060
01061
01062
01063
01064
void
01065
pop_back()
01066 {
01067
if (this->_M_impl._M_finish._M_cur
01068 != this->_M_impl._M_finish._M_first)
01069 {
01070 --this->_M_impl._M_finish._M_cur;
01071 std::_Destroy(this->_M_impl._M_finish._M_cur);
01072 }
01073
else
01074 _M_pop_back_aux();
01075 }
01076
01077
01078
01079
01080
01081
01082
01083
01084
01085
01086
iterator
01087 insert(
iterator position,
const value_type& __x);
01088
01089
01090
01091
01092
01093
01094
01095
01096
01097
01098
void
01099 insert(iterator __position, size_type __n,
const value_type& __x)
01100 { _M_fill_insert(__position, __n, __x); }
01101
01102
01103
01104
01105
01106
01107
01108
01109
01110
01111
01112
template<
typename _InputIterator>
01113
void
01114 insert(iterator __position, _InputIterator __first,
01115 _InputIterator __last)
01116 {
01117
01118
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
01119 _M_insert_dispatch(__position, __first, __last, _Integral());
01120 }
01121
01122
01123
01124
01125
01126
01127
01128
01129
01130
01131
01132
01133
01134
01135
iterator
01136 erase(
iterator __position);
01137
01138
01139
01140
01141
01142
01143
01144
01145
01146
01147
01148
01149
01150
01151
01152
01153
01154
iterator
01155 erase(
iterator __first,
iterator __last);
01156
01157
01158
01159
01160
01161
01162
01163
01164
01165
01166
void
01167
swap(
deque& __x)
01168 {
01169
std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
01170
std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
01171
std::swap(this->_M_impl._M_map, __x._M_impl._M_map);
01172
std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size);
01173 }
01174
01175
01176
01177
01178
01179
01180
01181
void clear();
01182
01183
protected:
01184
01185
01186
01187
template<
typename _Integer>
01188
void
01189 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
01190 {
01191 _M_initialize_map(__n);
01192 _M_fill_initialize(__x);
01193 }
01194
01195
01196
template<
typename _InputIterator>
01197
void
01198 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
01199 __false_type)
01200 {
01201
typedef typename iterator_traits<_InputIterator>::iterator_category
01202 _IterCategory;
01203 _M_range_initialize(__first, __last, _IterCategory());
01204 }
01205
01206
01207
01208
01209
01210
01211
01212
01213
01214
01215
01216
01217
01218
01219
01220
template<
typename _InputIterator>
01221
void
01222 _M_range_initialize(_InputIterator __first, _InputIterator __last,
01223 input_iterator_tag);
01224
01225
01226
template<
typename _ForwardIterator>
01227
void
01228 _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
01229 forward_iterator_tag);
01230
01231
01232
01233
01234
01235
01236
01237
01238
01239
01240
01241
01242
01243
01244
void
01245 _M_fill_initialize(
const value_type& __value);
01246
01247
01248
01249
01250
01251
template<
typename _Integer>
01252
void
01253 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
01254 {
01255 _M_fill_assign(static_cast<size_type>(__n),
01256 static_cast<value_type>(__val));
01257 }
01258
01259
01260
template<
typename _InputIterator>
01261
void
01262 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
01263 __false_type)
01264 {
01265
typedef typename iterator_traits<_InputIterator>::iterator_category
01266 _IterCategory;
01267 _M_assign_aux(__first, __last, _IterCategory());
01268 }
01269
01270
01271
template<
typename _InputIterator>
01272
void
01273 _M_assign_aux(_InputIterator __first, _InputIterator __last,
01274 input_iterator_tag);
01275
01276
01277
template<
typename _ForwardIterator>
01278
void
01279 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
01280 forward_iterator_tag)
01281 {
01282
const size_type __len =
std::distance(__first, __last);
01283
if (__len >
size())
01284 {
01285 _ForwardIterator __mid = __first;
01286
std::advance(__mid,
size());
01287
std::copy(__first, __mid,
begin());
01288 insert(
end(), __mid, __last);
01289 }
01290
else
01291 erase(std::copy(__first, __last,
begin()),
end());
01292 }
01293
01294
01295
01296
void
01297 _M_fill_assign(size_type __n,
const value_type& __val)
01298 {
01299
if (__n >
size())
01300 {
01301
std::fill(
begin(),
end(), __val);
01302 insert(
end(), __n -
size(), __val);
01303 }
01304
else
01305 {
01306 erase(
begin() + __n,
end());
01307
std::fill(
begin(),
end(), __val);
01308 }
01309 }
01310
01311
01312
01313
01314
01315
01316
01317
void _M_push_back_aux(
const value_type&);
01318
void _M_push_front_aux(
const value_type&);
01319
void _M_pop_back_aux();
01320
void _M_pop_front_aux();
01321
01322
01323
01324
01325
01326
01327
template<
typename _Integer>
01328
void
01329 _M_insert_dispatch(iterator __pos,
01330 _Integer __n, _Integer __x, __true_type)
01331 {
01332 _M_fill_insert(__pos, static_cast<size_type>(__n),
01333 static_cast<value_type>(__x));
01334 }
01335
01336
01337
template<
typename _InputIterator>
01338
void
01339 _M_insert_dispatch(iterator __pos,
01340 _InputIterator __first, _InputIterator __last,
01341 __false_type)
01342 {
01343
typedef typename iterator_traits<_InputIterator>::iterator_category
01344 _IterCategory;
01345 _M_range_insert_aux(__pos, __first, __last, _IterCategory());
01346 }
01347
01348
01349
template<
typename _InputIterator>
01350
void
01351 _M_range_insert_aux(iterator __pos, _InputIterator __first,
01352 _InputIterator __last, input_iterator_tag);
01353
01354
01355
template<
typename _ForwardIterator>
01356
void
01357 _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
01358 _ForwardIterator __last, forward_iterator_tag);
01359
01360
01361
01362
01363
void
01364 _M_fill_insert(iterator __pos, size_type __n,
const value_type& __x);
01365
01366
01367 iterator
01368 _M_insert_aux(iterator __pos,
const value_type& __x);
01369
01370
01371
void
01372 _M_insert_aux(iterator __pos, size_type __n,
const value_type& __x);
01373
01374
01375
template<
typename _ForwardIterator>
01376
void
01377 _M_insert_aux(iterator __pos,
01378 _ForwardIterator __first, _ForwardIterator __last,
01379 size_type __n);
01380
01381
01382
01383
01384
01385
01386
01387
01388 iterator
01389 _M_reserve_elements_at_front(size_type __n)
01390 {
01391
const size_type __vacancies = this->_M_impl._M_start._M_cur
01392 - this->_M_impl._M_start._M_first;
01393
if (__n > __vacancies)
01394 _M_new_elements_at_front(__n - __vacancies);
01395
return this->_M_impl._M_start - difference_type(__n);
01396 }
01397
01398 iterator
01399 _M_reserve_elements_at_back(size_type __n)
01400 {
01401
const size_type __vacancies = (this->_M_impl._M_finish._M_last
01402 - this->_M_impl._M_finish._M_cur) - 1;
01403
if (__n > __vacancies)
01404 _M_new_elements_at_back(__n - __vacancies);
01405
return this->_M_impl._M_finish + difference_type(__n);
01406 }
01407
01408
void
01409 _M_new_elements_at_front(size_type __new_elements);
01410
01411
void
01412 _M_new_elements_at_back(size_type __new_elements);
01413
01414
01415
01416
01417
01418
01419
01420
01421
01422
01423
01424
01425
01426
void
01427 _M_reserve_map_at_back (size_type __nodes_to_add = 1)
01428 {
01429
if (__nodes_to_add + 1 > this->_M_impl._M_map_size
01430 - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
01431 _M_reallocate_map(__nodes_to_add,
false);
01432 }
01433
01434
void
01435 _M_reserve_map_at_front (size_type __nodes_to_add = 1)
01436 {
01437
if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
01438 - this->_M_impl._M_map))
01439 _M_reallocate_map(__nodes_to_add,
true);
01440 }
01441
01442
void
01443 _M_reallocate_map(size_type __nodes_to_add,
bool __add_at_front);
01444
01445 };
01446
01447
01448
01449
01450
01451
01452
01453
01454
01455
01456
01457
01458
template<
typename _Tp,
typename _Alloc>
01459
inline bool
01460
operator==(
const deque<_Tp, _Alloc>& __x,
01461
const deque<_Tp, _Alloc>& __y)
01462 {
return __x.
size() == __y.
size()
01463 &&
std::equal(__x.
begin(), __x.
end(), __y.
begin()); }
01464
01465
01466
01467
01468
01469
01470
01471
01472
01473
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 lexicographical_compare(__x.begin(), __x.end(),
01481 __y.begin(), __y.end()); }
01482
01483
01484
template<
typename _Tp,
typename _Alloc>
01485
inline bool
01486
operator!=(
const deque<_Tp, _Alloc>& __x,
01487
const deque<_Tp, _Alloc>& __y)
01488 {
return !(__x == __y); }
01489
01490
01491
template<
typename _Tp,
typename _Alloc>
01492
inline bool
01493
operator>(
const deque<_Tp, _Alloc>& __x,
01494
const deque<_Tp, _Alloc>& __y)
01495 {
return __y < __x; }
01496
01497
01498
template<
typename _Tp,
typename _Alloc>
01499
inline bool
01500 operator<=(const deque<_Tp, _Alloc>& __x,
01501
const deque<_Tp, _Alloc>& __y)
01502 {
return !(__y < __x); }
01503
01504
01505
template<
typename _Tp,
typename _Alloc>
01506
inline bool
01507
operator>=(
const deque<_Tp, _Alloc>& __x,
01508
const deque<_Tp, _Alloc>& __y)
01509 {
return !(__x < __y); }
01510
01511
01512
template<
typename _Tp,
typename _Alloc>
01513
inline void
01514
swap(
deque<_Tp,_Alloc>& __x,
deque<_Tp,_Alloc>& __y)
01515 { __x.
swap(__y); }
01516 }
01517
01518
#endif