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