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