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 _BVECTOR_H
00062
#define _BVECTOR_H 1
00063
00064
namespace _GLIBCXX_STD
00065 {
00066
typedef unsigned long _Bit_type;
00067
enum { _S_word_bit = int(CHAR_BIT *
sizeof(_Bit_type)) };
00068
00069
struct _Bit_reference
00070 {
00071 _Bit_type * _M_p;
00072 _Bit_type _M_mask;
00073
00074 _Bit_reference(_Bit_type * __x, _Bit_type __y)
00075 : _M_p(__x), _M_mask(__y) { }
00076
00077 _Bit_reference() : _M_p(0), _M_mask(0) { }
00078
00079 operator bool()
const
00080
{
return !!(*_M_p & _M_mask); }
00081
00082 _Bit_reference&
00083 operator=(
bool __x)
00084 {
00085
if (__x)
00086 *_M_p |= _M_mask;
00087
else
00088 *_M_p &= ~_M_mask;
00089
return *
this;
00090 }
00091
00092 _Bit_reference&
00093 operator=(
const _Bit_reference& __x)
00094 {
return *
this = bool(__x); }
00095
00096
bool
00097 operator==(
const _Bit_reference& __x)
const
00098
{
return bool(*
this) == bool(__x); }
00099
00100
bool
00101
operator<(
const _Bit_reference& __x)
const
00102
{
return !bool(*
this) && bool(__x); }
00103
00104
void
00105 flip()
00106 { *_M_p ^= _M_mask; }
00107 };
00108
00109
struct _Bit_iterator_base :
public iterator<random_access_iterator_tag, bool>
00110 {
00111 _Bit_type * _M_p;
00112
unsigned int _M_offset;
00113
00114 _Bit_iterator_base(_Bit_type * __x,
unsigned int __y)
00115 : _M_p(__x), _M_offset(__y) { }
00116
00117
void
00118 _M_bump_up()
00119 {
00120
if (_M_offset++ == _S_word_bit - 1)
00121 {
00122 _M_offset = 0;
00123 ++_M_p;
00124 }
00125 }
00126
00127
void
00128 _M_bump_down()
00129 {
00130
if (_M_offset-- == 0)
00131 {
00132 _M_offset = _S_word_bit - 1;
00133 --_M_p;
00134 }
00135 }
00136
00137
void
00138 _M_incr(ptrdiff_t __i)
00139 {
00140 difference_type __n = __i + _M_offset;
00141 _M_p += __n / _S_word_bit;
00142 __n = __n % _S_word_bit;
00143
if (__n < 0)
00144 {
00145 _M_offset = static_cast<unsigned int>(__n + _S_word_bit);
00146 --_M_p;
00147 }
00148
else
00149 _M_offset = static_cast<unsigned int>(__n);
00150 }
00151
00152
bool
00153 operator==(
const _Bit_iterator_base& __i)
const
00154
{
return _M_p == __i._M_p && _M_offset == __i._M_offset; }
00155
00156
bool
00157
operator<(
const _Bit_iterator_base& __i)
const
00158
{
00159
return _M_p < __i._M_p
00160 || (_M_p == __i._M_p && _M_offset < __i._M_offset);
00161 }
00162
00163
bool
00164 operator!=(
const _Bit_iterator_base& __i)
const
00165
{
return !(*
this == __i); }
00166
00167
bool
00168
operator>(
const _Bit_iterator_base& __i)
const
00169
{
return __i < *
this; }
00170
00171
bool
00172
operator<=(
const _Bit_iterator_base& __i)
const
00173
{
return !(__i < *
this); }
00174
00175
bool
00176
operator>=(
const _Bit_iterator_base& __i)
const
00177
{
return !(*
this < __i); }
00178 };
00179
00180
inline ptrdiff_t
00181 operator-(
const _Bit_iterator_base& __x,
const _Bit_iterator_base& __y)
00182 {
00183
return _S_word_bit * (__x._M_p - __y._M_p) + __x._M_offset - __y._M_offset;
00184 }
00185
00186
struct _Bit_iterator :
public _Bit_iterator_base
00187 {
00188
typedef _Bit_reference reference;
00189
typedef _Bit_reference* pointer;
00190
typedef _Bit_iterator iterator;
00191
00192 _Bit_iterator() : _Bit_iterator_base(0, 0) { }
00193
00194 _Bit_iterator(_Bit_type * __x,
unsigned int __y)
00195 : _Bit_iterator_base(__x, __y) { }
00196
00197 reference
00198 operator*()
const
00199
{
return reference(_M_p, 1UL << _M_offset); }
00200
00201 iterator&
00202 operator++()
00203 {
00204 _M_bump_up();
00205
return *
this;
00206 }
00207
00208 iterator
00209 operator++(
int)
00210 {
00211 iterator __tmp = *
this;
00212 _M_bump_up();
00213
return __tmp;
00214 }
00215
00216 iterator&
00217 operator--()
00218 {
00219 _M_bump_down();
00220
return *
this;
00221 }
00222
00223 iterator
00224 operator--(
int)
00225 {
00226 iterator __tmp = *
this;
00227 _M_bump_down();
00228
return __tmp;
00229 }
00230
00231 iterator&
00232 operator+=(difference_type __i)
00233 {
00234 _M_incr(__i);
00235
return *
this;
00236 }
00237
00238 iterator&
00239 operator-=(difference_type __i)
00240 {
00241 *
this += -__i;
00242
return *
this;
00243 }
00244
00245 iterator
00246
operator+(difference_type __i)
const
00247
{
00248 iterator __tmp = *
this;
00249
return __tmp += __i;
00250 }
00251
00252 iterator
00253 operator-(difference_type __i)
const
00254
{
00255 iterator __tmp = *
this;
00256
return __tmp -= __i;
00257 }
00258
00259 reference
00260 operator[](difference_type __i)
00261 {
return *(*
this + __i); }
00262 };
00263
00264
inline _Bit_iterator
00265
operator+(ptrdiff_t __n,
const _Bit_iterator& __x)
00266 {
return __x + __n; }
00267
00268
struct _Bit_const_iterator :
public _Bit_iterator_base
00269 {
00270
typedef bool reference;
00271
typedef bool const_reference;
00272
typedef const bool* pointer;
00273
typedef _Bit_const_iterator const_iterator;
00274
00275 _Bit_const_iterator() : _Bit_iterator_base(0, 0) { }
00276
00277 _Bit_const_iterator(_Bit_type * __x,
unsigned int __y)
00278 : _Bit_iterator_base(__x, __y) { }
00279
00280 _Bit_const_iterator(
const _Bit_iterator& __x)
00281 : _Bit_iterator_base(__x._M_p, __x._M_offset) { }
00282
00283 const_reference
00284 operator*()
const
00285
{
return _Bit_reference(_M_p, 1UL << _M_offset); }
00286
00287 const_iterator&
00288 operator++()
00289 {
00290 _M_bump_up();
00291
return *
this;
00292 }
00293
00294 const_iterator
00295 operator++(
int)
00296 {
00297 const_iterator __tmp = *
this;
00298 _M_bump_up();
00299
return __tmp;
00300 }
00301
00302 const_iterator&
00303 operator--()
00304 {
00305 _M_bump_down();
00306
return *
this;
00307 }
00308
00309 const_iterator
00310 operator--(
int)
00311 {
00312 const_iterator __tmp = *
this;
00313 _M_bump_down();
00314
return __tmp;
00315 }
00316
00317 const_iterator&
00318 operator+=(difference_type __i)
00319 {
00320 _M_incr(__i);
00321
return *
this;
00322 }
00323
00324 const_iterator&
00325 operator-=(difference_type __i)
00326 {
00327 *
this += -__i;
00328
return *
this;
00329 }
00330
00331 const_iterator
00332
operator+(difference_type __i)
const
00333
{
00334 const_iterator __tmp = *
this;
00335
return __tmp += __i;
00336 }
00337
00338 const_iterator
00339 operator-(difference_type __i)
const
00340
{
00341 const_iterator __tmp = *
this;
00342
return __tmp -= __i;
00343 }
00344
00345 const_reference
00346 operator[](difference_type __i)
00347 {
return *(*
this + __i); }
00348 };
00349
00350
inline _Bit_const_iterator
00351
operator+(ptrdiff_t __n,
const _Bit_const_iterator& __x)
00352 {
return __x + __n; }
00353
00354
template<
class _Alloc>
00355
class _Bvector_base
00356 {
00357
typedef typename _Alloc::template rebind<_Bit_type>::other
00358 _Bit_alloc_type;
00359
00360
struct _Bvector_impl :
public _Bit_alloc_type
00361 {
00362 _Bit_iterator _M_start;
00363 _Bit_iterator _M_finish;
00364 _Bit_type* _M_end_of_storage;
00365 _Bvector_impl(
const _Bit_alloc_type& __a)
00366 : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage(0)
00367 { }
00368 };
00369
00370
public:
00371
typedef _Alloc allocator_type;
00372
00373 allocator_type
00374 get_allocator()
const
00375
{
return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); }
00376
00377 _Bvector_base(
const allocator_type& __a) : _M_impl(__a) { }
00378
00379 ~_Bvector_base()
00380 { this->_M_deallocate(); }
00381
00382
protected:
00383 _Bvector_impl _M_impl;
00384
00385 _Bit_type*
00386 _M_allocate(size_t __n)
00387 {
return _M_impl.allocate((__n + _S_word_bit - 1) / _S_word_bit); }
00388
00389
void
00390 _M_deallocate()
00391 {
00392
if (_M_impl._M_start._M_p)
00393 _M_impl.deallocate(_M_impl._M_start._M_p,
00394 _M_impl._M_end_of_storage - _M_impl._M_start._M_p);
00395 }
00396 };
00397 }
00398
00399
00400
#include <bits/stl_vector.h>
00401
00402
namespace _GLIBCXX_STD
00403 {
00404
00405
00406
00407
00408
00409
00410
00411
00412
00413
00414
00415
00416
00417
00418
00419
00420
00421
00422
template<
typename _Alloc>
00423 class vector<bool, _Alloc> :
public _Bvector_base<_Alloc>
00424 {
00425
public:
00426
typedef bool value_type;
00427
typedef size_t size_type;
00428
typedef ptrdiff_t difference_type;
00429
typedef _Bit_reference reference;
00430
typedef bool const_reference;
00431
typedef _Bit_reference* pointer;
00432
typedef const bool* const_pointer;
00433
00434
typedef _Bit_iterator iterator;
00435
typedef _Bit_const_iterator const_iterator;
00436
00437
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00438
typedef std::reverse_iterator<iterator> reverse_iterator;
00439
00440
typedef typename _Bvector_base<_Alloc>::allocator_type allocator_type;
00441
00442 allocator_type get_allocator()
const
00443
{
return _Bvector_base<_Alloc>::get_allocator(); }
00444
00445
protected:
00446
using _Bvector_base<_Alloc>::_M_allocate;
00447
using _Bvector_base<_Alloc>::_M_deallocate;
00448
00449
protected:
00450
void
00451 _M_initialize(size_type __n)
00452 {
00453 _Bit_type* __q = this->_M_allocate(__n);
00454 this->_M_impl._M_end_of_storage = (__q
00455 + ((__n + _S_word_bit - 1)
00456 / _S_word_bit));
00457 this->_M_impl._M_start = iterator(__q, 0);
00458 this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n);
00459 }
00460
00461
void
00462 _M_insert_aux(iterator __position,
bool __x)
00463 {
00464
if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
00465 {
00466
std::copy_backward(__position, this->_M_impl._M_finish,
00467 this->_M_impl._M_finish + 1);
00468 *__position = __x;
00469 ++this->_M_impl._M_finish;
00470 }
00471
else
00472 {
00473
const size_type __len = size() ? 2 * size()
00474 : static_cast<size_type>(_S_word_bit);
00475 _Bit_type * __q = this->_M_allocate(__len);
00476 iterator __i =
std::copy(begin(), __position, iterator(__q, 0));
00477 *__i++ = __x;
00478 this->_M_impl._M_finish =
std::copy(__position, end(), __i);
00479 this->_M_deallocate();
00480 this->_M_impl._M_end_of_storage = (__q + ((__len + _S_word_bit - 1)
00481 / _S_word_bit));
00482 this->_M_impl._M_start = iterator(__q, 0);
00483 }
00484 }
00485
00486
template<
class _InputIterator>
00487
void
00488 _M_initialize_range(_InputIterator __first, _InputIterator __last,
00489
input_iterator_tag)
00490 {
00491 this->_M_impl._M_start = iterator();
00492 this->_M_impl._M_finish = iterator();
00493 this->_M_impl._M_end_of_storage = 0;
00494
for (; __first != __last; ++__first)
00495 push_back(*__first);
00496 }
00497
00498
template<
class _ForwardIterator>
00499
void
00500 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
00501
forward_iterator_tag)
00502 {
00503
const size_type __n =
std::distance(__first, __last);
00504 _M_initialize(__n);
00505
std::copy(__first, __last, this->_M_impl._M_start);
00506 }
00507
00508
template<
class _InputIterator>
00509
void
00510 _M_insert_range(iterator __pos, _InputIterator __first,
00511 _InputIterator __last,
input_iterator_tag)
00512 {
00513
for (; __first != __last; ++__first)
00514 {
00515 __pos = insert(__pos, *__first);
00516 ++__pos;
00517 }
00518 }
00519
00520
template<
class _ForwardIterator>
00521
void
00522 _M_insert_range(iterator __position, _ForwardIterator __first,
00523 _ForwardIterator __last,
forward_iterator_tag)
00524 {
00525
if (__first != __last)
00526 {
00527 size_type __n =
std::distance(__first, __last);
00528
if (capacity() - size() >= __n)
00529 {
00530
std::copy_backward(__position, end(),
00531 this->_M_impl._M_finish
00532 + difference_type(__n));
00533
std::copy(__first, __last, __position);
00534 this->_M_impl._M_finish += difference_type(__n);
00535 }
00536
else
00537 {
00538
const size_type __len = size() +
std::max(size(), __n);
00539 _Bit_type * __q = this->_M_allocate(__len);
00540 iterator __i =
std::copy(begin(), __position,
00541 iterator(__q, 0));
00542 __i =
std::copy(__first, __last, __i);
00543 this->_M_impl._M_finish =
std::copy(__position, end(), __i);
00544 this->_M_deallocate();
00545 this->_M_impl._M_end_of_storage = (__q
00546 + ((__len + _S_word_bit - 1)
00547 / _S_word_bit));
00548 this->_M_impl._M_start = iterator(__q, 0);
00549 }
00550 }
00551 }
00552
00553
public:
00554 iterator
00555 begin()
00556 {
return this->_M_impl._M_start; }
00557
00558 const_iterator
00559 begin()
const
00560
{
return this->_M_impl._M_start; }
00561
00562 iterator
00563 end()
00564 {
return this->_M_impl._M_finish; }
00565
00566 const_iterator
00567 end()
const
00568
{
return this->_M_impl._M_finish; }
00569
00570
reverse_iterator
00571 rbegin()
00572 {
return reverse_iterator(end()); }
00573
00574
const_reverse_iterator
00575 rbegin()
const
00576
{
return const_reverse_iterator(end()); }
00577
00578
reverse_iterator
00579 rend()
00580 {
return reverse_iterator(begin()); }
00581
00582
const_reverse_iterator
00583 rend()
const
00584
{
return const_reverse_iterator(begin()); }
00585
00586 size_type
00587 size()
const
00588
{
return size_type(end() - begin()); }
00589
00590 size_type
00591 max_size()
const
00592
{
return size_type(-1); }
00593
00594 size_type
00595 capacity()
const
00596
{
return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0)
00597 - begin()); }
00598
bool
00599 empty()
const
00600
{
return begin() == end(); }
00601
00602 reference
00603 operator[](size_type __n)
00604 {
return *(begin() + difference_type(__n)); }
00605
00606 const_reference
00607 operator[](size_type __n)
const
00608
{
return *(begin() + difference_type(__n)); }
00609
00610
void
00611 _M_range_check(size_type __n)
const
00612
{
00613
if (__n >= this->size())
00614 __throw_out_of_range(__N(
"vector<bool>::_M_range_check"));
00615 }
00616
00617 reference
00618 at(size_type __n)
00619 { _M_range_check(__n);
return (*this)[__n]; }
00620
00621 const_reference
00622 at(size_type __n)
const
00623
{ _M_range_check(__n);
return (*this)[__n]; }
00624
00625
explicit
00626
vector(
const allocator_type& __a = allocator_type())
00627 : _Bvector_base<_Alloc>(__a) { }
00628
00629
vector(size_type __n,
bool __value,
00630
const allocator_type& __a = allocator_type())
00631 : _Bvector_base<_Alloc>(__a)
00632 {
00633 _M_initialize(__n);
00634
std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage,
00635 __value ? ~0 : 0);
00636 }
00637
00638
explicit
00639
vector(size_type __n)
00640 : _Bvector_base<_Alloc>(allocator_type())
00641 {
00642 _M_initialize(__n);
00643
std::fill(this->_M_impl._M_start._M_p,
00644 this->_M_impl._M_end_of_storage, 0);
00645 }
00646
00647
vector(
const vector& __x)
00648 : _Bvector_base<_Alloc>(__x.get_allocator())
00649 {
00650 _M_initialize(__x.
size());
00651
std::copy(__x.
begin(), __x.
end(), this->_M_impl._M_start);
00652 }
00653
00654
00655
template<
class _Integer>
00656
void
00657 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
00658 {
00659 _M_initialize(__n);
00660
std::fill(this->_M_impl._M_start._M_p,
00661 this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
00662 }
00663
00664
template<
class _InputIterator>
00665
void
00666 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
00667 __false_type)
00668 { _M_initialize_range(__first, __last,
00669 std::__iterator_category(__first)); }
00670
00671
template<
class _InputIterator>
00672
vector(_InputIterator __first, _InputIterator __last,
00673
const allocator_type& __a = allocator_type())
00674 : _Bvector_base<_Alloc>(__a)
00675 {
00676
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00677 _M_initialize_dispatch(__first, __last, _Integral());
00678 }
00679
00680 ~
vector() { }
00681
00682
vector&
00683 operator=(
const vector& __x)
00684 {
00685
if (&__x ==
this)
00686
return *
this;
00687
if (__x.
size() > capacity())
00688 {
00689 this->_M_deallocate();
00690 _M_initialize(__x.
size());
00691 }
00692
std::copy(__x.
begin(), __x.
end(), begin());
00693 this->_M_impl._M_finish = begin() + difference_type(__x.
size());
00694
return *
this;
00695 }
00696
00697
00698
00699
00700
00701
00702
void
00703 _M_fill_assign(size_t __n,
bool __x)
00704 {
00705
if (__n > size())
00706 {
00707
std::fill(this->_M_impl._M_start._M_p,
00708 this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
00709 insert(end(), __n - size(), __x);
00710 }
00711
else
00712 {
00713 erase(begin() + __n, end());
00714
std::fill(this->_M_impl._M_start._M_p,
00715 this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
00716 }
00717 }
00718
00719
void
00720 assign(size_t __n,
bool __x)
00721 { _M_fill_assign(__n, __x); }
00722
00723
template<
class _InputIterator>
00724
void
00725 assign(_InputIterator __first, _InputIterator __last)
00726 {
00727
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00728 _M_assign_dispatch(__first, __last, _Integral());
00729 }
00730
00731
template<
class _Integer>
00732
void
00733 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
00734 { _M_fill_assign((size_t) __n, (
bool) __val); }
00735
00736
template<
class _InputIterator>
00737
void
00738 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
00739 __false_type)
00740 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
00741
00742
template<
class _InputIterator>
00743
void
00744 _M_assign_aux(_InputIterator __first, _InputIterator __last,
00745
input_iterator_tag)
00746 {
00747 iterator __cur = begin();
00748
for (; __first != __last && __cur != end(); ++__cur, ++__first)
00749 *__cur = *__first;
00750
if (__first == __last)
00751 erase(__cur, end());
00752
else
00753 insert(end(), __first, __last);
00754 }
00755
00756
template<
class _ForwardIterator>
00757
void
00758 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
00759
forward_iterator_tag)
00760 {
00761
const size_type __len =
std::distance(__first, __last);
00762
if (__len < size())
00763 erase(std::copy(__first, __last, begin()), end());
00764
else
00765 {
00766 _ForwardIterator __mid = __first;
00767
std::advance(__mid, size());
00768
std::copy(__first, __mid, begin());
00769 insert(end(), __mid, __last);
00770 }
00771 }
00772
00773
void
00774 reserve(size_type __n)
00775 {
00776
if (__n > this->max_size())
00777 __throw_length_error(__N(
"vector::reserve"));
00778
if (this->capacity() < __n)
00779 {
00780 _Bit_type* __q = this->_M_allocate(__n);
00781 this->_M_impl._M_finish =
std::copy(begin(), end(),
00782 iterator(__q, 0));
00783 this->_M_deallocate();
00784 this->_M_impl._M_start = iterator(__q, 0);
00785 this->_M_impl._M_end_of_storage = (__q + (__n + _S_word_bit - 1)
00786 / _S_word_bit);
00787 }
00788 }
00789
00790 reference
00791 front()
00792 {
return *begin(); }
00793
00794 const_reference
00795 front()
const
00796
{
return *begin(); }
00797
00798 reference
00799 back()
00800 {
return *(end() - 1); }
00801
00802 const_reference
00803 back()
const
00804
{
return *(end() - 1); }
00805
00806
void
00807 push_back(
bool __x)
00808 {
00809
if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
00810 *this->_M_impl._M_finish++ = __x;
00811
else
00812 _M_insert_aux(end(), __x);
00813 }
00814
00815
void
00816
swap(
vector<bool, _Alloc>& __x)
00817 {
00818
std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
00819
std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
00820
std::swap(this->_M_impl._M_end_of_storage,
00821 __x._M_impl._M_end_of_storage);
00822 }
00823
00824
00825
static void
00826
swap(reference __x, reference __y)
00827 {
00828
bool __tmp = __x;
00829 __x = __y;
00830 __y = __tmp;
00831 }
00832
00833 iterator
00834 insert(iterator __position,
bool __x =
bool())
00835 {
00836
const difference_type __n = __position - begin();
00837
if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage
00838 && __position == end())
00839 *this->_M_impl._M_finish++ = __x;
00840
else
00841 _M_insert_aux(__position, __x);
00842
return begin() + __n;
00843 }
00844
00845
00846
00847
template<
class _Integer>
00848
void
00849 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
00850 __true_type)
00851 { _M_fill_insert(__pos, __n, __x); }
00852
00853
template<
class _InputIterator>
00854
void
00855 _M_insert_dispatch(iterator __pos,
00856 _InputIterator __first, _InputIterator __last,
00857 __false_type)
00858 { _M_insert_range(__pos, __first, __last,
00859 std::__iterator_category(__first)); }
00860
00861
template<
class _InputIterator>
00862
void
00863 insert(iterator __position,
00864 _InputIterator __first, _InputIterator __last)
00865 {
00866
typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
00867 _M_insert_dispatch(__position, __first, __last, _Integral());
00868 }
00869
00870
void
00871 _M_fill_insert(iterator __position, size_type __n,
bool __x)
00872 {
00873
if (__n == 0)
00874
return;
00875
if (capacity() - size() >= __n)
00876 {
00877
std::copy_backward(__position, end(),
00878 this->_M_impl._M_finish + difference_type(__n));
00879
std::fill(__position, __position + difference_type(__n), __x);
00880 this->_M_impl._M_finish += difference_type(__n);
00881 }
00882
else
00883 {
00884
const size_type __len = size() +
std::max(size(), __n);
00885 _Bit_type * __q = this->_M_allocate(__len);
00886 iterator __i =
std::copy(begin(), __position, iterator(__q, 0));
00887
std::fill_n(__i, __n, __x);
00888 this->_M_impl._M_finish =
std::copy(__position, end(),
00889 __i + difference_type(__n));
00890 this->_M_deallocate();
00891 this->_M_impl._M_end_of_storage = (__q + ((__len + _S_word_bit - 1)
00892 / _S_word_bit));
00893 this->_M_impl._M_start = iterator(__q, 0);
00894 }
00895 }
00896
00897
void
00898 insert(iterator __position, size_type __n,
bool __x)
00899 { _M_fill_insert(__position, __n, __x); }
00900
00901
void
00902 pop_back()
00903 { --this->_M_impl._M_finish; }
00904
00905 iterator
00906 erase(iterator __position)
00907 {
00908
if (__position + 1 != end())
00909
std::copy(__position + 1, end(), __position);
00910 --this->_M_impl._M_finish;
00911
return __position;
00912 }
00913
00914 iterator
00915 erase(iterator __first, iterator __last)
00916 {
00917 this->_M_impl._M_finish =
std::copy(__last, end(), __first);
00918
return __first;
00919 }
00920
00921
void
00922 resize(size_type __new_size,
bool __x =
bool())
00923 {
00924
if (__new_size < size())
00925 erase(begin() + difference_type(__new_size), end());
00926
else
00927 insert(end(), __new_size - size(), __x);
00928 }
00929
00930
void
00931 flip()
00932 {
00933
for (_Bit_type * __p = this->_M_impl._M_start._M_p;
00934 __p != this->_M_impl._M_end_of_storage; ++__p)
00935 *__p = ~*__p;
00936 }
00937
00938
void
00939 clear()
00940 { erase(begin(), end()); }
00941 };
00942 }
00943
00944
#endif