libstdc++
|
00001 // vector<bool> specialization -*- C++ -*- 00002 00003 // Copyright (C) 2001-2014 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 iterator 00226 _M_const_cast() const 00227 { return *this; } 00228 00229 reference 00230 operator*() const 00231 { return reference(_M_p, 1UL << _M_offset); } 00232 00233 iterator& 00234 operator++() 00235 { 00236 _M_bump_up(); 00237 return *this; 00238 } 00239 00240 iterator 00241 operator++(int) 00242 { 00243 iterator __tmp = *this; 00244 _M_bump_up(); 00245 return __tmp; 00246 } 00247 00248 iterator& 00249 operator--() 00250 { 00251 _M_bump_down(); 00252 return *this; 00253 } 00254 00255 iterator 00256 operator--(int) 00257 { 00258 iterator __tmp = *this; 00259 _M_bump_down(); 00260 return __tmp; 00261 } 00262 00263 iterator& 00264 operator+=(difference_type __i) 00265 { 00266 _M_incr(__i); 00267 return *this; 00268 } 00269 00270 iterator& 00271 operator-=(difference_type __i) 00272 { 00273 *this += -__i; 00274 return *this; 00275 } 00276 00277 iterator 00278 operator+(difference_type __i) const 00279 { 00280 iterator __tmp = *this; 00281 return __tmp += __i; 00282 } 00283 00284 iterator 00285 operator-(difference_type __i) const 00286 { 00287 iterator __tmp = *this; 00288 return __tmp -= __i; 00289 } 00290 00291 reference 00292 operator[](difference_type __i) const 00293 { return *(*this + __i); } 00294 }; 00295 00296 inline _Bit_iterator 00297 operator+(ptrdiff_t __n, const _Bit_iterator& __x) 00298 { return __x + __n; } 00299 00300 struct _Bit_const_iterator : public _Bit_iterator_base 00301 { 00302 typedef bool reference; 00303 typedef bool const_reference; 00304 typedef const bool* pointer; 00305 typedef _Bit_const_iterator const_iterator; 00306 00307 _Bit_const_iterator() : _Bit_iterator_base(0, 0) { } 00308 00309 _Bit_const_iterator(_Bit_type * __x, unsigned int __y) 00310 : _Bit_iterator_base(__x, __y) { } 00311 00312 _Bit_const_iterator(const _Bit_iterator& __x) 00313 : _Bit_iterator_base(__x._M_p, __x._M_offset) { } 00314 00315 _Bit_iterator 00316 _M_const_cast() const 00317 { return _Bit_iterator(_M_p, _M_offset); } 00318 00319 const_reference 00320 operator*() const 00321 { return _Bit_reference(_M_p, 1UL << _M_offset); } 00322 00323 const_iterator& 00324 operator++() 00325 { 00326 _M_bump_up(); 00327 return *this; 00328 } 00329 00330 const_iterator 00331 operator++(int) 00332 { 00333 const_iterator __tmp = *this; 00334 _M_bump_up(); 00335 return __tmp; 00336 } 00337 00338 const_iterator& 00339 operator--() 00340 { 00341 _M_bump_down(); 00342 return *this; 00343 } 00344 00345 const_iterator 00346 operator--(int) 00347 { 00348 const_iterator __tmp = *this; 00349 _M_bump_down(); 00350 return __tmp; 00351 } 00352 00353 const_iterator& 00354 operator+=(difference_type __i) 00355 { 00356 _M_incr(__i); 00357 return *this; 00358 } 00359 00360 const_iterator& 00361 operator-=(difference_type __i) 00362 { 00363 *this += -__i; 00364 return *this; 00365 } 00366 00367 const_iterator 00368 operator+(difference_type __i) const 00369 { 00370 const_iterator __tmp = *this; 00371 return __tmp += __i; 00372 } 00373 00374 const_iterator 00375 operator-(difference_type __i) const 00376 { 00377 const_iterator __tmp = *this; 00378 return __tmp -= __i; 00379 } 00380 00381 const_reference 00382 operator[](difference_type __i) const 00383 { return *(*this + __i); } 00384 }; 00385 00386 inline _Bit_const_iterator 00387 operator+(ptrdiff_t __n, const _Bit_const_iterator& __x) 00388 { return __x + __n; } 00389 00390 inline void 00391 __fill_bvector(_Bit_iterator __first, _Bit_iterator __last, bool __x) 00392 { 00393 for (; __first != __last; ++__first) 00394 *__first = __x; 00395 } 00396 00397 inline void 00398 fill(_Bit_iterator __first, _Bit_iterator __last, const bool& __x) 00399 { 00400 if (__first._M_p != __last._M_p) 00401 { 00402 std::fill(__first._M_p + 1, __last._M_p, __x ? ~0 : 0); 00403 __fill_bvector(__first, _Bit_iterator(__first._M_p + 1, 0), __x); 00404 __fill_bvector(_Bit_iterator(__last._M_p, 0), __last, __x); 00405 } 00406 else 00407 __fill_bvector(__first, __last, __x); 00408 } 00409 00410 template<typename _Alloc> 00411 struct _Bvector_base 00412 { 00413 typedef typename _Alloc::template rebind<_Bit_type>::other 00414 _Bit_alloc_type; 00415 00416 struct _Bvector_impl 00417 : public _Bit_alloc_type 00418 { 00419 _Bit_iterator _M_start; 00420 _Bit_iterator _M_finish; 00421 _Bit_type* _M_end_of_storage; 00422 00423 _Bvector_impl() 00424 : _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage(0) 00425 { } 00426 00427 _Bvector_impl(const _Bit_alloc_type& __a) 00428 : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage(0) 00429 { } 00430 00431 #if __cplusplus >= 201103L 00432 _Bvector_impl(_Bit_alloc_type&& __a) 00433 : _Bit_alloc_type(std::move(__a)), _M_start(), _M_finish(), 00434 _M_end_of_storage(0) 00435 { } 00436 #endif 00437 }; 00438 00439 public: 00440 typedef _Alloc allocator_type; 00441 00442 _Bit_alloc_type& 00443 _M_get_Bit_allocator() _GLIBCXX_NOEXCEPT 00444 { return *static_cast<_Bit_alloc_type*>(&this->_M_impl); } 00445 00446 const _Bit_alloc_type& 00447 _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT 00448 { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); } 00449 00450 allocator_type 00451 get_allocator() const _GLIBCXX_NOEXCEPT 00452 { return allocator_type(_M_get_Bit_allocator()); } 00453 00454 _Bvector_base() 00455 : _M_impl() { } 00456 00457 _Bvector_base(const allocator_type& __a) 00458 : _M_impl(__a) { } 00459 00460 #if __cplusplus >= 201103L 00461 _Bvector_base(_Bvector_base&& __x) noexcept 00462 : _M_impl(std::move(__x._M_get_Bit_allocator())) 00463 { 00464 this->_M_impl._M_start = __x._M_impl._M_start; 00465 this->_M_impl._M_finish = __x._M_impl._M_finish; 00466 this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; 00467 __x._M_impl._M_start = _Bit_iterator(); 00468 __x._M_impl._M_finish = _Bit_iterator(); 00469 __x._M_impl._M_end_of_storage = 0; 00470 } 00471 #endif 00472 00473 ~_Bvector_base() 00474 { this->_M_deallocate(); } 00475 00476 protected: 00477 _Bvector_impl _M_impl; 00478 00479 _Bit_type* 00480 _M_allocate(size_t __n) 00481 { return _M_impl.allocate(_S_nword(__n)); } 00482 00483 void 00484 _M_deallocate() 00485 { 00486 if (_M_impl._M_start._M_p) 00487 _M_impl.deallocate(_M_impl._M_start._M_p, 00488 _M_impl._M_end_of_storage - _M_impl._M_start._M_p); 00489 } 00490 00491 static size_t 00492 _S_nword(size_t __n) 00493 { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); } 00494 }; 00495 00496 _GLIBCXX_END_NAMESPACE_CONTAINER 00497 } // namespace std 00498 00499 // Declare a partial specialization of vector<T, Alloc>. 00500 #include <bits/stl_vector.h> 00501 00502 namespace std _GLIBCXX_VISIBILITY(default) 00503 { 00504 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 00505 00506 /** 00507 * @brief A specialization of vector for booleans which offers fixed time 00508 * access to individual elements in any order. 00509 * 00510 * @ingroup sequences 00511 * 00512 * @tparam _Alloc Allocator type. 00513 * 00514 * Note that vector<bool> does not actually meet the requirements for being 00515 * a container. This is because the reference and pointer types are not 00516 * really references and pointers to bool. See DR96 for details. @see 00517 * vector for function documentation. 00518 * 00519 * In some terminology a %vector can be described as a dynamic 00520 * C-style array, it offers fast and efficient access to individual 00521 * elements in any order and saves the user from worrying about 00522 * memory and size allocation. Subscripting ( @c [] ) access is 00523 * also provided as with C-style arrays. 00524 */ 00525 template<typename _Alloc> 00526 class vector<bool, _Alloc> : protected _Bvector_base<_Alloc> 00527 { 00528 typedef _Bvector_base<_Alloc> _Base; 00529 00530 #if __cplusplus >= 201103L 00531 template<typename> friend struct hash; 00532 #endif 00533 00534 public: 00535 typedef bool value_type; 00536 typedef size_t size_type; 00537 typedef ptrdiff_t difference_type; 00538 typedef _Bit_reference reference; 00539 typedef bool const_reference; 00540 typedef _Bit_reference* pointer; 00541 typedef const bool* const_pointer; 00542 typedef _Bit_iterator iterator; 00543 typedef _Bit_const_iterator const_iterator; 00544 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00545 typedef std::reverse_iterator<iterator> reverse_iterator; 00546 typedef _Alloc allocator_type; 00547 00548 allocator_type get_allocator() const 00549 { return _Base::get_allocator(); } 00550 00551 protected: 00552 using _Base::_M_allocate; 00553 using _Base::_M_deallocate; 00554 using _Base::_S_nword; 00555 using _Base::_M_get_Bit_allocator; 00556 00557 public: 00558 vector() 00559 : _Base() { } 00560 00561 explicit 00562 vector(const allocator_type& __a) 00563 : _Base(__a) { } 00564 00565 #if __cplusplus >= 201103L 00566 explicit 00567 vector(size_type __n, const allocator_type& __a = allocator_type()) 00568 : vector(__n, false, __a) 00569 { } 00570 00571 vector(size_type __n, const bool& __value, 00572 const allocator_type& __a = allocator_type()) 00573 : _Base(__a) 00574 { 00575 _M_initialize(__n); 00576 std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage, 00577 __value ? ~0 : 0); 00578 } 00579 #else 00580 explicit 00581 vector(size_type __n, const bool& __value = bool(), 00582 const allocator_type& __a = allocator_type()) 00583 : _Base(__a) 00584 { 00585 _M_initialize(__n); 00586 std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_of_storage, 00587 __value ? ~0 : 0); 00588 } 00589 #endif 00590 00591 vector(const vector& __x) 00592 : _Base(__x._M_get_Bit_allocator()) 00593 { 00594 _M_initialize(__x.size()); 00595 _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start); 00596 } 00597 00598 #if __cplusplus >= 201103L 00599 vector(vector&& __x) noexcept 00600 : _Base(std::move(__x)) { } 00601 00602 vector(initializer_list<bool> __l, 00603 const allocator_type& __a = allocator_type()) 00604 : _Base(__a) 00605 { 00606 _M_initialize_range(__l.begin(), __l.end(), 00607 random_access_iterator_tag()); 00608 } 00609 #endif 00610 00611 #if __cplusplus >= 201103L 00612 template<typename _InputIterator, 00613 typename = std::_RequireInputIter<_InputIterator>> 00614 vector(_InputIterator __first, _InputIterator __last, 00615 const allocator_type& __a = allocator_type()) 00616 : _Base(__a) 00617 { _M_initialize_dispatch(__first, __last, __false_type()); } 00618 #else 00619 template<typename _InputIterator> 00620 vector(_InputIterator __first, _InputIterator __last, 00621 const allocator_type& __a = allocator_type()) 00622 : _Base(__a) 00623 { 00624 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00625 _M_initialize_dispatch(__first, __last, _Integral()); 00626 } 00627 #endif 00628 00629 ~vector() _GLIBCXX_NOEXCEPT { } 00630 00631 vector& 00632 operator=(const vector& __x) 00633 { 00634 if (&__x == this) 00635 return *this; 00636 if (__x.size() > capacity()) 00637 { 00638 this->_M_deallocate(); 00639 _M_initialize(__x.size()); 00640 } 00641 this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(), 00642 begin()); 00643 return *this; 00644 } 00645 00646 #if __cplusplus >= 201103L 00647 vector& 00648 operator=(vector&& __x) 00649 { 00650 // NB: DR 1204. 00651 // NB: DR 675. 00652 this->clear(); 00653 this->swap(__x); 00654 return *this; 00655 } 00656 00657 vector& 00658 operator=(initializer_list<bool> __l) 00659 { 00660 this->assign (__l.begin(), __l.end()); 00661 return *this; 00662 } 00663 #endif 00664 00665 // assign(), a generalized assignment member function. Two 00666 // versions: one that takes a count, and one that takes a range. 00667 // The range version is a member template, so we dispatch on whether 00668 // or not the type is an integer. 00669 void 00670 assign(size_type __n, const bool& __x) 00671 { _M_fill_assign(__n, __x); } 00672 00673 #if __cplusplus >= 201103L 00674 template<typename _InputIterator, 00675 typename = std::_RequireInputIter<_InputIterator>> 00676 void 00677 assign(_InputIterator __first, _InputIterator __last) 00678 { _M_assign_dispatch(__first, __last, __false_type()); } 00679 #else 00680 template<typename _InputIterator> 00681 void 00682 assign(_InputIterator __first, _InputIterator __last) 00683 { 00684 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00685 _M_assign_dispatch(__first, __last, _Integral()); 00686 } 00687 #endif 00688 00689 #if __cplusplus >= 201103L 00690 void 00691 assign(initializer_list<bool> __l) 00692 { this->assign(__l.begin(), __l.end()); } 00693 #endif 00694 00695 iterator 00696 begin() _GLIBCXX_NOEXCEPT 00697 { return this->_M_impl._M_start; } 00698 00699 const_iterator 00700 begin() const _GLIBCXX_NOEXCEPT 00701 { return this->_M_impl._M_start; } 00702 00703 iterator 00704 end() _GLIBCXX_NOEXCEPT 00705 { return this->_M_impl._M_finish; } 00706 00707 const_iterator 00708 end() const _GLIBCXX_NOEXCEPT 00709 { return this->_M_impl._M_finish; } 00710 00711 reverse_iterator 00712 rbegin() _GLIBCXX_NOEXCEPT 00713 { return reverse_iterator(end()); } 00714 00715 const_reverse_iterator 00716 rbegin() const _GLIBCXX_NOEXCEPT 00717 { return const_reverse_iterator(end()); } 00718 00719 reverse_iterator 00720 rend() _GLIBCXX_NOEXCEPT 00721 { return reverse_iterator(begin()); } 00722 00723 const_reverse_iterator 00724 rend() const _GLIBCXX_NOEXCEPT 00725 { return const_reverse_iterator(begin()); } 00726 00727 #if __cplusplus >= 201103L 00728 const_iterator 00729 cbegin() const noexcept 00730 { return this->_M_impl._M_start; } 00731 00732 const_iterator 00733 cend() const noexcept 00734 { return this->_M_impl._M_finish; } 00735 00736 const_reverse_iterator 00737 crbegin() const noexcept 00738 { return const_reverse_iterator(end()); } 00739 00740 const_reverse_iterator 00741 crend() const noexcept 00742 { return const_reverse_iterator(begin()); } 00743 #endif 00744 00745 size_type 00746 size() const _GLIBCXX_NOEXCEPT 00747 { return size_type(end() - begin()); } 00748 00749 size_type 00750 max_size() const _GLIBCXX_NOEXCEPT 00751 { 00752 const size_type __isize = 00753 __gnu_cxx::__numeric_traits<difference_type>::__max 00754 - int(_S_word_bit) + 1; 00755 const size_type __asize = _M_get_Bit_allocator().max_size(); 00756 return (__asize <= __isize / int(_S_word_bit) 00757 ? __asize * int(_S_word_bit) : __isize); 00758 } 00759 00760 size_type 00761 capacity() const _GLIBCXX_NOEXCEPT 00762 { return size_type(const_iterator(this->_M_impl._M_end_of_storage, 0) 00763 - begin()); } 00764 00765 bool 00766 empty() const _GLIBCXX_NOEXCEPT 00767 { return begin() == end(); } 00768 00769 reference 00770 operator[](size_type __n) 00771 { 00772 return *iterator(this->_M_impl._M_start._M_p 00773 + __n / int(_S_word_bit), __n % int(_S_word_bit)); 00774 } 00775 00776 const_reference 00777 operator[](size_type __n) const 00778 { 00779 return *const_iterator(this->_M_impl._M_start._M_p 00780 + __n / int(_S_word_bit), __n % int(_S_word_bit)); 00781 } 00782 00783 protected: 00784 void 00785 _M_range_check(size_type __n) const 00786 { 00787 if (__n >= this->size()) 00788 __throw_out_of_range_fmt(__N("vector<bool>::_M_range_check: __n " 00789 "(which is %zu) >= this->size() " 00790 "(which is %zu)"), 00791 __n, this->size()); 00792 } 00793 00794 public: 00795 reference 00796 at(size_type __n) 00797 { _M_range_check(__n); return (*this)[__n]; } 00798 00799 const_reference 00800 at(size_type __n) const 00801 { _M_range_check(__n); return (*this)[__n]; } 00802 00803 void 00804 reserve(size_type __n) 00805 { 00806 if (__n > max_size()) 00807 __throw_length_error(__N("vector::reserve")); 00808 if (capacity() < __n) 00809 _M_reallocate(__n); 00810 } 00811 00812 reference 00813 front() 00814 { return *begin(); } 00815 00816 const_reference 00817 front() const 00818 { return *begin(); } 00819 00820 reference 00821 back() 00822 { return *(end() - 1); } 00823 00824 const_reference 00825 back() const 00826 { return *(end() - 1); } 00827 00828 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00829 // DR 464. Suggestion for new member functions in standard containers. 00830 // N.B. DR 464 says nothing about vector<bool> but we need something 00831 // here due to the way we are implementing DR 464 in the debug-mode 00832 // vector class. 00833 void 00834 data() _GLIBCXX_NOEXCEPT { } 00835 00836 void 00837 push_back(bool __x) 00838 { 00839 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage) 00840 *this->_M_impl._M_finish++ = __x; 00841 else 00842 _M_insert_aux(end(), __x); 00843 } 00844 00845 void 00846 swap(vector& __x) 00847 { 00848 std::swap(this->_M_impl._M_start, __x._M_impl._M_start); 00849 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); 00850 std::swap(this->_M_impl._M_end_of_storage, 00851 __x._M_impl._M_end_of_storage); 00852 00853 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00854 // 431. Swapping containers with unequal allocators. 00855 std::__alloc_swap<typename _Base::_Bit_alloc_type>:: 00856 _S_do_it(_M_get_Bit_allocator(), __x._M_get_Bit_allocator()); 00857 } 00858 00859 // [23.2.5]/1, third-to-last entry in synopsis listing 00860 static void 00861 swap(reference __x, reference __y) _GLIBCXX_NOEXCEPT 00862 { 00863 bool __tmp = __x; 00864 __x = __y; 00865 __y = __tmp; 00866 } 00867 00868 iterator 00869 #if __cplusplus >= 201103L 00870 insert(const_iterator __position, const bool& __x = bool()) 00871 #else 00872 insert(iterator __position, const bool& __x = bool()) 00873 #endif 00874 { 00875 const difference_type __n = __position - begin(); 00876 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage 00877 && __position == end()) 00878 *this->_M_impl._M_finish++ = __x; 00879 else 00880 _M_insert_aux(__position._M_const_cast(), __x); 00881 return begin() + __n; 00882 } 00883 00884 #if __cplusplus >= 201103L 00885 template<typename _InputIterator, 00886 typename = std::_RequireInputIter<_InputIterator>> 00887 iterator 00888 insert(const_iterator __position, 00889 _InputIterator __first, _InputIterator __last) 00890 { 00891 difference_type __offset = __position - cbegin(); 00892 _M_insert_dispatch(__position._M_const_cast(), 00893 __first, __last, __false_type()); 00894 return begin() + __offset; 00895 } 00896 #else 00897 template<typename _InputIterator> 00898 void 00899 insert(iterator __position, 00900 _InputIterator __first, _InputIterator __last) 00901 { 00902 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00903 _M_insert_dispatch(__position, __first, __last, _Integral()); 00904 } 00905 #endif 00906 00907 #if __cplusplus >= 201103L 00908 iterator 00909 insert(const_iterator __position, size_type __n, const bool& __x) 00910 { 00911 difference_type __offset = __position - cbegin(); 00912 _M_fill_insert(__position._M_const_cast(), __n, __x); 00913 return begin() + __offset; 00914 } 00915 #else 00916 void 00917 insert(iterator __position, size_type __n, const bool& __x) 00918 { _M_fill_insert(__position, __n, __x); } 00919 #endif 00920 00921 #if __cplusplus >= 201103L 00922 iterator 00923 insert(const_iterator __p, initializer_list<bool> __l) 00924 { return this->insert(__p, __l.begin(), __l.end()); } 00925 #endif 00926 00927 void 00928 pop_back() 00929 { --this->_M_impl._M_finish; } 00930 00931 iterator 00932 #if __cplusplus >= 201103L 00933 erase(const_iterator __position) 00934 #else 00935 erase(iterator __position) 00936 #endif 00937 { return _M_erase(__position._M_const_cast()); } 00938 00939 iterator 00940 #if __cplusplus >= 201103L 00941 erase(const_iterator __first, const_iterator __last) 00942 #else 00943 erase(iterator __first, iterator __last) 00944 #endif 00945 { return _M_erase(__first._M_const_cast(), __last._M_const_cast()); } 00946 00947 void 00948 resize(size_type __new_size, bool __x = bool()) 00949 { 00950 if (__new_size < size()) 00951 _M_erase_at_end(begin() + difference_type(__new_size)); 00952 else 00953 insert(end(), __new_size - size(), __x); 00954 } 00955 00956 #if __cplusplus >= 201103L 00957 void 00958 shrink_to_fit() 00959 { _M_shrink_to_fit(); } 00960 #endif 00961 00962 void 00963 flip() _GLIBCXX_NOEXCEPT 00964 { 00965 for (_Bit_type * __p = this->_M_impl._M_start._M_p; 00966 __p != this->_M_impl._M_end_of_storage; ++__p) 00967 *__p = ~*__p; 00968 } 00969 00970 void 00971 clear() _GLIBCXX_NOEXCEPT 00972 { _M_erase_at_end(begin()); } 00973 00974 #if __cplusplus >= 201103L 00975 template<typename... _Args> 00976 void 00977 emplace_back(_Args&&... __args) 00978 { push_back(bool(__args...)); } 00979 00980 template<typename... _Args> 00981 iterator 00982 emplace(const_iterator __pos, _Args&&... __args) 00983 { return insert(__pos, bool(__args...)); } 00984 #endif 00985 00986 protected: 00987 // Precondition: __first._M_offset == 0 && __result._M_offset == 0. 00988 iterator 00989 _M_copy_aligned(const_iterator __first, const_iterator __last, 00990 iterator __result) 00991 { 00992 _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p); 00993 return std::copy(const_iterator(__last._M_p, 0), __last, 00994 iterator(__q, 0)); 00995 } 00996 00997 void 00998 _M_initialize(size_type __n) 00999 { 01000 _Bit_type* __q = this->_M_allocate(__n); 01001 this->_M_impl._M_end_of_storage = __q + _S_nword(__n); 01002 this->_M_impl._M_start = iterator(__q, 0); 01003 this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n); 01004 } 01005 01006 void 01007 _M_reallocate(size_type __n); 01008 01009 #if __cplusplus >= 201103L 01010 bool 01011 _M_shrink_to_fit(); 01012 #endif 01013 01014 // Check whether it's an integral type. If so, it's not an iterator. 01015 01016 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01017 // 438. Ambiguity in the "do the right thing" clause 01018 template<typename _Integer> 01019 void 01020 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) 01021 { 01022 _M_initialize(static_cast<size_type>(__n)); 01023 std::fill(this->_M_impl._M_start._M_p, 01024 this->_M_impl._M_end_of_storage, __x ? ~0 : 0); 01025 } 01026 01027 template<typename _InputIterator> 01028 void 01029 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 01030 __false_type) 01031 { _M_initialize_range(__first, __last, 01032 std::__iterator_category(__first)); } 01033 01034 template<typename _InputIterator> 01035 void 01036 _M_initialize_range(_InputIterator __first, _InputIterator __last, 01037 std::input_iterator_tag) 01038 { 01039 for (; __first != __last; ++__first) 01040 push_back(*__first); 01041 } 01042 01043 template<typename _ForwardIterator> 01044 void 01045 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last, 01046 std::forward_iterator_tag) 01047 { 01048 const size_type __n = std::distance(__first, __last); 01049 _M_initialize(__n); 01050 std::copy(__first, __last, this->_M_impl._M_start); 01051 } 01052 01053 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01054 // 438. Ambiguity in the "do the right thing" clause 01055 template<typename _Integer> 01056 void 01057 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 01058 { _M_fill_assign(__n, __val); } 01059 01060 template<class _InputIterator> 01061 void 01062 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 01063 __false_type) 01064 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } 01065 01066 void 01067 _M_fill_assign(size_t __n, bool __x) 01068 { 01069 if (__n > size()) 01070 { 01071 std::fill(this->_M_impl._M_start._M_p, 01072 this->_M_impl._M_end_of_storage, __x ? ~0 : 0); 01073 insert(end(), __n - size(), __x); 01074 } 01075 else 01076 { 01077 _M_erase_at_end(begin() + __n); 01078 std::fill(this->_M_impl._M_start._M_p, 01079 this->_M_impl._M_end_of_storage, __x ? ~0 : 0); 01080 } 01081 } 01082 01083 template<typename _InputIterator> 01084 void 01085 _M_assign_aux(_InputIterator __first, _InputIterator __last, 01086 std::input_iterator_tag) 01087 { 01088 iterator __cur = begin(); 01089 for (; __first != __last && __cur != end(); ++__cur, ++__first) 01090 *__cur = *__first; 01091 if (__first == __last) 01092 _M_erase_at_end(__cur); 01093 else 01094 insert(end(), __first, __last); 01095 } 01096 01097 template<typename _ForwardIterator> 01098 void 01099 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 01100 std::forward_iterator_tag) 01101 { 01102 const size_type __len = std::distance(__first, __last); 01103 if (__len < size()) 01104 _M_erase_at_end(std::copy(__first, __last, begin())); 01105 else 01106 { 01107 _ForwardIterator __mid = __first; 01108 std::advance(__mid, size()); 01109 std::copy(__first, __mid, begin()); 01110 insert(end(), __mid, __last); 01111 } 01112 } 01113 01114 // Check whether it's an integral type. If so, it's not an iterator. 01115 01116 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01117 // 438. Ambiguity in the "do the right thing" clause 01118 template<typename _Integer> 01119 void 01120 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, 01121 __true_type) 01122 { _M_fill_insert(__pos, __n, __x); } 01123 01124 template<typename _InputIterator> 01125 void 01126 _M_insert_dispatch(iterator __pos, 01127 _InputIterator __first, _InputIterator __last, 01128 __false_type) 01129 { _M_insert_range(__pos, __first, __last, 01130 std::__iterator_category(__first)); } 01131 01132 void 01133 _M_fill_insert(iterator __position, size_type __n, bool __x); 01134 01135 template<typename _InputIterator> 01136 void 01137 _M_insert_range(iterator __pos, _InputIterator __first, 01138 _InputIterator __last, std::input_iterator_tag) 01139 { 01140 for (; __first != __last; ++__first) 01141 { 01142 __pos = insert(__pos, *__first); 01143 ++__pos; 01144 } 01145 } 01146 01147 template<typename _ForwardIterator> 01148 void 01149 _M_insert_range(iterator __position, _ForwardIterator __first, 01150 _ForwardIterator __last, std::forward_iterator_tag); 01151 01152 void 01153 _M_insert_aux(iterator __position, bool __x); 01154 01155 size_type 01156 _M_check_len(size_type __n, const char* __s) const 01157 { 01158 if (max_size() - size() < __n) 01159 __throw_length_error(__N(__s)); 01160 01161 const size_type __len = size() + std::max(size(), __n); 01162 return (__len < size() || __len > max_size()) ? max_size() : __len; 01163 } 01164 01165 void 01166 _M_erase_at_end(iterator __pos) 01167 { this->_M_impl._M_finish = __pos; } 01168 01169 iterator 01170 _M_erase(iterator __pos); 01171 01172 iterator 01173 _M_erase(iterator __first, iterator __last); 01174 }; 01175 01176 _GLIBCXX_END_NAMESPACE_CONTAINER 01177 } // namespace std 01178 01179 #if __cplusplus >= 201103L 01180 01181 #include <bits/functional_hash.h> 01182 01183 namespace std _GLIBCXX_VISIBILITY(default) 01184 { 01185 _GLIBCXX_BEGIN_NAMESPACE_VERSION 01186 01187 // DR 1182. 01188 /// std::hash specialization for vector<bool>. 01189 template<typename _Alloc> 01190 struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>> 01191 : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>> 01192 { 01193 size_t 01194 operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept; 01195 }; 01196 01197 _GLIBCXX_END_NAMESPACE_VERSION 01198 }// namespace std 01199 01200 #endif // C++11 01201 01202 #endif