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 #ifndef _STL_BVECTOR_H
00058 #define _STL_BVECTOR_H 1
00059
00060 #include <initializer_list>
00061
00062 namespace std _GLIBCXX_VISIBILITY(default)
00063 {
00064 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
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 __n += int(_S_word_bit);
00147 --_M_p;
00148 }
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 (int(_S_word_bit) * (__x._M_p - __y._M_p)
00184 + __x._M_offset - __y._M_offset);
00185 }
00186
00187 struct _Bit_iterator : public _Bit_iterator_base
00188 {
00189 typedef _Bit_reference reference;
00190 typedef _Bit_reference* pointer;
00191 typedef _Bit_iterator iterator;
00192
00193 _Bit_iterator() : _Bit_iterator_base(0, 0) { }
00194
00195 _Bit_iterator(_Bit_type * __x, unsigned int __y)
00196 : _Bit_iterator_base(__x, __y) { }
00197
00198 reference
00199 operator*() const
00200 { return reference(_M_p, 1UL << _M_offset); }
00201
00202 iterator&
00203 operator++()
00204 {
00205 _M_bump_up();
00206 return *this;
00207 }
00208
00209 iterator
00210 operator++(int)
00211 {
00212 iterator __tmp = *this;
00213 _M_bump_up();
00214 return __tmp;
00215 }
00216
00217 iterator&
00218 operator--()
00219 {
00220 _M_bump_down();
00221 return *this;
00222 }
00223
00224 iterator
00225 operator--(int)
00226 {
00227 iterator __tmp = *this;
00228 _M_bump_down();
00229 return __tmp;
00230 }
00231
00232 iterator&
00233 operator+=(difference_type __i)
00234 {
00235 _M_incr(__i);
00236 return *this;
00237 }
00238
00239 iterator&
00240 operator-=(difference_type __i)
00241 {
00242 *this += -__i;
00243 return *this;
00244 }
00245
00246 iterator
00247 operator+(difference_type __i) const
00248 {
00249 iterator __tmp = *this;
00250 return __tmp += __i;
00251 }
00252
00253 iterator
00254 operator-(difference_type __i) const
00255 {
00256 iterator __tmp = *this;
00257 return __tmp -= __i;
00258 }
00259
00260 reference
00261 operator[](difference_type __i) const
00262 { return *(*this + __i); }
00263 };
00264
00265 inline _Bit_iterator
00266 operator+(ptrdiff_t __n, const _Bit_iterator& __x)
00267 { return __x + __n; }
00268
00269 struct _Bit_const_iterator : public _Bit_iterator_base
00270 {
00271 typedef bool reference;
00272 typedef bool const_reference;
00273 typedef const bool* pointer;
00274 typedef _Bit_const_iterator const_iterator;
00275
00276 _Bit_const_iterator() : _Bit_iterator_base(0, 0) { }
00277
00278 _Bit_const_iterator(_Bit_type * __x, unsigned int __y)
00279 : _Bit_iterator_base(__x, __y) { }
00280
00281 _Bit_const_iterator(const _Bit_iterator& __x)
00282 : _Bit_iterator_base(__x._M_p, __x._M_offset) { }
00283
00284 const_reference
00285 operator*() const
00286 { return _Bit_reference(_M_p, 1UL << _M_offset); }
00287
00288 const_iterator&
00289 operator++()
00290 {
00291 _M_bump_up();
00292 return *this;
00293 }
00294
00295 const_iterator
00296 operator++(int)
00297 {
00298 const_iterator __tmp = *this;
00299 _M_bump_up();
00300 return __tmp;
00301 }
00302
00303 const_iterator&
00304 operator--()
00305 {
00306 _M_bump_down();
00307 return *this;
00308 }
00309
00310 const_iterator
00311 operator--(int)
00312 {
00313 const_iterator __tmp = *this;
00314 _M_bump_down();
00315 return __tmp;
00316 }
00317
00318 const_iterator&
00319 operator+=(difference_type __i)
00320 {
00321 _M_incr(__i);
00322 return *this;
00323 }
00324
00325 const_iterator&
00326 operator-=(difference_type __i)
00327 {
00328 *this += -__i;
00329 return *this;
00330 }
00331
00332 const_iterator
00333 operator+(difference_type __i) const
00334 {
00335 const_iterator __tmp = *this;
00336 return __tmp += __i;
00337 }
00338
00339 const_iterator
00340 operator-(difference_type __i) const
00341 {
00342 const_iterator __tmp = *this;
00343 return __tmp -= __i;
00344 }
00345
00346 const_reference
00347 operator[](difference_type __i) const
00348 { return *(*this + __i); }
00349 };
00350
00351 inline _Bit_const_iterator
00352 operator+(ptrdiff_t __n, const _Bit_const_iterator& __x)
00353 { return __x + __n; }
00354
00355 inline void
00356 __fill_bvector(_Bit_iterator __first, _Bit_iterator __last, bool __x)
00357 {
00358 for (; __first != __last; ++__first)
00359 *__first = __x;
00360 }
00361
00362 inline void
00363 fill(_Bit_iterator __first, _Bit_iterator __last, const bool& __x)
00364 {
00365 if (__first._M_p != __last._M_p)
00366 {
00367 std::fill(__first._M_p + 1, __last._M_p, __x ? ~0 : 0);
00368 __fill_bvector(__first, _Bit_iterator(__first._M_p + 1, 0), __x);
00369 __fill_bvector(_Bit_iterator(__last._M_p, 0), __last, __x);
00370 }
00371 else
00372 __fill_bvector(__first, __last, __x);
00373 }
00374
00375 template<typename _Alloc>
00376 struct _Bvector_base
00377 {
00378 typedef typename _Alloc::template rebind<_Bit_type>::other
00379 _Bit_alloc_type;
00380
00381 struct _Bvector_impl
00382 : public _Bit_alloc_type
00383 {
00384 _Bit_iterator _M_start;
00385 _Bit_iterator _M_finish;
00386 _Bit_type* _M_end_of_storage;
00387
00388 _Bvector_impl()
00389 : _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage(0)
00390 { }
00391
00392 _Bvector_impl(const _Bit_alloc_type& __a)
00393 : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage(0)
00394 { }
00395 };
00396
00397 public:
00398 typedef _Alloc allocator_type;
00399
00400 _Bit_alloc_type&
00401 _M_get_Bit_allocator()
00402 { return *static_cast<_Bit_alloc_type*>(&this->_M_impl); }
00403
00404 const _Bit_alloc_type&
00405 _M_get_Bit_allocator() const
00406 { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); }
00407
00408 allocator_type
00409 get_allocator() const
00410 { return allocator_type(_M_get_Bit_allocator()); }
00411
00412 _Bvector_base()
00413 : _M_impl() { }
00414
00415 _Bvector_base(const allocator_type& __a)
00416 : _M_impl(__a) { }
00417
00418 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00419 _Bvector_base(_Bvector_base&& __x)
00420 : _M_impl(__x._M_get_Bit_allocator())
00421 {
00422 this->_M_impl._M_start = __x._M_impl._M_start;
00423 this->_M_impl._M_finish = __x._M_impl._M_finish;
00424 this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage;
00425 __x._M_impl._M_start = _Bit_iterator();
00426 __x._M_impl._M_finish = _Bit_iterator();
00427 __x._M_impl._M_end_of_storage = 0;
00428 }
00429 #endif
00430
00431 ~_Bvector_base()
00432 { this->_M_deallocate(); }
00433
00434 protected:
00435 _Bvector_impl _M_impl;
00436
00437 _Bit_type*
00438 _M_allocate(size_t __n)
00439 { return _M_impl.allocate((__n + int(_S_word_bit) - 1)
00440 / int(_S_word_bit)); }
00441
00442 void
00443 _M_deallocate()
00444 {
00445 if (_M_impl._M_start._M_p)
00446 _M_impl.deallocate(_M_impl._M_start._M_p,
00447 _M_impl._M_end_of_storage - _M_impl._M_start._M_p);
00448 }
00449 };
00450
00451 _GLIBCXX_END_NAMESPACE_CONTAINER
00452 }
00453
00454
00455 #include <bits/stl_vector.h>
00456
00457 namespace std _GLIBCXX_VISIBILITY(default)
00458 {
00459 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00460
00461
00462
00463
00464
00465
00466
00467
00468
00469
00470
00471
00472
00473
00474
00475
00476
00477
00478 template<typename _Alloc>
00479 class vector<bool, _Alloc> : protected _Bvector_base<_Alloc>
00480 {
00481 typedef _Bvector_base<_Alloc> _Base;
00482
00483 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00484 template<typename> friend class hash;
00485 #endif
00486
00487 public:
00488 typedef bool value_type;
00489 typedef size_t size_type;
00490 typedef ptrdiff_t difference_type;
00491 typedef _Bit_reference reference;
00492 typedef bool const_reference;
00493 typedef _Bit_reference* pointer;
00494 typedef const bool* const_pointer;
00495 typedef _Bit_iterator iterator;
00496 typedef _Bit_const_iterator const_iterator;
00497 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00498 typedef std::reverse_iterator<iterator> reverse_iterator;
00499 typedef _Alloc allocator_type;
00500
00501 allocator_type get_allocator() const
00502 { return _Base::get_allocator(); }
00503
00504 protected:
00505 using _Base::_M_allocate;
00506 using _Base::_M_deallocate;
00507 using _Base::_M_get_Bit_allocator;
00508
00509 public:
00510 vector()
00511 : _Base() { }
00512
00513 explicit
00514 vector(const allocator_type& __a)
00515 : _Base(__a) { }
00516
00517 explicit
00518 vector(size_type __n, const bool& __value = bool(),
00519 const allocator_type& __a = allocator_type())
00520 : _Base(__a)
00521 {
00522 _M_initialize(__n);
00523 std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage,
00524 __value ? ~0 : 0);
00525 }
00526
00527 vector(const vector& __x)
00528 : _Base(__x._M_get_Bit_allocator())
00529 {
00530 _M_initialize(__x.size());
00531 _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start);
00532 }
00533
00534 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00535 vector(vector&& __x)
00536 : _Base(std::move(__x)) { }
00537
00538 vector(initializer_list<bool> __l,
00539 const allocator_type& __a = allocator_type())
00540 : _Base(__a)
00541 {
00542 _M_initialize_range(__l.begin(), __l.end(),
00543 random_access_iterator_tag());
00544 }
00545 #endif
00546
00547 template<typename _InputIterator>
00548 vector(_InputIterator __first, _InputIterator __last,
00549 const allocator_type& __a = allocator_type())
00550 : _Base(__a)
00551 {
00552 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00553 _M_initialize_dispatch(__first, __last, _Integral());
00554 }
00555
00556 ~vector() { }
00557
00558 vector&
00559 operator=(const vector& __x)
00560 {
00561 if (&__x == this)
00562 return *this;
00563 if (__x.size() > capacity())
00564 {
00565 this->_M_deallocate();
00566 _M_initialize(__x.size());
00567 }
00568 this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(),
00569 begin());
00570 return *this;
00571 }
00572
00573 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00574 vector&
00575 operator=(vector&& __x)
00576 {
00577
00578
00579 this->clear();
00580 this->swap(__x);
00581 return *this;
00582 }
00583
00584 vector&
00585 operator=(initializer_list<bool> __l)
00586 {
00587 this->assign (__l.begin(), __l.end());
00588 return *this;
00589 }
00590 #endif
00591
00592
00593
00594
00595
00596 void
00597 assign(size_type __n, const bool& __x)
00598 { _M_fill_assign(__n, __x); }
00599
00600 template<typename _InputIterator>
00601 void
00602 assign(_InputIterator __first, _InputIterator __last)
00603 {
00604 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00605 _M_assign_dispatch(__first, __last, _Integral());
00606 }
00607
00608 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00609 void
00610 assign(initializer_list<bool> __l)
00611 { this->assign(__l.begin(), __l.end()); }
00612 #endif
00613
00614 iterator
00615 begin()
00616 { return this->_M_impl._M_start; }
00617
00618 const_iterator
00619 begin() const
00620 { return this->_M_impl._M_start; }
00621
00622 iterator
00623 end()
00624 { return this->_M_impl._M_finish; }
00625
00626 const_iterator
00627 end() const
00628 { return this->_M_impl._M_finish; }
00629
00630 reverse_iterator
00631 rbegin()
00632 { return reverse_iterator(end()); }
00633
00634 const_reverse_iterator
00635 rbegin() const
00636 { return const_reverse_iterator(end()); }
00637
00638 reverse_iterator
00639 rend()
00640 { return reverse_iterator(begin()); }
00641
00642 const_reverse_iterator
00643 rend() const
00644 { return const_reverse_iterator(begin()); }
00645
00646 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00647 const_iterator
00648 cbegin() const
00649 { return this->_M_impl._M_start; }
00650
00651 const_iterator
00652 cend() const
00653 { return this->_M_impl._M_finish; }
00654
00655 const_reverse_iterator
00656 crbegin() const
00657 { return const_reverse_iterator(end()); }
00658
00659 const_reverse_iterator
00660 crend() const
00661 { return const_reverse_iterator(begin()); }
00662 #endif
00663
00664 size_type
00665 size() const
00666 { return size_type(end() - begin()); }
00667
00668 size_type
00669 max_size() const
00670 {
00671 const size_type __isize =
00672 __gnu_cxx::__numeric_traits<difference_type>::__max
00673 - int(_S_word_bit) + 1;
00674 const size_type __asize = _M_get_Bit_allocator().max_size();
00675 return (__asize <= __isize / int(_S_word_bit)
00676 ? __asize * int(_S_word_bit) : __isize);
00677 }
00678
00679 size_type
00680 capacity() const
00681 { return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0)
00682 - begin()); }
00683
00684 bool
00685 empty() const
00686 { return begin() == end(); }
00687
00688 reference
00689 operator[](size_type __n)
00690 {
00691 return *iterator(this->_M_impl._M_start._M_p
00692 + __n / int(_S_word_bit), __n % int(_S_word_bit));
00693 }
00694
00695 const_reference
00696 operator[](size_type __n) const
00697 {
00698 return *const_iterator(this->_M_impl._M_start._M_p
00699 + __n / int(_S_word_bit), __n % int(_S_word_bit));
00700 }
00701
00702 protected:
00703 void
00704 _M_range_check(size_type __n) const
00705 {
00706 if (__n >= this->size())
00707 __throw_out_of_range(__N("vector<bool>::_M_range_check"));
00708 }
00709
00710 public:
00711 reference
00712 at(size_type __n)
00713 { _M_range_check(__n); return (*this)[__n]; }
00714
00715 const_reference
00716 at(size_type __n) const
00717 { _M_range_check(__n); return (*this)[__n]; }
00718
00719 void
00720 reserve(size_type __n);
00721
00722 reference
00723 front()
00724 { return *begin(); }
00725
00726 const_reference
00727 front() const
00728 { return *begin(); }
00729
00730 reference
00731 back()
00732 { return *(end() - 1); }
00733
00734 const_reference
00735 back() const
00736 { return *(end() - 1); }
00737
00738
00739
00740
00741
00742
00743 void
00744 data() { }
00745
00746 void
00747 push_back(bool __x)
00748 {
00749 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage)
00750 *this->_M_impl._M_finish++ = __x;
00751 else
00752 _M_insert_aux(end(), __x);
00753 }
00754
00755 void
00756 swap(vector& __x)
00757 {
00758 std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
00759 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
00760 std::swap(this->_M_impl._M_end_of_storage,
00761 __x._M_impl._M_end_of_storage);
00762
00763
00764
00765 std::__alloc_swap<typename _Base::_Bit_alloc_type>::
00766 _S_do_it(_M_get_Bit_allocator(), __x._M_get_Bit_allocator());
00767 }
00768
00769
00770 static void
00771 swap(reference __x, reference __y)
00772 {
00773 bool __tmp = __x;
00774 __x = __y;
00775 __y = __tmp;
00776 }
00777
00778 iterator
00779 insert(iterator __position, const bool& __x = bool())
00780 {
00781 const difference_type __n = __position - begin();
00782 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage
00783 && __position == end())
00784 *this->_M_impl._M_finish++ = __x;
00785 else
00786 _M_insert_aux(__position, __x);
00787 return begin() + __n;
00788 }
00789
00790 template<typename _InputIterator>
00791 void
00792 insert(iterator __position,
00793 _InputIterator __first, _InputIterator __last)
00794 {
00795 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00796 _M_insert_dispatch(__position, __first, __last, _Integral());
00797 }
00798
00799 void
00800 insert(iterator __position, size_type __n, const bool& __x)
00801 { _M_fill_insert(__position, __n, __x); }
00802
00803 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00804 void insert(iterator __p, initializer_list<bool> __l)
00805 { this->insert(__p, __l.begin(), __l.end()); }
00806 #endif
00807
00808 void
00809 pop_back()
00810 { --this->_M_impl._M_finish; }
00811
00812 iterator
00813 erase(iterator __position)
00814 {
00815 if (__position + 1 != end())
00816 std::copy(__position + 1, end(), __position);
00817 --this->_M_impl._M_finish;
00818 return __position;
00819 }
00820
00821 iterator
00822 erase(iterator __first, iterator __last)
00823 {
00824 _M_erase_at_end(std::copy(__last, end(), __first));
00825 return __first;
00826 }
00827
00828 void
00829 resize(size_type __new_size, bool __x = bool())
00830 {
00831 if (__new_size < size())
00832 _M_erase_at_end(begin() + difference_type(__new_size));
00833 else
00834 insert(end(), __new_size - size(), __x);
00835 }
00836
00837 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00838 void
00839 shrink_to_fit()
00840 { std::__shrink_to_fit<vector>::_S_do_it(*this); }
00841 #endif
00842
00843 void
00844 flip()
00845 {
00846 for (_Bit_type * __p = this->_M_impl._M_start._M_p;
00847 __p != this->_M_impl._M_end_of_storage; ++__p)
00848 *__p = ~*__p;
00849 }
00850
00851 void
00852 clear()
00853 { _M_erase_at_end(begin()); }
00854
00855
00856 protected:
00857
00858 iterator
00859 _M_copy_aligned(const_iterator __first, const_iterator __last,
00860 iterator __result)
00861 {
00862 _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p);
00863 return std::copy(const_iterator(__last._M_p, 0), __last,
00864 iterator(__q, 0));
00865 }
00866
00867 void
00868 _M_initialize(size_type __n)
00869 {
00870 _Bit_type* __q = this->_M_allocate(__n);
00871 this->_M_impl._M_end_of_storage = (__q
00872 + ((__n + int(_S_word_bit) - 1)
00873 / int(_S_word_bit)));
00874 this->_M_impl._M_start = iterator(__q, 0);
00875 this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n);
00876 }
00877
00878
00879
00880
00881
00882 template<typename _Integer>
00883 void
00884 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
00885 {
00886 _M_initialize(static_cast<size_type>(__n));
00887 std::fill(this->_M_impl._M_start._M_p,
00888 this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
00889 }
00890
00891 template<typename _InputIterator>
00892 void
00893 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
00894 __false_type)
00895 { _M_initialize_range(__first, __last,
00896 std::__iterator_category(__first)); }
00897
00898 template<typename _InputIterator>
00899 void
00900 _M_initialize_range(_InputIterator __first, _InputIterator __last,
00901 std::input_iterator_tag)
00902 {
00903 for (; __first != __last; ++__first)
00904 push_back(*__first);
00905 }
00906
00907 template<typename _ForwardIterator>
00908 void
00909 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last,
00910 std::forward_iterator_tag)
00911 {
00912 const size_type __n = std::distance(__first, __last);
00913 _M_initialize(__n);
00914 std::copy(__first, __last, this->_M_impl._M_start);
00915 }
00916
00917
00918
00919 template<typename _Integer>
00920 void
00921 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
00922 { _M_fill_assign(__n, __val); }
00923
00924 template<class _InputIterator>
00925 void
00926 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
00927 __false_type)
00928 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); }
00929
00930 void
00931 _M_fill_assign(size_t __n, bool __x)
00932 {
00933 if (__n > size())
00934 {
00935 std::fill(this->_M_impl._M_start._M_p,
00936 this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
00937 insert(end(), __n - size(), __x);
00938 }
00939 else
00940 {
00941 _M_erase_at_end(begin() + __n);
00942 std::fill(this->_M_impl._M_start._M_p,
00943 this->_M_impl._M_end_of_storage, __x ? ~0 : 0);
00944 }
00945 }
00946
00947 template<typename _InputIterator>
00948 void
00949 _M_assign_aux(_InputIterator __first, _InputIterator __last,
00950 std::input_iterator_tag)
00951 {
00952 iterator __cur = begin();
00953 for (; __first != __last && __cur != end(); ++__cur, ++__first)
00954 *__cur = *__first;
00955 if (__first == __last)
00956 _M_erase_at_end(__cur);
00957 else
00958 insert(end(), __first, __last);
00959 }
00960
00961 template<typename _ForwardIterator>
00962 void
00963 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
00964 std::forward_iterator_tag)
00965 {
00966 const size_type __len = std::distance(__first, __last);
00967 if (__len < size())
00968 _M_erase_at_end(std::copy(__first, __last, begin()));
00969 else
00970 {
00971 _ForwardIterator __mid = __first;
00972 std::advance(__mid, size());
00973 std::copy(__first, __mid, begin());
00974 insert(end(), __mid, __last);
00975 }
00976 }
00977
00978
00979
00980
00981
00982 template<typename _Integer>
00983 void
00984 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
00985 __true_type)
00986 { _M_fill_insert(__pos, __n, __x); }
00987
00988 template<typename _InputIterator>
00989 void
00990 _M_insert_dispatch(iterator __pos,
00991 _InputIterator __first, _InputIterator __last,
00992 __false_type)
00993 { _M_insert_range(__pos, __first, __last,
00994 std::__iterator_category(__first)); }
00995
00996 void
00997 _M_fill_insert(iterator __position, size_type __n, bool __x);
00998
00999 template<typename _InputIterator>
01000 void
01001 _M_insert_range(iterator __pos, _InputIterator __first,
01002 _InputIterator __last, std::input_iterator_tag)
01003 {
01004 for (; __first != __last; ++__first)
01005 {
01006 __pos = insert(__pos, *__first);
01007 ++__pos;
01008 }
01009 }
01010
01011 template<typename _ForwardIterator>
01012 void
01013 _M_insert_range(iterator __position, _ForwardIterator __first,
01014 _ForwardIterator __last, std::forward_iterator_tag);
01015
01016 void
01017 _M_insert_aux(iterator __position, bool __x);
01018
01019 size_type
01020 _M_check_len(size_type __n, const char* __s) const
01021 {
01022 if (max_size() - size() < __n)
01023 __throw_length_error(__N(__s));
01024
01025 const size_type __len = size() + std::max(size(), __n);
01026 return (__len < size() || __len > max_size()) ? max_size() : __len;
01027 }
01028
01029 void
01030 _M_erase_at_end(iterator __pos)
01031 { this->_M_impl._M_finish = __pos; }
01032 };
01033
01034 _GLIBCXX_END_NAMESPACE_CONTAINER
01035 }
01036
01037 #ifdef __GXX_EXPERIMENTAL_CXX0X__
01038
01039 #include <bits/functional_hash.h>
01040
01041 namespace std _GLIBCXX_VISIBILITY(default)
01042 {
01043 _GLIBCXX_BEGIN_NAMESPACE_VERSION
01044
01045
01046
01047 template<typename _Alloc>
01048 struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>
01049 : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>>
01050 {
01051 size_t
01052 operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const;
01053 };
01054
01055 _GLIBCXX_END_NAMESPACE_VERSION
01056 }
01057
01058 #endif // __GXX_EXPERIMENTAL_CXX0X__
01059
01060 #endif