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