libstdc++
|
00001 // vector<bool> specialization -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 00004 // 2011 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 bits/stl_bvector.h 00053 * This is an internal header file, included by other library headers. 00054 * Do not attempt to use it directly. @headername{vector} 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 } // namespace std 00453 00454 // Declare a partial specialization of vector<T, Alloc>. 00455 #include <bits/stl_vector.h> 00456 00457 namespace std _GLIBCXX_VISIBILITY(default) 00458 { 00459 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 00460 00461 /** 00462 * @brief A specialization of vector for booleans which offers fixed time 00463 * access to individual elements in any order. 00464 * 00465 * Note that vector<bool> does not actually meet the requirements for being 00466 * a container. This is because the reference and pointer types are not 00467 * really references and pointers to bool. See DR96 for details. @see 00468 * vector for function documentation. 00469 * 00470 * @ingroup sequences 00471 * 00472 * In some terminology a %vector can be described as a dynamic 00473 * C-style array, it offers fast and efficient access to individual 00474 * elements in any order and saves the user from worrying about 00475 * memory and size allocation. Subscripting ( @c [] ) access is 00476 * also provided as with C-style arrays. 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 // NB: DR 1204. 00578 // NB: DR 675. 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 // assign(), a generalized assignment member function. Two 00593 // versions: one that takes a count, and one that takes a range. 00594 // The range version is a member template, so we dispatch on whether 00595 // or not the type is an integer. 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 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00739 // DR 464. Suggestion for new member functions in standard containers. 00740 // N.B. DR 464 says nothing about vector<bool> but we need something 00741 // here due to the way we are implementing DR 464 in the debug-mode 00742 // vector class. 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 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00764 // 431. Swapping containers with unequal allocators. 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 // [23.2.5]/1, third-to-last entry in synopsis listing 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 if (__first != __last) 00825 _M_erase_at_end(std::copy(__last, end(), __first)); 00826 return __first; 00827 } 00828 00829 void 00830 resize(size_type __new_size, bool __x = bool()) 00831 { 00832 if (__new_size < size()) 00833 _M_erase_at_end(begin() + difference_type(__new_size)); 00834 else 00835 insert(end(), __new_size - size(), __x); 00836 } 00837 00838 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00839 void 00840 shrink_to_fit() 00841 { std::__shrink_to_fit<vector>::_S_do_it(*this); } 00842 #endif 00843 00844 void 00845 flip() 00846 { 00847 for (_Bit_type * __p = this->_M_impl._M_start._M_p; 00848 __p != this->_M_impl._M_end_of_storage; ++__p) 00849 *__p = ~*__p; 00850 } 00851 00852 void 00853 clear() 00854 { _M_erase_at_end(begin()); } 00855 00856 00857 protected: 00858 // Precondition: __first._M_offset == 0 && __result._M_offset == 0. 00859 iterator 00860 _M_copy_aligned(const_iterator __first, const_iterator __last, 00861 iterator __result) 00862 { 00863 _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p); 00864 return std::copy(const_iterator(__last._M_p, 0), __last, 00865 iterator(__q, 0)); 00866 } 00867 00868 void 00869 _M_initialize(size_type __n) 00870 { 00871 _Bit_type* __q = this->_M_allocate(__n); 00872 this->_M_impl._M_end_of_storage = (__q 00873 + ((__n + int(_S_word_bit) - 1) 00874 / int(_S_word_bit))); 00875 this->_M_impl._M_start = iterator(__q, 0); 00876 this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n); 00877 } 00878 00879 // Check whether it's an integral type. If so, it's not an iterator. 00880 00881 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00882 // 438. Ambiguity in the "do the right thing" clause 00883 template<typename _Integer> 00884 void 00885 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) 00886 { 00887 _M_initialize(static_cast<size_type>(__n)); 00888 std::fill(this->_M_impl._M_start._M_p, 00889 this->_M_impl._M_end_of_storage, __x ? ~0 : 0); 00890 } 00891 00892 template<typename _InputIterator> 00893 void 00894 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 00895 __false_type) 00896 { _M_initialize_range(__first, __last, 00897 std::__iterator_category(__first)); } 00898 00899 template<typename _InputIterator> 00900 void 00901 _M_initialize_range(_InputIterator __first, _InputIterator __last, 00902 std::input_iterator_tag) 00903 { 00904 for (; __first != __last; ++__first) 00905 push_back(*__first); 00906 } 00907 00908 template<typename _ForwardIterator> 00909 void 00910 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last, 00911 std::forward_iterator_tag) 00912 { 00913 const size_type __n = std::distance(__first, __last); 00914 _M_initialize(__n); 00915 std::copy(__first, __last, this->_M_impl._M_start); 00916 } 00917 00918 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00919 // 438. Ambiguity in the "do the right thing" clause 00920 template<typename _Integer> 00921 void 00922 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 00923 { _M_fill_assign(__n, __val); } 00924 00925 template<class _InputIterator> 00926 void 00927 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 00928 __false_type) 00929 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } 00930 00931 void 00932 _M_fill_assign(size_t __n, bool __x) 00933 { 00934 if (__n > size()) 00935 { 00936 std::fill(this->_M_impl._M_start._M_p, 00937 this->_M_impl._M_end_of_storage, __x ? ~0 : 0); 00938 insert(end(), __n - size(), __x); 00939 } 00940 else 00941 { 00942 _M_erase_at_end(begin() + __n); 00943 std::fill(this->_M_impl._M_start._M_p, 00944 this->_M_impl._M_end_of_storage, __x ? ~0 : 0); 00945 } 00946 } 00947 00948 template<typename _InputIterator> 00949 void 00950 _M_assign_aux(_InputIterator __first, _InputIterator __last, 00951 std::input_iterator_tag) 00952 { 00953 iterator __cur = begin(); 00954 for (; __first != __last && __cur != end(); ++__cur, ++__first) 00955 *__cur = *__first; 00956 if (__first == __last) 00957 _M_erase_at_end(__cur); 00958 else 00959 insert(end(), __first, __last); 00960 } 00961 00962 template<typename _ForwardIterator> 00963 void 00964 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 00965 std::forward_iterator_tag) 00966 { 00967 const size_type __len = std::distance(__first, __last); 00968 if (__len < size()) 00969 _M_erase_at_end(std::copy(__first, __last, begin())); 00970 else 00971 { 00972 _ForwardIterator __mid = __first; 00973 std::advance(__mid, size()); 00974 std::copy(__first, __mid, begin()); 00975 insert(end(), __mid, __last); 00976 } 00977 } 00978 00979 // Check whether it's an integral type. If so, it's not an iterator. 00980 00981 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00982 // 438. Ambiguity in the "do the right thing" clause 00983 template<typename _Integer> 00984 void 00985 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, 00986 __true_type) 00987 { _M_fill_insert(__pos, __n, __x); } 00988 00989 template<typename _InputIterator> 00990 void 00991 _M_insert_dispatch(iterator __pos, 00992 _InputIterator __first, _InputIterator __last, 00993 __false_type) 00994 { _M_insert_range(__pos, __first, __last, 00995 std::__iterator_category(__first)); } 00996 00997 void 00998 _M_fill_insert(iterator __position, size_type __n, bool __x); 00999 01000 template<typename _InputIterator> 01001 void 01002 _M_insert_range(iterator __pos, _InputIterator __first, 01003 _InputIterator __last, std::input_iterator_tag) 01004 { 01005 for (; __first != __last; ++__first) 01006 { 01007 __pos = insert(__pos, *__first); 01008 ++__pos; 01009 } 01010 } 01011 01012 template<typename _ForwardIterator> 01013 void 01014 _M_insert_range(iterator __position, _ForwardIterator __first, 01015 _ForwardIterator __last, std::forward_iterator_tag); 01016 01017 void 01018 _M_insert_aux(iterator __position, bool __x); 01019 01020 size_type 01021 _M_check_len(size_type __n, const char* __s) const 01022 { 01023 if (max_size() - size() < __n) 01024 __throw_length_error(__N(__s)); 01025 01026 const size_type __len = size() + std::max(size(), __n); 01027 return (__len < size() || __len > max_size()) ? max_size() : __len; 01028 } 01029 01030 void 01031 _M_erase_at_end(iterator __pos) 01032 { this->_M_impl._M_finish = __pos; } 01033 }; 01034 01035 _GLIBCXX_END_NAMESPACE_CONTAINER 01036 } // namespace std 01037 01038 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 01039 01040 #include <bits/functional_hash.h> 01041 01042 namespace std _GLIBCXX_VISIBILITY(default) 01043 { 01044 _GLIBCXX_BEGIN_NAMESPACE_VERSION 01045 01046 // DR 1182. 01047 /// std::hash specialization for vector<bool>. 01048 template<typename _Alloc> 01049 struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>> 01050 : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>> 01051 { 01052 size_t 01053 operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const; 01054 }; 01055 01056 _GLIBCXX_END_NAMESPACE_VERSION 01057 }// namespace std 01058 01059 #endif // __GXX_EXPERIMENTAL_CXX0X__ 01060 01061 #endif