libstdc++
|
00001 // vector<bool> specialization -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 3, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 /* 00027 * 00028 * Copyright (c) 1994 00029 * Hewlett-Packard Company 00030 * 00031 * Permission to use, copy, modify, distribute and sell this software 00032 * and its documentation for any purpose is hereby granted without fee, 00033 * provided that the above copyright notice appear in all copies and 00034 * that both that copyright notice and this permission notice appear 00035 * in supporting documentation. Hewlett-Packard Company makes no 00036 * representations about the suitability of this software for any 00037 * purpose. It is provided "as is" without express or implied warranty. 00038 * 00039 * 00040 * Copyright (c) 1996-1999 00041 * Silicon Graphics Computer Systems, Inc. 00042 * 00043 * Permission to use, copy, modify, distribute and sell this software 00044 * and its documentation for any purpose is hereby granted without fee, 00045 * provided that the above copyright notice appear in all copies and 00046 * that both that copyright notice and this permission notice appear 00047 * in supporting documentation. Silicon Graphics makes no 00048 * representations about the suitability of this software for any 00049 * purpose. It is provided "as is" without express or implied warranty. 00050 */ 00051 00052 /** @file stl_bvector.h 00053 * This is an internal header file, included by other library headers. 00054 * You should not attempt to use it directly. 00055 */ 00056 00057 #ifndef _STL_BVECTOR_H 00058 #define _STL_BVECTOR_H 1 00059 00060 #include <initializer_list> 00061 00062 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) 00063 00064 typedef unsigned long _Bit_type; 00065 enum { _S_word_bit = int(__CHAR_BIT__ * sizeof(_Bit_type)) }; 00066 00067 struct _Bit_reference 00068 { 00069 _Bit_type * _M_p; 00070 _Bit_type _M_mask; 00071 00072 _Bit_reference(_Bit_type * __x, _Bit_type __y) 00073 : _M_p(__x), _M_mask(__y) { } 00074 00075 _Bit_reference() : _M_p(0), _M_mask(0) { } 00076 00077 operator bool() const 00078 { return !!(*_M_p & _M_mask); } 00079 00080 _Bit_reference& 00081 operator=(bool __x) 00082 { 00083 if (__x) 00084 *_M_p |= _M_mask; 00085 else 00086 *_M_p &= ~_M_mask; 00087 return *this; 00088 } 00089 00090 _Bit_reference& 00091 operator=(const _Bit_reference& __x) 00092 { return *this = bool(__x); } 00093 00094 bool 00095 operator==(const _Bit_reference& __x) const 00096 { return bool(*this) == bool(__x); } 00097 00098 bool 00099 operator<(const _Bit_reference& __x) const 00100 { return !bool(*this) && bool(__x); } 00101 00102 void 00103 flip() 00104 { *_M_p ^= _M_mask; } 00105 }; 00106 00107 struct _Bit_iterator_base 00108 : public std::iterator<std::random_access_iterator_tag, bool> 00109 { 00110 _Bit_type * _M_p; 00111 unsigned int _M_offset; 00112 00113 _Bit_iterator_base(_Bit_type * __x, unsigned int __y) 00114 : _M_p(__x), _M_offset(__y) { } 00115 00116 void 00117 _M_bump_up() 00118 { 00119 if (_M_offset++ == int(_S_word_bit) - 1) 00120 { 00121 _M_offset = 0; 00122 ++_M_p; 00123 } 00124 } 00125 00126 void 00127 _M_bump_down() 00128 { 00129 if (_M_offset-- == 0) 00130 { 00131 _M_offset = int(_S_word_bit) - 1; 00132 --_M_p; 00133 } 00134 } 00135 00136 void 00137 _M_incr(ptrdiff_t __i) 00138 { 00139 difference_type __n = __i + _M_offset; 00140 _M_p += __n / int(_S_word_bit); 00141 __n = __n % int(_S_word_bit); 00142 if (__n < 0) 00143 { 00144 __n += int(_S_word_bit); 00145 --_M_p; 00146 } 00147 _M_offset = static_cast<unsigned int>(__n); 00148 } 00149 00150 bool 00151 operator==(const _Bit_iterator_base& __i) const 00152 { return _M_p == __i._M_p && _M_offset == __i._M_offset; } 00153 00154 bool 00155 operator<(const _Bit_iterator_base& __i) const 00156 { 00157 return _M_p < __i._M_p 00158 || (_M_p == __i._M_p && _M_offset < __i._M_offset); 00159 } 00160 00161 bool 00162 operator!=(const _Bit_iterator_base& __i) const 00163 { return !(*this == __i); } 00164 00165 bool 00166 operator>(const _Bit_iterator_base& __i) const 00167 { return __i < *this; } 00168 00169 bool 00170 operator<=(const _Bit_iterator_base& __i) const 00171 { return !(__i < *this); } 00172 00173 bool 00174 operator>=(const _Bit_iterator_base& __i) const 00175 { return !(*this < __i); } 00176 }; 00177 00178 inline ptrdiff_t 00179 operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 00180 { 00181 return (int(_S_word_bit) * (__x._M_p - __y._M_p) 00182 + __x._M_offset - __y._M_offset); 00183 } 00184 00185 struct _Bit_iterator : public _Bit_iterator_base 00186 { 00187 typedef _Bit_reference reference; 00188 typedef _Bit_reference* pointer; 00189 typedef _Bit_iterator iterator; 00190 00191 _Bit_iterator() : _Bit_iterator_base(0, 0) { } 00192 00193 _Bit_iterator(_Bit_type * __x, unsigned int __y) 00194 : _Bit_iterator_base(__x, __y) { } 00195 00196 reference 00197 operator*() const 00198 { return reference(_M_p, 1UL << _M_offset); } 00199 00200 iterator& 00201 operator++() 00202 { 00203 _M_bump_up(); 00204 return *this; 00205 } 00206 00207 iterator 00208 operator++(int) 00209 { 00210 iterator __tmp = *this; 00211 _M_bump_up(); 00212 return __tmp; 00213 } 00214 00215 iterator& 00216 operator--() 00217 { 00218 _M_bump_down(); 00219 return *this; 00220 } 00221 00222 iterator 00223 operator--(int) 00224 { 00225 iterator __tmp = *this; 00226 _M_bump_down(); 00227 return __tmp; 00228 } 00229 00230 iterator& 00231 operator+=(difference_type __i) 00232 { 00233 _M_incr(__i); 00234 return *this; 00235 } 00236 00237 iterator& 00238 operator-=(difference_type __i) 00239 { 00240 *this += -__i; 00241 return *this; 00242 } 00243 00244 iterator 00245 operator+(difference_type __i) const 00246 { 00247 iterator __tmp = *this; 00248 return __tmp += __i; 00249 } 00250 00251 iterator 00252 operator-(difference_type __i) const 00253 { 00254 iterator __tmp = *this; 00255 return __tmp -= __i; 00256 } 00257 00258 reference 00259 operator[](difference_type __i) const 00260 { return *(*this + __i); } 00261 }; 00262 00263 inline _Bit_iterator 00264 operator+(ptrdiff_t __n, const _Bit_iterator& __x) 00265 { return __x + __n; } 00266 00267 struct _Bit_const_iterator : public _Bit_iterator_base 00268 { 00269 typedef bool reference; 00270 typedef bool const_reference; 00271 typedef const bool* pointer; 00272 typedef _Bit_const_iterator const_iterator; 00273 00274 _Bit_const_iterator() : _Bit_iterator_base(0, 0) { } 00275 00276 _Bit_const_iterator(_Bit_type * __x, unsigned int __y) 00277 : _Bit_iterator_base(__x, __y) { } 00278 00279 _Bit_const_iterator(const _Bit_iterator& __x) 00280 : _Bit_iterator_base(__x._M_p, __x._M_offset) { } 00281 00282 const_reference 00283 operator*() const 00284 { return _Bit_reference(_M_p, 1UL << _M_offset); } 00285 00286 const_iterator& 00287 operator++() 00288 { 00289 _M_bump_up(); 00290 return *this; 00291 } 00292 00293 const_iterator 00294 operator++(int) 00295 { 00296 const_iterator __tmp = *this; 00297 _M_bump_up(); 00298 return __tmp; 00299 } 00300 00301 const_iterator& 00302 operator--() 00303 { 00304 _M_bump_down(); 00305 return *this; 00306 } 00307 00308 const_iterator 00309 operator--(int) 00310 { 00311 const_iterator __tmp = *this; 00312 _M_bump_down(); 00313 return __tmp; 00314 } 00315 00316 const_iterator& 00317 operator+=(difference_type __i) 00318 { 00319 _M_incr(__i); 00320 return *this; 00321 } 00322 00323 const_iterator& 00324 operator-=(difference_type __i) 00325 { 00326 *this += -__i; 00327 return *this; 00328 } 00329 00330 const_iterator 00331 operator+(difference_type __i) const 00332 { 00333 const_iterator __tmp = *this; 00334 return __tmp += __i; 00335 } 00336 00337 const_iterator 00338 operator-(difference_type __i) const 00339 { 00340 const_iterator __tmp = *this; 00341 return __tmp -= __i; 00342 } 00343 00344 const_reference 00345 operator[](difference_type __i) const 00346 { return *(*this + __i); } 00347 }; 00348 00349 inline _Bit_const_iterator 00350 operator+(ptrdiff_t __n, const _Bit_const_iterator& __x) 00351 { return __x + __n; } 00352 00353 inline void 00354 __fill_bvector(_Bit_iterator __first, _Bit_iterator __last, bool __x) 00355 { 00356 for (; __first != __last; ++__first) 00357 *__first = __x; 00358 } 00359 00360 inline void 00361 fill(_Bit_iterator __first, _Bit_iterator __last, const bool& __x) 00362 { 00363 if (__first._M_p != __last._M_p) 00364 { 00365 std::fill(__first._M_p + 1, __last._M_p, __x ? ~0 : 0); 00366 __fill_bvector(__first, _Bit_iterator(__first._M_p + 1, 0), __x); 00367 __fill_bvector(_Bit_iterator(__last._M_p, 0), __last, __x); 00368 } 00369 else 00370 __fill_bvector(__first, __last, __x); 00371 } 00372 00373 template<typename _Alloc> 00374 struct _Bvector_base 00375 { 00376 typedef typename _Alloc::template rebind<_Bit_type>::other 00377 _Bit_alloc_type; 00378 00379 struct _Bvector_impl 00380 : public _Bit_alloc_type 00381 { 00382 _Bit_iterator _M_start; 00383 _Bit_iterator _M_finish; 00384 _Bit_type* _M_end_of_storage; 00385 00386 _Bvector_impl() 00387 : _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage(0) 00388 { } 00389 00390 _Bvector_impl(const _Bit_alloc_type& __a) 00391 : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage(0) 00392 { } 00393 }; 00394 00395 public: 00396 typedef _Alloc allocator_type; 00397 00398 _Bit_alloc_type& 00399 _M_get_Bit_allocator() 00400 { return *static_cast<_Bit_alloc_type*>(&this->_M_impl); } 00401 00402 const _Bit_alloc_type& 00403 _M_get_Bit_allocator() const 00404 { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); } 00405 00406 allocator_type 00407 get_allocator() const 00408 { return allocator_type(_M_get_Bit_allocator()); } 00409 00410 _Bvector_base() 00411 : _M_impl() { } 00412 00413 _Bvector_base(const allocator_type& __a) 00414 : _M_impl(__a) { } 00415 00416 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00417 _Bvector_base(_Bvector_base&& __x) 00418 : _M_impl(__x._M_get_Bit_allocator()) 00419 { 00420 this->_M_impl._M_start = __x._M_impl._M_start; 00421 this->_M_impl._M_finish = __x._M_impl._M_finish; 00422 this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; 00423 __x._M_impl._M_start = _Bit_iterator(); 00424 __x._M_impl._M_finish = _Bit_iterator(); 00425 __x._M_impl._M_end_of_storage = 0; 00426 } 00427 #endif 00428 00429 ~_Bvector_base() 00430 { this->_M_deallocate(); } 00431 00432 protected: 00433 _Bvector_impl _M_impl; 00434 00435 _Bit_type* 00436 _M_allocate(size_t __n) 00437 { return _M_impl.allocate((__n + int(_S_word_bit) - 1) 00438 / int(_S_word_bit)); } 00439 00440 void 00441 _M_deallocate() 00442 { 00443 if (_M_impl._M_start._M_p) 00444 _M_impl.deallocate(_M_impl._M_start._M_p, 00445 _M_impl._M_end_of_storage - _M_impl._M_start._M_p); 00446 } 00447 }; 00448 00449 _GLIBCXX_END_NESTED_NAMESPACE 00450 00451 // Declare a partial specialization of vector<T, Alloc>. 00452 #include <bits/stl_vector.h> 00453 00454 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) 00455 00456 /** 00457 * @brief A specialization of vector for booleans which offers fixed time 00458 * access to individual elements in any order. 00459 * 00460 * Note that vector<bool> does not actually meet the requirements for being 00461 * a container. This is because the reference and pointer types are not 00462 * really references and pointers to bool. See DR96 for details. @see 00463 * vector for function documentation. 00464 * 00465 * @ingroup sequences 00466 * 00467 * In some terminology a %vector can be described as a dynamic 00468 * C-style array, it offers fast and efficient access to individual 00469 * elements in any order and saves the user from worrying about 00470 * memory and size allocation. Subscripting ( @c [] ) access is 00471 * also provided as with C-style arrays. 00472 */ 00473 template<typename _Alloc> 00474 class vector<bool, _Alloc> : protected _Bvector_base<_Alloc> 00475 { 00476 typedef _Bvector_base<_Alloc> _Base; 00477 00478 public: 00479 typedef bool value_type; 00480 typedef size_t size_type; 00481 typedef ptrdiff_t difference_type; 00482 typedef _Bit_reference reference; 00483 typedef bool const_reference; 00484 typedef _Bit_reference* pointer; 00485 typedef const bool* const_pointer; 00486 typedef _Bit_iterator iterator; 00487 typedef _Bit_const_iterator const_iterator; 00488 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00489 typedef std::reverse_iterator<iterator> reverse_iterator; 00490 typedef _Alloc allocator_type; 00491 00492 allocator_type get_allocator() const 00493 { return _Base::get_allocator(); } 00494 00495 protected: 00496 using _Base::_M_allocate; 00497 using _Base::_M_deallocate; 00498 using _Base::_M_get_Bit_allocator; 00499 00500 public: 00501 vector() 00502 : _Base() { } 00503 00504 explicit 00505 vector(const allocator_type& __a) 00506 : _Base(__a) { } 00507 00508 explicit 00509 vector(size_type __n, const bool& __value = bool(), 00510 const allocator_type& __a = allocator_type()) 00511 : _Base(__a) 00512 { 00513 _M_initialize(__n); 00514 std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage, 00515 __value ? ~0 : 0); 00516 } 00517 00518 vector(const vector& __x) 00519 : _Base(__x._M_get_Bit_allocator()) 00520 { 00521 _M_initialize(__x.size()); 00522 _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start); 00523 } 00524 00525 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00526 vector(vector&& __x) 00527 : _Base(std::forward<_Base>(__x)) { } 00528 00529 vector(initializer_list<bool> __l, 00530 const allocator_type& __a = allocator_type()) 00531 : _Base(__a) 00532 { 00533 _M_initialize_range(__l.begin(), __l.end(), 00534 random_access_iterator_tag()); 00535 } 00536 #endif 00537 00538 template<typename _InputIterator> 00539 vector(_InputIterator __first, _InputIterator __last, 00540 const allocator_type& __a = allocator_type()) 00541 : _Base(__a) 00542 { 00543 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00544 _M_initialize_dispatch(__first, __last, _Integral()); 00545 } 00546 00547 ~vector() { } 00548 00549 vector& 00550 operator=(const vector& __x) 00551 { 00552 if (&__x == this) 00553 return *this; 00554 if (__x.size() > capacity()) 00555 { 00556 this->_M_deallocate(); 00557 _M_initialize(__x.size()); 00558 } 00559 this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(), 00560 begin()); 00561 return *this; 00562 } 00563 00564 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00565 vector& 00566 operator=(vector&& __x) 00567 { 00568 // NB: DR 675. 00569 this->clear(); 00570 this->swap(__x); 00571 return *this; 00572 } 00573 00574 vector& 00575 operator=(initializer_list<bool> __l) 00576 { 00577 this->assign (__l.begin(), __l.end()); 00578 return *this; 00579 } 00580 #endif 00581 00582 // assign(), a generalized assignment member function. Two 00583 // versions: one that takes a count, and one that takes a range. 00584 // The range version is a member template, so we dispatch on whether 00585 // or not the type is an integer. 00586 void 00587 assign(size_type __n, const bool& __x) 00588 { _M_fill_assign(__n, __x); } 00589 00590 template<typename _InputIterator> 00591 void 00592 assign(_InputIterator __first, _InputIterator __last) 00593 { 00594 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00595 _M_assign_dispatch(__first, __last, _Integral()); 00596 } 00597 00598 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00599 void 00600 assign(initializer_list<bool> __l) 00601 { this->assign(__l.begin(), __l.end()); } 00602 #endif 00603 00604 iterator 00605 begin() 00606 { return this->_M_impl._M_start; } 00607 00608 const_iterator 00609 begin() const 00610 { return this->_M_impl._M_start; } 00611 00612 iterator 00613 end() 00614 { return this->_M_impl._M_finish; } 00615 00616 const_iterator 00617 end() const 00618 { return this->_M_impl._M_finish; } 00619 00620 reverse_iterator 00621 rbegin() 00622 { return reverse_iterator(end()); } 00623 00624 const_reverse_iterator 00625 rbegin() const 00626 { return const_reverse_iterator(end()); } 00627 00628 reverse_iterator 00629 rend() 00630 { return reverse_iterator(begin()); } 00631 00632 const_reverse_iterator 00633 rend() const 00634 { return const_reverse_iterator(begin()); } 00635 00636 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00637 const_iterator 00638 cbegin() const 00639 { return this->_M_impl._M_start; } 00640 00641 const_iterator 00642 cend() const 00643 { return this->_M_impl._M_finish; } 00644 00645 const_reverse_iterator 00646 crbegin() const 00647 { return const_reverse_iterator(end()); } 00648 00649 const_reverse_iterator 00650 crend() const 00651 { return const_reverse_iterator(begin()); } 00652 #endif 00653 00654 size_type 00655 size() const 00656 { return size_type(end() - begin()); } 00657 00658 size_type 00659 max_size() const 00660 { 00661 const size_type __isize = 00662 __gnu_cxx::__numeric_traits<difference_type>::__max 00663 - int(_S_word_bit) + 1; 00664 const size_type __asize = _M_get_Bit_allocator().max_size(); 00665 return (__asize <= __isize / int(_S_word_bit) 00666 ? __asize * int(_S_word_bit) : __isize); 00667 } 00668 00669 size_type 00670 capacity() const 00671 { return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0) 00672 - begin()); } 00673 00674 bool 00675 empty() const 00676 { return begin() == end(); } 00677 00678 reference 00679 operator[](size_type __n) 00680 { 00681 return *iterator(this->_M_impl._M_start._M_p 00682 + __n / int(_S_word_bit), __n % int(_S_word_bit)); 00683 } 00684 00685 const_reference 00686 operator[](size_type __n) const 00687 { 00688 return *const_iterator(this->_M_impl._M_start._M_p 00689 + __n / int(_S_word_bit), __n % int(_S_word_bit)); 00690 } 00691 00692 protected: 00693 void 00694 _M_range_check(size_type __n) const 00695 { 00696 if (__n >= this->size()) 00697 __throw_out_of_range(__N("vector<bool>::_M_range_check")); 00698 } 00699 00700 public: 00701 reference 00702 at(size_type __n) 00703 { _M_range_check(__n); return (*this)[__n]; } 00704 00705 const_reference 00706 at(size_type __n) const 00707 { _M_range_check(__n); return (*this)[__n]; } 00708 00709 void 00710 reserve(size_type __n); 00711 00712 reference 00713 front() 00714 { return *begin(); } 00715 00716 const_reference 00717 front() const 00718 { return *begin(); } 00719 00720 reference 00721 back() 00722 { return *(end() - 1); } 00723 00724 const_reference 00725 back() const 00726 { return *(end() - 1); } 00727 00728 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00729 // DR 464. Suggestion for new member functions in standard containers. 00730 // N.B. DR 464 says nothing about vector<bool> but we need something 00731 // here due to the way we are implementing DR 464 in the debug-mode 00732 // vector class. 00733 void 00734 data() { } 00735 00736 void 00737 push_back(bool __x) 00738 { 00739 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage) 00740 *this->_M_impl._M_finish++ = __x; 00741 else 00742 _M_insert_aux(end(), __x); 00743 } 00744 00745 void 00746 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00747 swap(vector&& __x) 00748 #else 00749 swap(vector& __x) 00750 #endif 00751 { 00752 std::swap(this->_M_impl._M_start, __x._M_impl._M_start); 00753 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); 00754 std::swap(this->_M_impl._M_end_of_storage, 00755 __x._M_impl._M_end_of_storage); 00756 00757 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00758 // 431. Swapping containers with unequal allocators. 00759 std::__alloc_swap<typename _Base::_Bit_alloc_type>:: 00760 _S_do_it(_M_get_Bit_allocator(), __x._M_get_Bit_allocator()); 00761 } 00762 00763 // [23.2.5]/1, third-to-last entry in synopsis listing 00764 static void 00765 swap(reference __x, reference __y) 00766 { 00767 bool __tmp = __x; 00768 __x = __y; 00769 __y = __tmp; 00770 } 00771 00772 iterator 00773 insert(iterator __position, const bool& __x = bool()) 00774 { 00775 const difference_type __n = __position - begin(); 00776 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage 00777 && __position == end()) 00778 *this->_M_impl._M_finish++ = __x; 00779 else 00780 _M_insert_aux(__position, __x); 00781 return begin() + __n; 00782 } 00783 00784 template<typename _InputIterator> 00785 void 00786 insert(iterator __position, 00787 _InputIterator __first, _InputIterator __last) 00788 { 00789 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00790 _M_insert_dispatch(__position, __first, __last, _Integral()); 00791 } 00792 00793 void 00794 insert(iterator __position, size_type __n, const bool& __x) 00795 { _M_fill_insert(__position, __n, __x); } 00796 00797 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00798 void insert(iterator __p, initializer_list<bool> __l) 00799 { this->insert(__p, __l.begin(), __l.end()); } 00800 #endif 00801 00802 void 00803 pop_back() 00804 { --this->_M_impl._M_finish; } 00805 00806 iterator 00807 erase(iterator __position) 00808 { 00809 if (__position + 1 != end()) 00810 std::copy(__position + 1, end(), __position); 00811 --this->_M_impl._M_finish; 00812 return __position; 00813 } 00814 00815 iterator 00816 erase(iterator __first, iterator __last) 00817 { 00818 _M_erase_at_end(std::copy(__last, end(), __first)); 00819 return __first; 00820 } 00821 00822 void 00823 resize(size_type __new_size, bool __x = bool()) 00824 { 00825 if (__new_size < size()) 00826 _M_erase_at_end(begin() + difference_type(__new_size)); 00827 else 00828 insert(end(), __new_size - size(), __x); 00829 } 00830 00831 void 00832 flip() 00833 { 00834 for (_Bit_type * __p = this->_M_impl._M_start._M_p; 00835 __p != this->_M_impl._M_end_of_storage; ++__p) 00836 *__p = ~*__p; 00837 } 00838 00839 void 00840 clear() 00841 { _M_erase_at_end(begin()); } 00842 00843 00844 protected: 00845 // Precondition: __first._M_offset == 0 && __result._M_offset == 0. 00846 iterator 00847 _M_copy_aligned(const_iterator __first, const_iterator __last, 00848 iterator __result) 00849 { 00850 _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p); 00851 return std::copy(const_iterator(__last._M_p, 0), __last, 00852 iterator(__q, 0)); 00853 } 00854 00855 void 00856 _M_initialize(size_type __n) 00857 { 00858 _Bit_type* __q = this->_M_allocate(__n); 00859 this->_M_impl._M_end_of_storage = (__q 00860 + ((__n + int(_S_word_bit) - 1) 00861 / int(_S_word_bit))); 00862 this->_M_impl._M_start = iterator(__q, 0); 00863 this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n); 00864 } 00865 00866 // Check whether it's an integral type. If so, it's not an iterator. 00867 00868 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00869 // 438. Ambiguity in the "do the right thing" clause 00870 template<typename _Integer> 00871 void 00872 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) 00873 { 00874 _M_initialize(static_cast<size_type>(__n)); 00875 std::fill(this->_M_impl._M_start._M_p, 00876 this->_M_impl._M_end_of_storage, __x ? ~0 : 0); 00877 } 00878 00879 template<typename _InputIterator> 00880 void 00881 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 00882 __false_type) 00883 { _M_initialize_range(__first, __last, 00884 std::__iterator_category(__first)); } 00885 00886 template<typename _InputIterator> 00887 void 00888 _M_initialize_range(_InputIterator __first, _InputIterator __last, 00889 std::input_iterator_tag) 00890 { 00891 for (; __first != __last; ++__first) 00892 push_back(*__first); 00893 } 00894 00895 template<typename _ForwardIterator> 00896 void 00897 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last, 00898 std::forward_iterator_tag) 00899 { 00900 const size_type __n = std::distance(__first, __last); 00901 _M_initialize(__n); 00902 std::copy(__first, __last, this->_M_impl._M_start); 00903 } 00904 00905 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00906 // 438. Ambiguity in the "do the right thing" clause 00907 template<typename _Integer> 00908 void 00909 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 00910 { _M_fill_assign(__n, __val); } 00911 00912 template<class _InputIterator> 00913 void 00914 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 00915 __false_type) 00916 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } 00917 00918 void 00919 _M_fill_assign(size_t __n, bool __x) 00920 { 00921 if (__n > size()) 00922 { 00923 std::fill(this->_M_impl._M_start._M_p, 00924 this->_M_impl._M_end_of_storage, __x ? ~0 : 0); 00925 insert(end(), __n - size(), __x); 00926 } 00927 else 00928 { 00929 _M_erase_at_end(begin() + __n); 00930 std::fill(this->_M_impl._M_start._M_p, 00931 this->_M_impl._M_end_of_storage, __x ? ~0 : 0); 00932 } 00933 } 00934 00935 template<typename _InputIterator> 00936 void 00937 _M_assign_aux(_InputIterator __first, _InputIterator __last, 00938 std::input_iterator_tag) 00939 { 00940 iterator __cur = begin(); 00941 for (; __first != __last && __cur != end(); ++__cur, ++__first) 00942 *__cur = *__first; 00943 if (__first == __last) 00944 _M_erase_at_end(__cur); 00945 else 00946 insert(end(), __first, __last); 00947 } 00948 00949 template<typename _ForwardIterator> 00950 void 00951 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 00952 std::forward_iterator_tag) 00953 { 00954 const size_type __len = std::distance(__first, __last); 00955 if (__len < size()) 00956 _M_erase_at_end(std::copy(__first, __last, begin())); 00957 else 00958 { 00959 _ForwardIterator __mid = __first; 00960 std::advance(__mid, size()); 00961 std::copy(__first, __mid, begin()); 00962 insert(end(), __mid, __last); 00963 } 00964 } 00965 00966 // Check whether it's an integral type. If so, it's not an iterator. 00967 00968 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00969 // 438. Ambiguity in the "do the right thing" clause 00970 template<typename _Integer> 00971 void 00972 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, 00973 __true_type) 00974 { _M_fill_insert(__pos, __n, __x); } 00975 00976 template<typename _InputIterator> 00977 void 00978 _M_insert_dispatch(iterator __pos, 00979 _InputIterator __first, _InputIterator __last, 00980 __false_type) 00981 { _M_insert_range(__pos, __first, __last, 00982 std::__iterator_category(__first)); } 00983 00984 void 00985 _M_fill_insert(iterator __position, size_type __n, bool __x); 00986 00987 template<typename _InputIterator> 00988 void 00989 _M_insert_range(iterator __pos, _InputIterator __first, 00990 _InputIterator __last, std::input_iterator_tag) 00991 { 00992 for (; __first != __last; ++__first) 00993 { 00994 __pos = insert(__pos, *__first); 00995 ++__pos; 00996 } 00997 } 00998 00999 template<typename _ForwardIterator> 01000 void 01001 _M_insert_range(iterator __position, _ForwardIterator __first, 01002 _ForwardIterator __last, std::forward_iterator_tag); 01003 01004 void 01005 _M_insert_aux(iterator __position, bool __x); 01006 01007 size_type 01008 _M_check_len(size_type __n, const char* __s) const 01009 { 01010 if (max_size() - size() < __n) 01011 __throw_length_error(__N(__s)); 01012 01013 const size_type __len = size() + std::max(size(), __n); 01014 return (__len < size() || __len > max_size()) ? max_size() : __len; 01015 } 01016 01017 void 01018 _M_erase_at_end(iterator __pos) 01019 { this->_M_impl._M_finish = __pos; } 01020 }; 01021 01022 _GLIBCXX_END_NESTED_NAMESPACE 01023 01024 #endif