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
00062 #ifndef _STL_BVECTOR_H
00063 #define _STL_BVECTOR_H 1
00064
00065 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
00066
00067 typedef unsigned long _Bit_type;
00068 enum { _S_word_bit = int(__CHAR_BIT__ * sizeof(_Bit_type)) };
00069
00070 struct _Bit_reference
00071 {
00072 _Bit_type * _M_p;
00073 _Bit_type _M_mask;
00074
00075 _Bit_reference(_Bit_type * __x, _Bit_type __y)
00076 : _M_p(__x), _M_mask(__y) { }
00077
00078 _Bit_reference() : _M_p(0), _M_mask(0) { }
00079
00080 operator bool() const
00081 { return !!(*_M_p & _M_mask); }
00082
00083 _Bit_reference&
00084 operator=(bool __x)
00085 {
00086 if (__x)
00087 *_M_p |= _M_mask;
00088 else
00089 *_M_p &= ~_M_mask;
00090 return *this;
00091 }
00092
00093 _Bit_reference&
00094 operator=(const _Bit_reference& __x)
00095 { return *this = bool(__x); }
00096
00097 bool
00098 operator==(const _Bit_reference& __x) const
00099 { return bool(*this) == bool(__x); }
00100
00101 bool
00102 operator<(const _Bit_reference& __x) const
00103 { return !bool(*this) && bool(__x); }
00104
00105 void
00106 flip()
00107 { *_M_p ^= _M_mask; }
00108 };
00109
00110 struct _Bit_iterator_base
00111 : public std::iterator<std::random_access_iterator_tag, bool>
00112 {
00113 _Bit_type * _M_p;
00114 unsigned int _M_offset;
00115
00116 _Bit_iterator_base(_Bit_type * __x, unsigned int __y)
00117 : _M_p(__x), _M_offset(__y) { }
00118
00119 void
00120 _M_bump_up()
00121 {
00122 if (_M_offset++ == int(_S_word_bit) - 1)
00123 {
00124 _M_offset = 0;
00125 ++_M_p;
00126 }
00127 }
00128
00129 void
00130 _M_bump_down()
00131 {
00132 if (_M_offset-- == 0)
00133 {
00134 _M_offset = int(_S_word_bit) - 1;
00135 --_M_p;
00136 }
00137 }
00138
00139 void
00140 _M_incr(ptrdiff_t __i)
00141 {
00142 difference_type __n = __i + _M_offset;
00143 _M_p += __n / int(_S_word_bit);
00144 __n = __n % int(_S_word_bit);
00145 if (__n < 0)
00146 {
00147 __n += int(_S_word_bit);
00148 --_M_p;
00149 }
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 inline void
00357 __fill_bvector(_Bit_iterator __first, _Bit_iterator __last, bool __x)
00358 {
00359 for (; __first != __last; ++__first)
00360 *__first = __x;
00361 }
00362
00363 inline void
00364 fill(_Bit_iterator __first, _Bit_iterator __last, const bool& __x)
00365 {
00366 if (__first._M_p != __last._M_p)
00367 {
00368 std::fill(__first._M_p + 1, __last._M_p, __x ? ~0 : 0);
00369 __fill_bvector(__first, _Bit_iterator(__first._M_p + 1, 0), __x);
00370 __fill_bvector(_Bit_iterator(__last._M_p, 0), __last, __x);
00371 }
00372 else
00373 __fill_bvector(__first, __last, __x);
00374 }
00375
00376 template<typename _Alloc>
00377 struct _Bvector_base
00378 {
00379 typedef typename _Alloc::template rebind<_Bit_type>::other
00380 _Bit_alloc_type;
00381
00382 struct _Bvector_impl
00383 : public _Bit_alloc_type
00384 {
00385 _Bit_iterator _M_start;
00386 _Bit_iterator _M_finish;
00387 _Bit_type* _M_end_of_storage;
00388
00389 _Bvector_impl()
00390 : _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage(0)
00391 { }
00392
00393 _Bvector_impl(const _Bit_alloc_type& __a)
00394 : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage(0)
00395 { }
00396 };
00397
00398 public:
00399 typedef _Alloc allocator_type;
00400
00401 _Bit_alloc_type&
00402 _M_get_Bit_allocator()
00403 { return *static_cast<_Bit_alloc_type*>(&this->_M_impl); }
00404
00405 const _Bit_alloc_type&
00406 _M_get_Bit_allocator() const
00407 { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); }
00408
00409 allocator_type
00410 get_allocator() const
00411 { return allocator_type(_M_get_Bit_allocator()); }
00412
00413 _Bvector_base()
00414 : _M_impl() { }
00415
00416 _Bvector_base(const allocator_type& __a)
00417 : _M_impl(__a) { }
00418
00419 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00420 _Bvector_base(_Bvector_base&& __x)
00421 : _M_impl(__x._M_get_Bit_allocator())
00422 {
00423 this->_M_impl._M_start = __x._M_impl._M_start;
00424 this->_M_impl._M_finish = __x._M_impl._M_finish;
00425 this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage;
00426 __x._M_impl._M_start = _Bit_iterator();
00427 __x._M_impl._M_finish = _Bit_iterator();
00428 __x._M_impl._M_end_of_storage = 0;
00429 }
00430 #endif
00431
00432 ~_Bvector_base()
00433 { this->_M_deallocate(); }
00434
00435 protected:
00436 _Bvector_impl _M_impl;
00437
00438 _Bit_type*
00439 _M_allocate(size_t __n)
00440 { return _M_impl.allocate((__n + int(_S_word_bit) - 1)
00441 / int(_S_word_bit)); }
00442
00443 void
00444 _M_deallocate()
00445 {
00446 if (_M_impl._M_start._M_p)
00447 _M_impl.deallocate(_M_impl._M_start._M_p,
00448 _M_impl._M_end_of_storage - _M_impl._M_start._M_p);
00449 }
00450 };
00451
00452 _GLIBCXX_END_NESTED_NAMESPACE
00453
00454
00455 #include <bits/stl_vector.h>
00456
00457 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
00458
00459
00460
00461
00462
00463
00464
00465
00466
00467
00468
00469
00470
00471
00472
00473
00474
00475
00476
00477 template<typename _Alloc>
00478 class vector<bool, _Alloc> : protected _Bvector_base<_Alloc>
00479 {
00480 typedef _Bvector_base<_Alloc> _Base;
00481
00482 public:
00483 typedef bool value_type;
00484 typedef size_t size_type;
00485 typedef ptrdiff_t difference_type;
00486 typedef _Bit_reference reference;
00487 typedef bool const_reference;
00488 typedef _Bit_reference* pointer;
00489 typedef const bool* const_pointer;
00490 typedef _Bit_iterator iterator;
00491 typedef _Bit_const_iterator const_iterator;
00492 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00493 typedef std::reverse_iterator<iterator> reverse_iterator;
00494 typedef _Alloc allocator_type;
00495
00496 allocator_type get_allocator() const
00497 { return _Base::get_allocator(); }
00498
00499 protected:
00500 using _Base::_M_allocate;
00501 using _Base::_M_deallocate;
00502 using _Base::_M_get_Bit_allocator;
00503
00504 public:
00505 vector()
00506 : _Base() { }
00507
00508 explicit
00509 vector(const allocator_type& __a)
00510 : _Base(__a) { }
00511
00512 explicit
00513 vector(size_type __n, const bool& __value = bool(),
00514 const allocator_type& __a = allocator_type())
00515 : _Base(__a)
00516 {
00517 _M_initialize(__n);
00518 std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage,
00519 __value ? ~0 : 0);
00520 }
00521
00522 vector(const vector& __x)
00523 : _Base(__x._M_get_Bit_allocator())
00524 {
00525 _M_initialize(__x.size());
00526 _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start);
00527 }
00528
00529 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00530 vector(vector&& __x)
00531 : _Base(std::forward<_Base>(__x)) { }
00532 #endif
00533
00534 template<typename _InputIterator>
00535 vector(_InputIterator __first, _InputIterator __last,
00536 const allocator_type& __a = allocator_type())
00537 : _Base(__a)
00538 {
00539 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00540 _M_initialize_dispatch(__first, __last, _Integral());
00541 }
00542
00543 ~vector() { }
00544
00545 vector&
00546 operator=(const vector& __x)
00547 {
00548 if (&__x == this)
00549 return *this;
00550 if (__x.size() > capacity())
00551 {
00552 this->_M_deallocate();
00553 _M_initialize(__x.size());
00554 }
00555 this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(),
00556 begin());
00557 return *this;
00558 }
00559
00560 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00561 vector&
00562 operator=(vector&& __x)
00563 {
00564
00565 this->clear();
00566 this->swap(__x);
00567 return *this;
00568 }
00569 #endif
00570
00571
00572
00573
00574
00575 void
00576 assign(size_type __n, const bool& __x)
00577 { _M_fill_assign(__n, __x); }
00578
00579 template<typename _InputIterator>
00580 void
00581 assign(_InputIterator __first, _InputIterator __last)
00582 {
00583 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00584 _M_assign_dispatch(__first, __last, _Integral());
00585 }
00586
00587 iterator
00588 begin()
00589 { return this->_M_impl._M_start; }
00590
00591 const_iterator
00592 begin() const
00593 { return this->_M_impl._M_start; }
00594
00595 iterator
00596 end()
00597 { return this->_M_impl._M_finish; }
00598
00599 const_iterator
00600 end() const
00601 { return this->_M_impl._M_finish; }
00602
00603 reverse_iterator
00604 rbegin()
00605 { return reverse_iterator(end()); }
00606
00607 const_reverse_iterator
00608 rbegin() const
00609 { return const_reverse_iterator(end()); }
00610
00611 reverse_iterator
00612 rend()
00613 { return reverse_iterator(begin()); }
00614
00615 const_reverse_iterator
00616 rend() const
00617 { return const_reverse_iterator(begin()); }
00618
00619 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00620 const_iterator
00621 cbegin() const
00622 { return this->_M_impl._M_start; }
00623
00624 const_iterator
00625 cend() const
00626 { return this->_M_impl._M_finish; }
00627
00628 const_reverse_iterator
00629 crbegin() const
00630 { return const_reverse_iterator(end()); }
00631
00632 const_reverse_iterator
00633 crend() const
00634 { return const_reverse_iterator(begin()); }
00635 #endif
00636
00637 size_type
00638 size() const
00639 { return size_type(end() - begin()); }
00640
00641 size_type
00642 max_size() const
00643 {
00644 const size_type __isize =
00645 __gnu_cxx::__numeric_traits<difference_type>::__max
00646 - int(_S_word_bit) + 1;
00647 const size_type __asize = _M_get_Bit_allocator().max_size();
00648 return (__asize <= __isize / int(_S_word_bit)
00649 ? __asize * int(_S_word_bit) : __isize);
00650 }
00651
00652 size_type
00653 capacity() const
00654 { return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0)
00655 - begin()); }
00656
00657 bool
00658 empty() const
00659 { return begin() == end(); }
00660
00661 reference
00662 operator[](size_type __n)
00663 {
00664 return *iterator(this->_M_impl._M_start._M_p
00665 + __n / int(_S_word_bit), __n % int(_S_word_bit));
00666 }
00667
00668 const_reference
00669 operator[](size_type __n) const
00670 {
00671 return *const_iterator(this->_M_impl._M_start._M_p
00672 + __n / int(_S_word_bit), __n % int(_S_word_bit));
00673 }
00674
00675 protected:
00676 void
00677 _M_range_check(size_type __n) const
00678 {
00679 if (__n >= this->size())
00680 __throw_out_of_range(__N("vector<bool>::_M_range_check"));
00681 }
00682
00683 public:
00684 reference
00685 at(size_type __n)
00686 { _M_range_check(__n); return (*this)[__n]; }
00687
00688 const_reference
00689 at(size_type __n) const
00690 { _M_range_check(__n); return (*this)[__n]; }
00691
00692 void
00693 reserve(size_type __n);
00694
00695 reference
00696 front()
00697 { return *begin(); }
00698
00699 const_reference
00700 front() const
00701 { return *begin(); }
00702
00703 reference
00704 back()
00705 { return *(end() - 1); }
00706
00707 const_reference
00708 back() const
00709 { return *(end() - 1); }
00710
00711
00712
00713
00714
00715
00716 void
00717 data() { }
00718
00719 void
00720 push_back(bool __x)
00721 {
00722 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
00723 *this->_M_impl._M_finish++ = __x;
00724 else
00725 _M_insert_aux(end(), __x);
00726 }
00727
00728 void
00729 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00730 swap(vector&& __x)
00731 #else
00732 swap(vector& __x)
00733 #endif
00734 {
00735 std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
00736 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
00737 std::swap(this->_M_impl._M_end_of_storage,
00738 __x._M_impl._M_end_of_storage);
00739
00740
00741
00742 std::__alloc_swap<typename _Base::_Bit_alloc_type>::
00743 _S_do_it(_M_get_Bit_allocator(), __x._M_get_Bit_allocator());
00744 }
00745
00746
00747 static void
00748 swap(reference __x, reference __y)
00749 {
00750 bool __tmp = __x;
00751 __x = __y;
00752 __y = __tmp;
00753 }
00754
00755 iterator
00756 insert(iterator __position, const bool& __x = bool())
00757 {
00758 const difference_type __n = __position - begin();
00759 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage
00760 && __position == end())
00761 *this->_M_impl._M_finish++ = __x;
00762 else
00763 _M_insert_aux(__position, __x);
00764 return begin() + __n;
00765 }
00766
00767 template<typename _InputIterator>
00768 void
00769 insert(iterator __position,
00770 _InputIterator __first, _InputIterator __last)
00771 {
00772 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00773 _M_insert_dispatch(__position, __first, __last, _Integral());
00774 }
00775
00776 void
00777 insert(iterator __position, size_type __n, const bool& __x)
00778 { _M_fill_insert(__position, __n, __x); }
00779
00780 void
00781 pop_back()
00782 { --this->_M_impl._M_finish; }
00783
00784 iterator
00785 erase(iterator __position)
00786 {
00787 if (__position + 1 != end())
00788 std::copy(__position + 1, end(), __position);
00789 --this->_M_impl._M_finish;
00790 return __position;
00791 }
00792
00793 iterator
00794 erase(iterator __first, iterator __last)
00795 {
00796 _M_erase_at_end(std::copy(__last, end(), __first));
00797 return __first;
00798 }
00799
00800 void
00801 resize(size_type __new_size, bool __x = bool())
00802 {
00803 if (__new_size < size())
00804 _M_erase_at_end(begin() + difference_type(__new_size));
00805 else
00806 insert(end(), __new_size - size(), __x);
00807 }
00808
00809 void
00810 flip()
00811 {
00812 for (_Bit_type * __p = this->_M_impl._M_start._M_p;
00813 __p != this->_M_impl._M_end_of_storage; ++__p)
00814 *__p = ~*__p;
00815 }
00816
00817 void
00818 clear()
00819 { _M_erase_at_end(begin()); }
00820
00821
00822 protected:
00823
00824 iterator
00825 _M_copy_aligned(const_iterator __first, const_iterator __last,
00826 iterator __result)
00827 {
00828 _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p);
00829 return std::copy(const_iterator(__last._M_p, 0), __last,
00830 iterator(__q, 0));
00831 }
00832
00833 void
00834 _M_initialize(size_type __n)
00835 {
00836 _Bit_type* __q = this->_M_allocate(__n);
00837 this->_M_impl._M_end_of_storage = (__q
00838 + ((__n + int(_S_word_bit) - 1)
00839 / int(_S_word_bit)));
00840 this->_M_impl._M_start = iterator(__q, 0);
00841 this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n);
00842 }
00843
00844
00845
00846
00847
00848 template<typename _Integer>
00849 void
00850 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
00851 {
00852 _M_initialize(static_cast<size_type>(__n));
00853 std::fill(this->_M_impl._M_start._M_p,
00854 this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
00855 }
00856
00857 template<typename _InputIterator>
00858 void
00859 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
00860 __false_type)
00861 { _M_initialize_range(__first, __last,
00862 std::__iterator_category(__first)); }
00863
00864 template<typename _InputIterator>
00865 void
00866 _M_initialize_range(_InputIterator __first, _InputIterator __last,
00867 std::input_iterator_tag)
00868 {
00869 for (; __first != __last; ++__first)
00870 push_back(*__first);
00871 }
00872
00873 template<typename _ForwardIterator>
00874 void
00875 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
00876 std::forward_iterator_tag)
00877 {
00878 const size_type __n = std::distance(__first, __last);
00879 _M_initialize(__n);
00880 std::copy(__first, __last, this->_M_impl._M_start);
00881 }
00882
00883
00884
00885 template<typename _Integer>
00886 void
00887 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
00888 { _M_fill_assign(__n, __val); }
00889
00890 template<class _InputIterator>
00891 void
00892 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
00893 __false_type)
00894 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
00895
00896 void
00897 _M_fill_assign(size_t __n, bool __x)
00898 {
00899 if (__n > size())
00900 {
00901 std::fill(this->_M_impl._M_start._M_p,
00902 this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
00903 insert(end(), __n - size(), __x);
00904 }
00905 else
00906 {
00907 _M_erase_at_end(begin() + __n);
00908 std::fill(this->_M_impl._M_start._M_p,
00909 this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
00910 }
00911 }
00912
00913 template<typename _InputIterator>
00914 void
00915 _M_assign_aux(_InputIterator __first, _InputIterator __last,
00916 std::input_iterator_tag)
00917 {
00918 iterator __cur = begin();
00919 for (; __first != __last && __cur != end(); ++__cur, ++__first)
00920 *__cur = *__first;
00921 if (__first == __last)
00922 _M_erase_at_end(__cur);
00923 else
00924 insert(end(), __first, __last);
00925 }
00926
00927 template<typename _ForwardIterator>
00928 void
00929 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
00930 std::forward_iterator_tag)
00931 {
00932 const size_type __len = std::distance(__first, __last);
00933 if (__len < size())
00934 _M_erase_at_end(std::copy(__first, __last, begin()));
00935 else
00936 {
00937 _ForwardIterator __mid = __first;
00938 std::advance(__mid, size());
00939 std::copy(__first, __mid, begin());
00940 insert(end(), __mid, __last);
00941 }
00942 }
00943
00944
00945
00946
00947
00948 template<typename _Integer>
00949 void
00950 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
00951 __true_type)
00952 { _M_fill_insert(__pos, __n, __x); }
00953
00954 template<typename _InputIterator>
00955 void
00956 _M_insert_dispatch(iterator __pos,
00957 _InputIterator __first, _InputIterator __last,
00958 __false_type)
00959 { _M_insert_range(__pos, __first, __last,
00960 std::__iterator_category(__first)); }
00961
00962 void
00963 _M_fill_insert(iterator __position, size_type __n, bool __x);
00964
00965 template<typename _InputIterator>
00966 void
00967 _M_insert_range(iterator __pos, _InputIterator __first,
00968 _InputIterator __last, std::input_iterator_tag)
00969 {
00970 for (; __first != __last; ++__first)
00971 {
00972 __pos = insert(__pos, *__first);
00973 ++__pos;
00974 }
00975 }
00976
00977 template<typename _ForwardIterator>
00978 void
00979 _M_insert_range(iterator __position, _ForwardIterator __first,
00980 _ForwardIterator __last, std::forward_iterator_tag);
00981
00982 void
00983 _M_insert_aux(iterator __position, bool __x);
00984
00985 size_type
00986 _M_check_len(size_type __n, const char* __s) const
00987 {
00988 if (max_size() - size() < __n)
00989 __throw_length_error(__N(__s));
00990
00991 const size_type __len = size() + std::max(size(), __n);
00992 return (__len < size() || __len > max_size()) ? max_size() : __len;
00993 }
00994
00995 void
00996 _M_erase_at_end(iterator __pos)
00997 { this->_M_impl._M_finish = __pos; }
00998 };
00999
01000 _GLIBCXX_END_NESTED_NAMESPACE
01001
01002 #endif