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