libstdc++
|
00001 // vector<bool> specialization -*- C++ -*- 00002 00003 // Copyright (C) 2001-2018 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 #include <bits/functional_hash.h> 00062 #endif 00063 00064 namespace std _GLIBCXX_VISIBILITY(default) 00065 { 00066 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00067 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 00068 00069 typedef unsigned long _Bit_type; 00070 enum { _S_word_bit = int(__CHAR_BIT__ * sizeof(_Bit_type)) }; 00071 00072 struct _Bit_reference 00073 { 00074 _Bit_type * _M_p; 00075 _Bit_type _M_mask; 00076 00077 _Bit_reference(_Bit_type * __x, _Bit_type __y) 00078 : _M_p(__x), _M_mask(__y) { } 00079 00080 _Bit_reference() _GLIBCXX_NOEXCEPT : _M_p(0), _M_mask(0) { } 00081 00082 operator bool() const _GLIBCXX_NOEXCEPT 00083 { return !!(*_M_p & _M_mask); } 00084 00085 _Bit_reference& 00086 operator=(bool __x) _GLIBCXX_NOEXCEPT 00087 { 00088 if (__x) 00089 *_M_p |= _M_mask; 00090 else 00091 *_M_p &= ~_M_mask; 00092 return *this; 00093 } 00094 00095 _Bit_reference& 00096 operator=(const _Bit_reference& __x) _GLIBCXX_NOEXCEPT 00097 { return *this = bool(__x); } 00098 00099 bool 00100 operator==(const _Bit_reference& __x) const 00101 { return bool(*this) == bool(__x); } 00102 00103 bool 00104 operator<(const _Bit_reference& __x) const 00105 { return !bool(*this) && bool(__x); } 00106 00107 void 00108 flip() _GLIBCXX_NOEXCEPT 00109 { *_M_p ^= _M_mask; } 00110 }; 00111 00112 #if __cplusplus >= 201103L 00113 inline void 00114 swap(_Bit_reference __x, _Bit_reference __y) noexcept 00115 { 00116 bool __tmp = __x; 00117 __x = __y; 00118 __y = __tmp; 00119 } 00120 00121 inline void 00122 swap(_Bit_reference __x, bool& __y) noexcept 00123 { 00124 bool __tmp = __x; 00125 __x = __y; 00126 __y = __tmp; 00127 } 00128 00129 inline void 00130 swap(bool& __x, _Bit_reference __y) noexcept 00131 { 00132 bool __tmp = __x; 00133 __x = __y; 00134 __y = __tmp; 00135 } 00136 #endif 00137 00138 struct _Bit_iterator_base 00139 : public std::iterator<std::random_access_iterator_tag, bool> 00140 { 00141 _Bit_type * _M_p; 00142 unsigned int _M_offset; 00143 00144 _Bit_iterator_base(_Bit_type * __x, unsigned int __y) 00145 : _M_p(__x), _M_offset(__y) { } 00146 00147 void 00148 _M_bump_up() 00149 { 00150 if (_M_offset++ == int(_S_word_bit) - 1) 00151 { 00152 _M_offset = 0; 00153 ++_M_p; 00154 } 00155 } 00156 00157 void 00158 _M_bump_down() 00159 { 00160 if (_M_offset-- == 0) 00161 { 00162 _M_offset = int(_S_word_bit) - 1; 00163 --_M_p; 00164 } 00165 } 00166 00167 void 00168 _M_incr(ptrdiff_t __i) 00169 { 00170 difference_type __n = __i + _M_offset; 00171 _M_p += __n / int(_S_word_bit); 00172 __n = __n % int(_S_word_bit); 00173 if (__n < 0) 00174 { 00175 __n += int(_S_word_bit); 00176 --_M_p; 00177 } 00178 _M_offset = static_cast<unsigned int>(__n); 00179 } 00180 00181 bool 00182 operator==(const _Bit_iterator_base& __i) const 00183 { return _M_p == __i._M_p && _M_offset == __i._M_offset; } 00184 00185 bool 00186 operator<(const _Bit_iterator_base& __i) const 00187 { 00188 return _M_p < __i._M_p 00189 || (_M_p == __i._M_p && _M_offset < __i._M_offset); 00190 } 00191 00192 bool 00193 operator!=(const _Bit_iterator_base& __i) const 00194 { return !(*this == __i); } 00195 00196 bool 00197 operator>(const _Bit_iterator_base& __i) const 00198 { return __i < *this; } 00199 00200 bool 00201 operator<=(const _Bit_iterator_base& __i) const 00202 { return !(__i < *this); } 00203 00204 bool 00205 operator>=(const _Bit_iterator_base& __i) const 00206 { return !(*this < __i); } 00207 }; 00208 00209 inline ptrdiff_t 00210 operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y) 00211 { 00212 return (int(_S_word_bit) * (__x._M_p - __y._M_p) 00213 + __x._M_offset - __y._M_offset); 00214 } 00215 00216 struct _Bit_iterator : public _Bit_iterator_base 00217 { 00218 typedef _Bit_reference reference; 00219 typedef _Bit_reference* pointer; 00220 typedef _Bit_iterator iterator; 00221 00222 _Bit_iterator() : _Bit_iterator_base(0, 0) { } 00223 00224 _Bit_iterator(_Bit_type * __x, unsigned int __y) 00225 : _Bit_iterator_base(__x, __y) { } 00226 00227 iterator 00228 _M_const_cast() const 00229 { return *this; } 00230 00231 reference 00232 operator*() const 00233 { return reference(_M_p, 1UL << _M_offset); } 00234 00235 iterator& 00236 operator++() 00237 { 00238 _M_bump_up(); 00239 return *this; 00240 } 00241 00242 iterator 00243 operator++(int) 00244 { 00245 iterator __tmp = *this; 00246 _M_bump_up(); 00247 return __tmp; 00248 } 00249 00250 iterator& 00251 operator--() 00252 { 00253 _M_bump_down(); 00254 return *this; 00255 } 00256 00257 iterator 00258 operator--(int) 00259 { 00260 iterator __tmp = *this; 00261 _M_bump_down(); 00262 return __tmp; 00263 } 00264 00265 iterator& 00266 operator+=(difference_type __i) 00267 { 00268 _M_incr(__i); 00269 return *this; 00270 } 00271 00272 iterator& 00273 operator-=(difference_type __i) 00274 { 00275 *this += -__i; 00276 return *this; 00277 } 00278 00279 iterator 00280 operator+(difference_type __i) const 00281 { 00282 iterator __tmp = *this; 00283 return __tmp += __i; 00284 } 00285 00286 iterator 00287 operator-(difference_type __i) const 00288 { 00289 iterator __tmp = *this; 00290 return __tmp -= __i; 00291 } 00292 00293 reference 00294 operator[](difference_type __i) const 00295 { return *(*this + __i); } 00296 }; 00297 00298 inline _Bit_iterator 00299 operator+(ptrdiff_t __n, const _Bit_iterator& __x) 00300 { return __x + __n; } 00301 00302 struct _Bit_const_iterator : public _Bit_iterator_base 00303 { 00304 typedef bool reference; 00305 typedef bool const_reference; 00306 typedef const bool* pointer; 00307 typedef _Bit_const_iterator const_iterator; 00308 00309 _Bit_const_iterator() : _Bit_iterator_base(0, 0) { } 00310 00311 _Bit_const_iterator(_Bit_type * __x, unsigned int __y) 00312 : _Bit_iterator_base(__x, __y) { } 00313 00314 _Bit_const_iterator(const _Bit_iterator& __x) 00315 : _Bit_iterator_base(__x._M_p, __x._M_offset) { } 00316 00317 _Bit_iterator 00318 _M_const_cast() const 00319 { return _Bit_iterator(_M_p, _M_offset); } 00320 00321 const_reference 00322 operator*() const 00323 { return _Bit_reference(_M_p, 1UL << _M_offset); } 00324 00325 const_iterator& 00326 operator++() 00327 { 00328 _M_bump_up(); 00329 return *this; 00330 } 00331 00332 const_iterator 00333 operator++(int) 00334 { 00335 const_iterator __tmp = *this; 00336 _M_bump_up(); 00337 return __tmp; 00338 } 00339 00340 const_iterator& 00341 operator--() 00342 { 00343 _M_bump_down(); 00344 return *this; 00345 } 00346 00347 const_iterator 00348 operator--(int) 00349 { 00350 const_iterator __tmp = *this; 00351 _M_bump_down(); 00352 return __tmp; 00353 } 00354 00355 const_iterator& 00356 operator+=(difference_type __i) 00357 { 00358 _M_incr(__i); 00359 return *this; 00360 } 00361 00362 const_iterator& 00363 operator-=(difference_type __i) 00364 { 00365 *this += -__i; 00366 return *this; 00367 } 00368 00369 const_iterator 00370 operator+(difference_type __i) const 00371 { 00372 const_iterator __tmp = *this; 00373 return __tmp += __i; 00374 } 00375 00376 const_iterator 00377 operator-(difference_type __i) const 00378 { 00379 const_iterator __tmp = *this; 00380 return __tmp -= __i; 00381 } 00382 00383 const_reference 00384 operator[](difference_type __i) const 00385 { return *(*this + __i); } 00386 }; 00387 00388 inline _Bit_const_iterator 00389 operator+(ptrdiff_t __n, const _Bit_const_iterator& __x) 00390 { return __x + __n; } 00391 00392 inline void 00393 __fill_bvector(_Bit_type * __v, 00394 unsigned int __first, unsigned int __last, bool __x) 00395 { 00396 const _Bit_type __fmask = ~0ul << __first; 00397 const _Bit_type __lmask = ~0ul >> (_S_word_bit - __last); 00398 const _Bit_type __mask = __fmask & __lmask; 00399 00400 if (__x) 00401 *__v |= __mask; 00402 else 00403 *__v &= ~__mask; 00404 } 00405 00406 inline void 00407 fill(_Bit_iterator __first, _Bit_iterator __last, const bool& __x) 00408 { 00409 if (__first._M_p != __last._M_p) 00410 { 00411 _Bit_type* __first_p = __first._M_p; 00412 if (__first._M_offset != 0) 00413 __fill_bvector(__first_p++, __first._M_offset, _S_word_bit, __x); 00414 00415 __builtin_memset(__first_p, __x ? ~0 : 0, 00416 (__last._M_p - __first_p) * sizeof(_Bit_type)); 00417 00418 if (__last._M_offset != 0) 00419 __fill_bvector(__last._M_p, 0, __last._M_offset, __x); 00420 } 00421 else if (__first._M_offset != __last._M_offset) 00422 __fill_bvector(__first._M_p, __first._M_offset, __last._M_offset, __x); 00423 } 00424 00425 template<typename _Alloc> 00426 struct _Bvector_base 00427 { 00428 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 00429 rebind<_Bit_type>::other _Bit_alloc_type; 00430 typedef typename __gnu_cxx::__alloc_traits<_Bit_alloc_type> 00431 _Bit_alloc_traits; 00432 typedef typename _Bit_alloc_traits::pointer _Bit_pointer; 00433 00434 struct _Bvector_impl_data 00435 { 00436 _Bit_iterator _M_start; 00437 _Bit_iterator _M_finish; 00438 _Bit_pointer _M_end_of_storage; 00439 00440 _Bvector_impl_data() _GLIBCXX_NOEXCEPT 00441 : _M_start(), _M_finish(), _M_end_of_storage() 00442 { } 00443 00444 #if __cplusplus >= 201103L 00445 _Bvector_impl_data(_Bvector_impl_data&& __x) noexcept 00446 : _M_start(__x._M_start), _M_finish(__x._M_finish) 00447 , _M_end_of_storage(__x._M_end_of_storage) 00448 { __x._M_reset(); } 00449 00450 void 00451 _M_move_data(_Bvector_impl_data&& __x) noexcept 00452 { 00453 this->_M_start = __x._M_start; 00454 this->_M_finish = __x._M_finish; 00455 this->_M_end_of_storage = __x._M_end_of_storage; 00456 __x._M_reset(); 00457 } 00458 #endif 00459 00460 void 00461 _M_reset() _GLIBCXX_NOEXCEPT 00462 { 00463 _M_start = _M_finish = _Bit_iterator(); 00464 _M_end_of_storage = _Bit_pointer(); 00465 } 00466 }; 00467 00468 struct _Bvector_impl 00469 : public _Bit_alloc_type, public _Bvector_impl_data 00470 { 00471 public: 00472 _Bvector_impl() _GLIBCXX_NOEXCEPT_IF( 00473 is_nothrow_default_constructible<_Bit_alloc_type>::value) 00474 : _Bit_alloc_type() 00475 { } 00476 00477 _Bvector_impl(const _Bit_alloc_type& __a) _GLIBCXX_NOEXCEPT 00478 : _Bit_alloc_type(__a) 00479 { } 00480 00481 #if __cplusplus >= 201103L 00482 _Bvector_impl(_Bvector_impl&&) = default; 00483 #endif 00484 00485 _Bit_type* 00486 _M_end_addr() const _GLIBCXX_NOEXCEPT 00487 { 00488 if (this->_M_end_of_storage) 00489 return std::__addressof(this->_M_end_of_storage[-1]) + 1; 00490 return 0; 00491 } 00492 }; 00493 00494 public: 00495 typedef _Alloc allocator_type; 00496 00497 _Bit_alloc_type& 00498 _M_get_Bit_allocator() _GLIBCXX_NOEXCEPT 00499 { return this->_M_impl; } 00500 00501 const _Bit_alloc_type& 00502 _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT 00503 { return this->_M_impl; } 00504 00505 allocator_type 00506 get_allocator() const _GLIBCXX_NOEXCEPT 00507 { return allocator_type(_M_get_Bit_allocator()); } 00508 00509 #if __cplusplus >= 201103L 00510 _Bvector_base() = default; 00511 #else 00512 _Bvector_base() { } 00513 #endif 00514 00515 _Bvector_base(const allocator_type& __a) 00516 : _M_impl(__a) { } 00517 00518 #if __cplusplus >= 201103L 00519 _Bvector_base(_Bvector_base&&) = default; 00520 #endif 00521 00522 ~_Bvector_base() 00523 { this->_M_deallocate(); } 00524 00525 protected: 00526 _Bvector_impl _M_impl; 00527 00528 _Bit_pointer 00529 _M_allocate(size_t __n) 00530 { return _Bit_alloc_traits::allocate(_M_impl, _S_nword(__n)); } 00531 00532 void 00533 _M_deallocate() 00534 { 00535 if (_M_impl._M_start._M_p) 00536 { 00537 const size_t __n = _M_impl._M_end_addr() - _M_impl._M_start._M_p; 00538 _Bit_alloc_traits::deallocate(_M_impl, 00539 _M_impl._M_end_of_storage - __n, 00540 __n); 00541 _M_impl._M_reset(); 00542 } 00543 } 00544 00545 #if __cplusplus >= 201103L 00546 void 00547 _M_move_data(_Bvector_base&& __x) noexcept 00548 { _M_impl._M_move_data(std::move(__x._M_impl)); } 00549 #endif 00550 00551 static size_t 00552 _S_nword(size_t __n) 00553 { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); } 00554 }; 00555 00556 _GLIBCXX_END_NAMESPACE_CONTAINER 00557 _GLIBCXX_END_NAMESPACE_VERSION 00558 } // namespace std 00559 00560 // Declare a partial specialization of vector<T, Alloc>. 00561 #include <bits/stl_vector.h> 00562 00563 namespace std _GLIBCXX_VISIBILITY(default) 00564 { 00565 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00566 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 00567 00568 /** 00569 * @brief A specialization of vector for booleans which offers fixed time 00570 * access to individual elements in any order. 00571 * 00572 * @ingroup sequences 00573 * 00574 * @tparam _Alloc Allocator type. 00575 * 00576 * Note that vector<bool> does not actually meet the requirements for being 00577 * a container. This is because the reference and pointer types are not 00578 * really references and pointers to bool. See DR96 for details. @see 00579 * vector for function documentation. 00580 * 00581 * In some terminology a %vector can be described as a dynamic 00582 * C-style array, it offers fast and efficient access to individual 00583 * elements in any order and saves the user from worrying about 00584 * memory and size allocation. Subscripting ( @c [] ) access is 00585 * also provided as with C-style arrays. 00586 */ 00587 template<typename _Alloc> 00588 class vector<bool, _Alloc> : protected _Bvector_base<_Alloc> 00589 { 00590 typedef _Bvector_base<_Alloc> _Base; 00591 typedef typename _Base::_Bit_pointer _Bit_pointer; 00592 typedef typename _Base::_Bit_alloc_traits _Bit_alloc_traits; 00593 00594 #if __cplusplus >= 201103L 00595 friend struct std::hash<vector>; 00596 #endif 00597 00598 public: 00599 typedef bool value_type; 00600 typedef size_t size_type; 00601 typedef ptrdiff_t difference_type; 00602 typedef _Bit_reference reference; 00603 typedef bool const_reference; 00604 typedef _Bit_reference* pointer; 00605 typedef const bool* const_pointer; 00606 typedef _Bit_iterator iterator; 00607 typedef _Bit_const_iterator const_iterator; 00608 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00609 typedef std::reverse_iterator<iterator> reverse_iterator; 00610 typedef _Alloc allocator_type; 00611 00612 allocator_type 00613 get_allocator() const 00614 { return _Base::get_allocator(); } 00615 00616 protected: 00617 using _Base::_M_allocate; 00618 using _Base::_M_deallocate; 00619 using _Base::_S_nword; 00620 using _Base::_M_get_Bit_allocator; 00621 00622 public: 00623 #if __cplusplus >= 201103L 00624 vector() = default; 00625 #else 00626 vector() { } 00627 #endif 00628 00629 explicit 00630 vector(const allocator_type& __a) 00631 : _Base(__a) { } 00632 00633 #if __cplusplus >= 201103L 00634 explicit 00635 vector(size_type __n, const allocator_type& __a = allocator_type()) 00636 : vector(__n, false, __a) 00637 { } 00638 00639 vector(size_type __n, const bool& __value, 00640 const allocator_type& __a = allocator_type()) 00641 #else 00642 explicit 00643 vector(size_type __n, const bool& __value = bool(), 00644 const allocator_type& __a = allocator_type()) 00645 #endif 00646 : _Base(__a) 00647 { 00648 _M_initialize(__n); 00649 _M_initialize_value(__value); 00650 } 00651 00652 vector(const vector& __x) 00653 : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator())) 00654 { 00655 _M_initialize(__x.size()); 00656 _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start); 00657 } 00658 00659 #if __cplusplus >= 201103L 00660 vector(vector&&) = default; 00661 00662 vector(vector&& __x, const allocator_type& __a) 00663 noexcept(_Bit_alloc_traits::_S_always_equal()) 00664 : _Base(__a) 00665 { 00666 if (__x.get_allocator() == __a) 00667 this->_M_move_data(std::move(__x)); 00668 else 00669 { 00670 _M_initialize(__x.size()); 00671 _M_copy_aligned(__x.begin(), __x.end(), begin()); 00672 __x.clear(); 00673 } 00674 } 00675 00676 vector(const vector& __x, const allocator_type& __a) 00677 : _Base(__a) 00678 { 00679 _M_initialize(__x.size()); 00680 _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start); 00681 } 00682 00683 vector(initializer_list<bool> __l, 00684 const allocator_type& __a = allocator_type()) 00685 : _Base(__a) 00686 { 00687 _M_initialize_range(__l.begin(), __l.end(), 00688 random_access_iterator_tag()); 00689 } 00690 #endif 00691 00692 #if __cplusplus >= 201103L 00693 template<typename _InputIterator, 00694 typename = std::_RequireInputIter<_InputIterator>> 00695 vector(_InputIterator __first, _InputIterator __last, 00696 const allocator_type& __a = allocator_type()) 00697 : _Base(__a) 00698 { _M_initialize_dispatch(__first, __last, __false_type()); } 00699 #else 00700 template<typename _InputIterator> 00701 vector(_InputIterator __first, _InputIterator __last, 00702 const allocator_type& __a = allocator_type()) 00703 : _Base(__a) 00704 { 00705 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00706 _M_initialize_dispatch(__first, __last, _Integral()); 00707 } 00708 #endif 00709 00710 ~vector() _GLIBCXX_NOEXCEPT { } 00711 00712 vector& 00713 operator=(const vector& __x) 00714 { 00715 if (&__x == this) 00716 return *this; 00717 #if __cplusplus >= 201103L 00718 if (_Bit_alloc_traits::_S_propagate_on_copy_assign()) 00719 { 00720 if (this->_M_get_Bit_allocator() != __x._M_get_Bit_allocator()) 00721 { 00722 this->_M_deallocate(); 00723 std::__alloc_on_copy(_M_get_Bit_allocator(), 00724 __x._M_get_Bit_allocator()); 00725 _M_initialize(__x.size()); 00726 } 00727 else 00728 std::__alloc_on_copy(_M_get_Bit_allocator(), 00729 __x._M_get_Bit_allocator()); 00730 } 00731 #endif 00732 if (__x.size() > capacity()) 00733 { 00734 this->_M_deallocate(); 00735 _M_initialize(__x.size()); 00736 } 00737 this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(), 00738 begin()); 00739 return *this; 00740 } 00741 00742 #if __cplusplus >= 201103L 00743 vector& 00744 operator=(vector&& __x) noexcept(_Bit_alloc_traits::_S_nothrow_move()) 00745 { 00746 if (_Bit_alloc_traits::_S_propagate_on_move_assign() 00747 || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator()) 00748 { 00749 this->_M_deallocate(); 00750 this->_M_move_data(std::move(__x)); 00751 std::__alloc_on_move(_M_get_Bit_allocator(), 00752 __x._M_get_Bit_allocator()); 00753 } 00754 else 00755 { 00756 if (__x.size() > capacity()) 00757 { 00758 this->_M_deallocate(); 00759 _M_initialize(__x.size()); 00760 } 00761 this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(), 00762 begin()); 00763 __x.clear(); 00764 } 00765 return *this; 00766 } 00767 00768 vector& 00769 operator=(initializer_list<bool> __l) 00770 { 00771 this->assign (__l.begin(), __l.end()); 00772 return *this; 00773 } 00774 #endif 00775 00776 // assign(), a generalized assignment member function. Two 00777 // versions: one that takes a count, and one that takes a range. 00778 // The range version is a member template, so we dispatch on whether 00779 // or not the type is an integer. 00780 void 00781 assign(size_type __n, const bool& __x) 00782 { _M_fill_assign(__n, __x); } 00783 00784 #if __cplusplus >= 201103L 00785 template<typename _InputIterator, 00786 typename = std::_RequireInputIter<_InputIterator>> 00787 void 00788 assign(_InputIterator __first, _InputIterator __last) 00789 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } 00790 #else 00791 template<typename _InputIterator> 00792 void 00793 assign(_InputIterator __first, _InputIterator __last) 00794 { 00795 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00796 _M_assign_dispatch(__first, __last, _Integral()); 00797 } 00798 #endif 00799 00800 #if __cplusplus >= 201103L 00801 void 00802 assign(initializer_list<bool> __l) 00803 { _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); } 00804 #endif 00805 00806 iterator 00807 begin() _GLIBCXX_NOEXCEPT 00808 { return this->_M_impl._M_start; } 00809 00810 const_iterator 00811 begin() const _GLIBCXX_NOEXCEPT 00812 { return this->_M_impl._M_start; } 00813 00814 iterator 00815 end() _GLIBCXX_NOEXCEPT 00816 { return this->_M_impl._M_finish; } 00817 00818 const_iterator 00819 end() const _GLIBCXX_NOEXCEPT 00820 { return this->_M_impl._M_finish; } 00821 00822 reverse_iterator 00823 rbegin() _GLIBCXX_NOEXCEPT 00824 { return reverse_iterator(end()); } 00825 00826 const_reverse_iterator 00827 rbegin() const _GLIBCXX_NOEXCEPT 00828 { return const_reverse_iterator(end()); } 00829 00830 reverse_iterator 00831 rend() _GLIBCXX_NOEXCEPT 00832 { return reverse_iterator(begin()); } 00833 00834 const_reverse_iterator 00835 rend() const _GLIBCXX_NOEXCEPT 00836 { return const_reverse_iterator(begin()); } 00837 00838 #if __cplusplus >= 201103L 00839 const_iterator 00840 cbegin() const noexcept 00841 { return this->_M_impl._M_start; } 00842 00843 const_iterator 00844 cend() const noexcept 00845 { return this->_M_impl._M_finish; } 00846 00847 const_reverse_iterator 00848 crbegin() const noexcept 00849 { return const_reverse_iterator(end()); } 00850 00851 const_reverse_iterator 00852 crend() const noexcept 00853 { return const_reverse_iterator(begin()); } 00854 #endif 00855 00856 size_type 00857 size() const _GLIBCXX_NOEXCEPT 00858 { return size_type(end() - begin()); } 00859 00860 size_type 00861 max_size() const _GLIBCXX_NOEXCEPT 00862 { 00863 const size_type __isize = 00864 __gnu_cxx::__numeric_traits<difference_type>::__max 00865 - int(_S_word_bit) + 1; 00866 const size_type __asize 00867 = _Bit_alloc_traits::max_size(_M_get_Bit_allocator()); 00868 return (__asize <= __isize / int(_S_word_bit) 00869 ? __asize * int(_S_word_bit) : __isize); 00870 } 00871 00872 size_type 00873 capacity() const _GLIBCXX_NOEXCEPT 00874 { return size_type(const_iterator(this->_M_impl._M_end_addr(), 0) 00875 - begin()); } 00876 00877 bool 00878 empty() const _GLIBCXX_NOEXCEPT 00879 { return begin() == end(); } 00880 00881 reference 00882 operator[](size_type __n) 00883 { 00884 return *iterator(this->_M_impl._M_start._M_p 00885 + __n / int(_S_word_bit), __n % int(_S_word_bit)); 00886 } 00887 00888 const_reference 00889 operator[](size_type __n) const 00890 { 00891 return *const_iterator(this->_M_impl._M_start._M_p 00892 + __n / int(_S_word_bit), __n % int(_S_word_bit)); 00893 } 00894 00895 protected: 00896 void 00897 _M_range_check(size_type __n) const 00898 { 00899 if (__n >= this->size()) 00900 __throw_out_of_range_fmt(__N("vector<bool>::_M_range_check: __n " 00901 "(which is %zu) >= this->size() " 00902 "(which is %zu)"), 00903 __n, this->size()); 00904 } 00905 00906 public: 00907 reference 00908 at(size_type __n) 00909 { _M_range_check(__n); return (*this)[__n]; } 00910 00911 const_reference 00912 at(size_type __n) const 00913 { _M_range_check(__n); return (*this)[__n]; } 00914 00915 void 00916 reserve(size_type __n) 00917 { 00918 if (__n > max_size()) 00919 __throw_length_error(__N("vector::reserve")); 00920 if (capacity() < __n) 00921 _M_reallocate(__n); 00922 } 00923 00924 reference 00925 front() 00926 { return *begin(); } 00927 00928 const_reference 00929 front() const 00930 { return *begin(); } 00931 00932 reference 00933 back() 00934 { return *(end() - 1); } 00935 00936 const_reference 00937 back() const 00938 { return *(end() - 1); } 00939 00940 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00941 // DR 464. Suggestion for new member functions in standard containers. 00942 // N.B. DR 464 says nothing about vector<bool> but we need something 00943 // here due to the way we are implementing DR 464 in the debug-mode 00944 // vector class. 00945 void 00946 data() _GLIBCXX_NOEXCEPT { } 00947 00948 void 00949 push_back(bool __x) 00950 { 00951 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()) 00952 *this->_M_impl._M_finish++ = __x; 00953 else 00954 _M_insert_aux(end(), __x); 00955 } 00956 00957 void 00958 swap(vector& __x) _GLIBCXX_NOEXCEPT 00959 { 00960 std::swap(this->_M_impl._M_start, __x._M_impl._M_start); 00961 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); 00962 std::swap(this->_M_impl._M_end_of_storage, 00963 __x._M_impl._M_end_of_storage); 00964 _Bit_alloc_traits::_S_on_swap(_M_get_Bit_allocator(), 00965 __x._M_get_Bit_allocator()); 00966 } 00967 00968 // [23.2.5]/1, third-to-last entry in synopsis listing 00969 static void 00970 swap(reference __x, reference __y) _GLIBCXX_NOEXCEPT 00971 { 00972 bool __tmp = __x; 00973 __x = __y; 00974 __y = __tmp; 00975 } 00976 00977 iterator 00978 #if __cplusplus >= 201103L 00979 insert(const_iterator __position, const bool& __x = bool()) 00980 #else 00981 insert(iterator __position, const bool& __x = bool()) 00982 #endif 00983 { 00984 const difference_type __n = __position - begin(); 00985 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr() 00986 && __position == end()) 00987 *this->_M_impl._M_finish++ = __x; 00988 else 00989 _M_insert_aux(__position._M_const_cast(), __x); 00990 return begin() + __n; 00991 } 00992 00993 #if __cplusplus >= 201103L 00994 template<typename _InputIterator, 00995 typename = std::_RequireInputIter<_InputIterator>> 00996 iterator 00997 insert(const_iterator __position, 00998 _InputIterator __first, _InputIterator __last) 00999 { 01000 difference_type __offset = __position - cbegin(); 01001 _M_insert_dispatch(__position._M_const_cast(), 01002 __first, __last, __false_type()); 01003 return begin() + __offset; 01004 } 01005 #else 01006 template<typename _InputIterator> 01007 void 01008 insert(iterator __position, 01009 _InputIterator __first, _InputIterator __last) 01010 { 01011 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 01012 _M_insert_dispatch(__position, __first, __last, _Integral()); 01013 } 01014 #endif 01015 01016 #if __cplusplus >= 201103L 01017 iterator 01018 insert(const_iterator __position, size_type __n, const bool& __x) 01019 { 01020 difference_type __offset = __position - cbegin(); 01021 _M_fill_insert(__position._M_const_cast(), __n, __x); 01022 return begin() + __offset; 01023 } 01024 #else 01025 void 01026 insert(iterator __position, size_type __n, const bool& __x) 01027 { _M_fill_insert(__position, __n, __x); } 01028 #endif 01029 01030 #if __cplusplus >= 201103L 01031 iterator 01032 insert(const_iterator __p, initializer_list<bool> __l) 01033 { return this->insert(__p, __l.begin(), __l.end()); } 01034 #endif 01035 01036 void 01037 pop_back() 01038 { --this->_M_impl._M_finish; } 01039 01040 iterator 01041 #if __cplusplus >= 201103L 01042 erase(const_iterator __position) 01043 #else 01044 erase(iterator __position) 01045 #endif 01046 { return _M_erase(__position._M_const_cast()); } 01047 01048 iterator 01049 #if __cplusplus >= 201103L 01050 erase(const_iterator __first, const_iterator __last) 01051 #else 01052 erase(iterator __first, iterator __last) 01053 #endif 01054 { return _M_erase(__first._M_const_cast(), __last._M_const_cast()); } 01055 01056 void 01057 resize(size_type __new_size, bool __x = bool()) 01058 { 01059 if (__new_size < size()) 01060 _M_erase_at_end(begin() + difference_type(__new_size)); 01061 else 01062 insert(end(), __new_size - size(), __x); 01063 } 01064 01065 #if __cplusplus >= 201103L 01066 void 01067 shrink_to_fit() 01068 { _M_shrink_to_fit(); } 01069 #endif 01070 01071 void 01072 flip() _GLIBCXX_NOEXCEPT 01073 { 01074 _Bit_type * const __end = this->_M_impl._M_end_addr(); 01075 for (_Bit_type * __p = this->_M_impl._M_start._M_p; __p != __end; ++__p) 01076 *__p = ~*__p; 01077 } 01078 01079 void 01080 clear() _GLIBCXX_NOEXCEPT 01081 { _M_erase_at_end(begin()); } 01082 01083 #if __cplusplus >= 201103L 01084 template<typename... _Args> 01085 #if __cplusplus > 201402L 01086 reference 01087 #else 01088 void 01089 #endif 01090 emplace_back(_Args&&... __args) 01091 { 01092 push_back(bool(__args...)); 01093 #if __cplusplus > 201402L 01094 return back(); 01095 #endif 01096 } 01097 01098 template<typename... _Args> 01099 iterator 01100 emplace(const_iterator __pos, _Args&&... __args) 01101 { return insert(__pos, bool(__args...)); } 01102 #endif 01103 01104 protected: 01105 // Precondition: __first._M_offset == 0 && __result._M_offset == 0. 01106 iterator 01107 _M_copy_aligned(const_iterator __first, const_iterator __last, 01108 iterator __result) 01109 { 01110 _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p); 01111 return std::copy(const_iterator(__last._M_p, 0), __last, 01112 iterator(__q, 0)); 01113 } 01114 01115 void 01116 _M_initialize(size_type __n) 01117 { 01118 if (__n) 01119 { 01120 _Bit_pointer __q = this->_M_allocate(__n); 01121 this->_M_impl._M_end_of_storage = __q + _S_nword(__n); 01122 this->_M_impl._M_start = iterator(std::__addressof(*__q), 0); 01123 } 01124 else 01125 { 01126 this->_M_impl._M_end_of_storage = _Bit_pointer(); 01127 this->_M_impl._M_start = iterator(0, 0); 01128 } 01129 this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n); 01130 01131 } 01132 01133 void 01134 _M_initialize_value(bool __x) 01135 { 01136 if (_Bit_type* __p = this->_M_impl._M_start._M_p) 01137 __builtin_memset(__p, __x ? ~0 : 0, 01138 (this->_M_impl._M_end_addr() - __p) 01139 * sizeof(_Bit_type)); 01140 } 01141 01142 void 01143 _M_reallocate(size_type __n); 01144 01145 #if __cplusplus >= 201103L 01146 bool 01147 _M_shrink_to_fit(); 01148 #endif 01149 01150 // Check whether it's an integral type. If so, it's not an iterator. 01151 01152 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01153 // 438. Ambiguity in the "do the right thing" clause 01154 template<typename _Integer> 01155 void 01156 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) 01157 { 01158 _M_initialize(static_cast<size_type>(__n)); 01159 _M_initialize_value(__x); 01160 } 01161 01162 template<typename _InputIterator> 01163 void 01164 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 01165 __false_type) 01166 { _M_initialize_range(__first, __last, 01167 std::__iterator_category(__first)); } 01168 01169 template<typename _InputIterator> 01170 void 01171 _M_initialize_range(_InputIterator __first, _InputIterator __last, 01172 std::input_iterator_tag) 01173 { 01174 for (; __first != __last; ++__first) 01175 push_back(*__first); 01176 } 01177 01178 template<typename _ForwardIterator> 01179 void 01180 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last, 01181 std::forward_iterator_tag) 01182 { 01183 const size_type __n = std::distance(__first, __last); 01184 _M_initialize(__n); 01185 std::copy(__first, __last, this->_M_impl._M_start); 01186 } 01187 01188 #if __cplusplus < 201103L 01189 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01190 // 438. Ambiguity in the "do the right thing" clause 01191 template<typename _Integer> 01192 void 01193 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 01194 { _M_fill_assign(__n, __val); } 01195 01196 template<class _InputIterator> 01197 void 01198 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 01199 __false_type) 01200 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } 01201 #endif 01202 01203 void 01204 _M_fill_assign(size_t __n, bool __x) 01205 { 01206 if (__n > size()) 01207 { 01208 _M_initialize_value(__x); 01209 insert(end(), __n - size(), __x); 01210 } 01211 else 01212 { 01213 _M_erase_at_end(begin() + __n); 01214 _M_initialize_value(__x); 01215 } 01216 } 01217 01218 template<typename _InputIterator> 01219 void 01220 _M_assign_aux(_InputIterator __first, _InputIterator __last, 01221 std::input_iterator_tag) 01222 { 01223 iterator __cur = begin(); 01224 for (; __first != __last && __cur != end(); ++__cur, ++__first) 01225 *__cur = *__first; 01226 if (__first == __last) 01227 _M_erase_at_end(__cur); 01228 else 01229 insert(end(), __first, __last); 01230 } 01231 01232 template<typename _ForwardIterator> 01233 void 01234 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 01235 std::forward_iterator_tag) 01236 { 01237 const size_type __len = std::distance(__first, __last); 01238 if (__len < size()) 01239 _M_erase_at_end(std::copy(__first, __last, begin())); 01240 else 01241 { 01242 _ForwardIterator __mid = __first; 01243 std::advance(__mid, size()); 01244 std::copy(__first, __mid, begin()); 01245 insert(end(), __mid, __last); 01246 } 01247 } 01248 01249 // Check whether it's an integral type. If so, it's not an iterator. 01250 01251 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01252 // 438. Ambiguity in the "do the right thing" clause 01253 template<typename _Integer> 01254 void 01255 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, 01256 __true_type) 01257 { _M_fill_insert(__pos, __n, __x); } 01258 01259 template<typename _InputIterator> 01260 void 01261 _M_insert_dispatch(iterator __pos, 01262 _InputIterator __first, _InputIterator __last, 01263 __false_type) 01264 { _M_insert_range(__pos, __first, __last, 01265 std::__iterator_category(__first)); } 01266 01267 void 01268 _M_fill_insert(iterator __position, size_type __n, bool __x); 01269 01270 template<typename _InputIterator> 01271 void 01272 _M_insert_range(iterator __pos, _InputIterator __first, 01273 _InputIterator __last, std::input_iterator_tag) 01274 { 01275 for (; __first != __last; ++__first) 01276 { 01277 __pos = insert(__pos, *__first); 01278 ++__pos; 01279 } 01280 } 01281 01282 template<typename _ForwardIterator> 01283 void 01284 _M_insert_range(iterator __position, _ForwardIterator __first, 01285 _ForwardIterator __last, std::forward_iterator_tag); 01286 01287 void 01288 _M_insert_aux(iterator __position, bool __x); 01289 01290 size_type 01291 _M_check_len(size_type __n, const char* __s) const 01292 { 01293 if (max_size() - size() < __n) 01294 __throw_length_error(__N(__s)); 01295 01296 const size_type __len = size() + std::max(size(), __n); 01297 return (__len < size() || __len > max_size()) ? max_size() : __len; 01298 } 01299 01300 void 01301 _M_erase_at_end(iterator __pos) 01302 { this->_M_impl._M_finish = __pos; } 01303 01304 iterator 01305 _M_erase(iterator __pos); 01306 01307 iterator 01308 _M_erase(iterator __first, iterator __last); 01309 }; 01310 01311 _GLIBCXX_END_NAMESPACE_CONTAINER 01312 _GLIBCXX_END_NAMESPACE_VERSION 01313 } // namespace std 01314 01315 #if __cplusplus >= 201103L 01316 01317 namespace std _GLIBCXX_VISIBILITY(default) 01318 { 01319 _GLIBCXX_BEGIN_NAMESPACE_VERSION 01320 01321 // DR 1182. 01322 /// std::hash specialization for vector<bool>. 01323 template<typename _Alloc> 01324 struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>> 01325 : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>> 01326 { 01327 size_t 01328 operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept; 01329 }; 01330 01331 _GLIBCXX_END_NAMESPACE_VERSION 01332 }// namespace std 01333 01334 #endif // C++11 01335 01336 #endif