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 std::__is_integer<_InputIterator>::__type _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 std::__is_integer<_InputIterator>::__type _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 std::__is_integer<_InputIterator>::__type _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