libstdc++
|
00001 // vector<bool> specialization -*- C++ -*- 00002 00003 // Copyright (C) 2001-2017 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 __gnu_cxx::__alloc_traits<_Alloc>::template 00414 rebind<_Bit_type>::other _Bit_alloc_type; 00415 typedef typename __gnu_cxx::__alloc_traits<_Bit_alloc_type> 00416 _Bit_alloc_traits; 00417 typedef typename _Bit_alloc_traits::pointer _Bit_pointer; 00418 00419 struct _Bvector_impl 00420 : public _Bit_alloc_type 00421 { 00422 _Bit_iterator _M_start; 00423 _Bit_iterator _M_finish; 00424 _Bit_pointer _M_end_of_storage; 00425 00426 _Bvector_impl() 00427 : _Bit_alloc_type(), _M_start(), _M_finish(), _M_end_of_storage() 00428 { } 00429 00430 _Bvector_impl(const _Bit_alloc_type& __a) 00431 : _Bit_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage() 00432 { } 00433 00434 #if __cplusplus >= 201103L 00435 _Bvector_impl(_Bit_alloc_type&& __a) 00436 : _Bit_alloc_type(std::move(__a)), _M_start(), _M_finish(), 00437 _M_end_of_storage() 00438 { } 00439 #endif 00440 00441 _Bit_type* 00442 _M_end_addr() const _GLIBCXX_NOEXCEPT 00443 { 00444 if (_M_end_of_storage) 00445 return std::__addressof(_M_end_of_storage[-1]) + 1; 00446 return 0; 00447 } 00448 }; 00449 00450 public: 00451 typedef _Alloc allocator_type; 00452 00453 _Bit_alloc_type& 00454 _M_get_Bit_allocator() _GLIBCXX_NOEXCEPT 00455 { return *static_cast<_Bit_alloc_type*>(&this->_M_impl); } 00456 00457 const _Bit_alloc_type& 00458 _M_get_Bit_allocator() const _GLIBCXX_NOEXCEPT 00459 { return *static_cast<const _Bit_alloc_type*>(&this->_M_impl); } 00460 00461 allocator_type 00462 get_allocator() const _GLIBCXX_NOEXCEPT 00463 { return allocator_type(_M_get_Bit_allocator()); } 00464 00465 _Bvector_base() 00466 : _M_impl() { } 00467 00468 _Bvector_base(const allocator_type& __a) 00469 : _M_impl(__a) { } 00470 00471 #if __cplusplus >= 201103L 00472 _Bvector_base(_Bvector_base&& __x) noexcept 00473 : _M_impl(std::move(__x._M_get_Bit_allocator())) 00474 { 00475 this->_M_impl._M_start = __x._M_impl._M_start; 00476 this->_M_impl._M_finish = __x._M_impl._M_finish; 00477 this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; 00478 __x._M_impl._M_start = _Bit_iterator(); 00479 __x._M_impl._M_finish = _Bit_iterator(); 00480 __x._M_impl._M_end_of_storage = nullptr; 00481 } 00482 #endif 00483 00484 ~_Bvector_base() 00485 { this->_M_deallocate(); } 00486 00487 protected: 00488 _Bvector_impl _M_impl; 00489 00490 _Bit_pointer 00491 _M_allocate(size_t __n) 00492 { return _Bit_alloc_traits::allocate(_M_impl, _S_nword(__n)); } 00493 00494 void 00495 _M_deallocate() 00496 { 00497 if (_M_impl._M_start._M_p) 00498 { 00499 const size_t __n = _M_impl._M_end_addr() - _M_impl._M_start._M_p; 00500 _Bit_alloc_traits::deallocate(_M_impl, 00501 _M_impl._M_end_of_storage - __n, 00502 __n); 00503 _M_impl._M_start = _M_impl._M_finish = _Bit_iterator(); 00504 _M_impl._M_end_of_storage = _Bit_pointer(); 00505 } 00506 } 00507 00508 static size_t 00509 _S_nword(size_t __n) 00510 { return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); } 00511 }; 00512 00513 _GLIBCXX_END_NAMESPACE_CONTAINER 00514 } // namespace std 00515 00516 // Declare a partial specialization of vector<T, Alloc>. 00517 #include <bits/stl_vector.h> 00518 00519 namespace std _GLIBCXX_VISIBILITY(default) 00520 { 00521 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 00522 00523 /** 00524 * @brief A specialization of vector for booleans which offers fixed time 00525 * access to individual elements in any order. 00526 * 00527 * @ingroup sequences 00528 * 00529 * @tparam _Alloc Allocator type. 00530 * 00531 * Note that vector<bool> does not actually meet the requirements for being 00532 * a container. This is because the reference and pointer types are not 00533 * really references and pointers to bool. See DR96 for details. @see 00534 * vector for function documentation. 00535 * 00536 * In some terminology a %vector can be described as a dynamic 00537 * C-style array, it offers fast and efficient access to individual 00538 * elements in any order and saves the user from worrying about 00539 * memory and size allocation. Subscripting ( @c [] ) access is 00540 * also provided as with C-style arrays. 00541 */ 00542 template<typename _Alloc> 00543 class vector<bool, _Alloc> : protected _Bvector_base<_Alloc> 00544 { 00545 typedef _Bvector_base<_Alloc> _Base; 00546 typedef typename _Base::_Bit_pointer _Bit_pointer; 00547 typedef typename _Base::_Bit_alloc_traits _Bit_alloc_traits; 00548 00549 #if __cplusplus >= 201103L 00550 template<typename> friend struct hash; 00551 #endif 00552 00553 public: 00554 typedef bool value_type; 00555 typedef size_t size_type; 00556 typedef ptrdiff_t difference_type; 00557 typedef _Bit_reference reference; 00558 typedef bool const_reference; 00559 typedef _Bit_reference* pointer; 00560 typedef const bool* const_pointer; 00561 typedef _Bit_iterator iterator; 00562 typedef _Bit_const_iterator const_iterator; 00563 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00564 typedef std::reverse_iterator<iterator> reverse_iterator; 00565 typedef _Alloc allocator_type; 00566 00567 allocator_type get_allocator() const 00568 { return _Base::get_allocator(); } 00569 00570 protected: 00571 using _Base::_M_allocate; 00572 using _Base::_M_deallocate; 00573 using _Base::_S_nword; 00574 using _Base::_M_get_Bit_allocator; 00575 00576 public: 00577 vector() 00578 #if __cplusplus >= 201103L 00579 noexcept(is_nothrow_default_constructible<allocator_type>::value) 00580 #endif 00581 : _Base() { } 00582 00583 explicit 00584 vector(const allocator_type& __a) 00585 : _Base(__a) { } 00586 00587 #if __cplusplus >= 201103L 00588 explicit 00589 vector(size_type __n, const allocator_type& __a = allocator_type()) 00590 : vector(__n, false, __a) 00591 { } 00592 00593 vector(size_type __n, const bool& __value, 00594 const allocator_type& __a = allocator_type()) 00595 : _Base(__a) 00596 { 00597 _M_initialize(__n); 00598 std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_addr(), 00599 __value ? ~0 : 0); 00600 } 00601 #else 00602 explicit 00603 vector(size_type __n, const bool& __value = bool(), 00604 const allocator_type& __a = allocator_type()) 00605 : _Base(__a) 00606 { 00607 _M_initialize(__n); 00608 std::fill(this->_M_impl._M_start._M_p, this->_M_impl._M_end_addr(), 00609 __value ? ~0 : 0); 00610 } 00611 #endif 00612 00613 vector(const vector& __x) 00614 : _Base(_Bit_alloc_traits::_S_select_on_copy(__x._M_get_Bit_allocator())) 00615 { 00616 _M_initialize(__x.size()); 00617 _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start); 00618 } 00619 00620 #if __cplusplus >= 201103L 00621 vector(vector&& __x) noexcept 00622 : _Base(std::move(__x)) { } 00623 00624 vector(vector&& __x, const allocator_type& __a) 00625 noexcept(_Bit_alloc_traits::_S_always_equal()) 00626 : _Base(__a) 00627 { 00628 if (__x.get_allocator() == __a) 00629 { 00630 this->_M_impl._M_start = __x._M_impl._M_start; 00631 this->_M_impl._M_finish = __x._M_impl._M_finish; 00632 this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; 00633 __x._M_impl._M_start = _Bit_iterator(); 00634 __x._M_impl._M_finish = _Bit_iterator(); 00635 __x._M_impl._M_end_of_storage = nullptr; 00636 } 00637 else 00638 { 00639 _M_initialize(__x.size()); 00640 _M_copy_aligned(__x.begin(), __x.end(), begin()); 00641 __x.clear(); 00642 } 00643 } 00644 00645 vector(const vector& __x, const allocator_type& __a) 00646 : _Base(__a) 00647 { 00648 _M_initialize(__x.size()); 00649 _M_copy_aligned(__x.begin(), __x.end(), this->_M_impl._M_start); 00650 } 00651 00652 vector(initializer_list<bool> __l, 00653 const allocator_type& __a = allocator_type()) 00654 : _Base(__a) 00655 { 00656 _M_initialize_range(__l.begin(), __l.end(), 00657 random_access_iterator_tag()); 00658 } 00659 #endif 00660 00661 #if __cplusplus >= 201103L 00662 template<typename _InputIterator, 00663 typename = std::_RequireInputIter<_InputIterator>> 00664 vector(_InputIterator __first, _InputIterator __last, 00665 const allocator_type& __a = allocator_type()) 00666 : _Base(__a) 00667 { _M_initialize_dispatch(__first, __last, __false_type()); } 00668 #else 00669 template<typename _InputIterator> 00670 vector(_InputIterator __first, _InputIterator __last, 00671 const allocator_type& __a = allocator_type()) 00672 : _Base(__a) 00673 { 00674 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00675 _M_initialize_dispatch(__first, __last, _Integral()); 00676 } 00677 #endif 00678 00679 ~vector() _GLIBCXX_NOEXCEPT { } 00680 00681 vector& 00682 operator=(const vector& __x) 00683 { 00684 if (&__x == this) 00685 return *this; 00686 #if __cplusplus >= 201103L 00687 if (_Bit_alloc_traits::_S_propagate_on_copy_assign()) 00688 { 00689 if (this->_M_get_Bit_allocator() != __x._M_get_Bit_allocator()) 00690 { 00691 this->_M_deallocate(); 00692 std::__alloc_on_copy(_M_get_Bit_allocator(), 00693 __x._M_get_Bit_allocator()); 00694 _M_initialize(__x.size()); 00695 } 00696 else 00697 std::__alloc_on_copy(_M_get_Bit_allocator(), 00698 __x._M_get_Bit_allocator()); 00699 } 00700 #endif 00701 if (__x.size() > capacity()) 00702 { 00703 this->_M_deallocate(); 00704 _M_initialize(__x.size()); 00705 } 00706 this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(), 00707 begin()); 00708 return *this; 00709 } 00710 00711 #if __cplusplus >= 201103L 00712 vector& 00713 operator=(vector&& __x) noexcept(_Bit_alloc_traits::_S_nothrow_move()) 00714 { 00715 if (_Bit_alloc_traits::_S_propagate_on_move_assign() 00716 || this->_M_get_Bit_allocator() == __x._M_get_Bit_allocator()) 00717 { 00718 this->_M_deallocate(); 00719 this->_M_impl._M_start = __x._M_impl._M_start; 00720 this->_M_impl._M_finish = __x._M_impl._M_finish; 00721 this->_M_impl._M_end_of_storage = __x._M_impl._M_end_of_storage; 00722 __x._M_impl._M_start = _Bit_iterator(); 00723 __x._M_impl._M_finish = _Bit_iterator(); 00724 __x._M_impl._M_end_of_storage = nullptr; 00725 std::__alloc_on_move(_M_get_Bit_allocator(), 00726 __x._M_get_Bit_allocator()); 00727 } 00728 else 00729 { 00730 if (__x.size() > capacity()) 00731 { 00732 this->_M_deallocate(); 00733 _M_initialize(__x.size()); 00734 } 00735 this->_M_impl._M_finish = _M_copy_aligned(__x.begin(), __x.end(), 00736 begin()); 00737 __x.clear(); 00738 } 00739 return *this; 00740 } 00741 00742 vector& 00743 operator=(initializer_list<bool> __l) 00744 { 00745 this->assign (__l.begin(), __l.end()); 00746 return *this; 00747 } 00748 #endif 00749 00750 // assign(), a generalized assignment member function. Two 00751 // versions: one that takes a count, and one that takes a range. 00752 // The range version is a member template, so we dispatch on whether 00753 // or not the type is an integer. 00754 void 00755 assign(size_type __n, const bool& __x) 00756 { _M_fill_assign(__n, __x); } 00757 00758 #if __cplusplus >= 201103L 00759 template<typename _InputIterator, 00760 typename = std::_RequireInputIter<_InputIterator>> 00761 void 00762 assign(_InputIterator __first, _InputIterator __last) 00763 { _M_assign_dispatch(__first, __last, __false_type()); } 00764 #else 00765 template<typename _InputIterator> 00766 void 00767 assign(_InputIterator __first, _InputIterator __last) 00768 { 00769 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00770 _M_assign_dispatch(__first, __last, _Integral()); 00771 } 00772 #endif 00773 00774 #if __cplusplus >= 201103L 00775 void 00776 assign(initializer_list<bool> __l) 00777 { this->assign(__l.begin(), __l.end()); } 00778 #endif 00779 00780 iterator 00781 begin() _GLIBCXX_NOEXCEPT 00782 { return this->_M_impl._M_start; } 00783 00784 const_iterator 00785 begin() const _GLIBCXX_NOEXCEPT 00786 { return this->_M_impl._M_start; } 00787 00788 iterator 00789 end() _GLIBCXX_NOEXCEPT 00790 { return this->_M_impl._M_finish; } 00791 00792 const_iterator 00793 end() const _GLIBCXX_NOEXCEPT 00794 { return this->_M_impl._M_finish; } 00795 00796 reverse_iterator 00797 rbegin() _GLIBCXX_NOEXCEPT 00798 { return reverse_iterator(end()); } 00799 00800 const_reverse_iterator 00801 rbegin() const _GLIBCXX_NOEXCEPT 00802 { return const_reverse_iterator(end()); } 00803 00804 reverse_iterator 00805 rend() _GLIBCXX_NOEXCEPT 00806 { return reverse_iterator(begin()); } 00807 00808 const_reverse_iterator 00809 rend() const _GLIBCXX_NOEXCEPT 00810 { return const_reverse_iterator(begin()); } 00811 00812 #if __cplusplus >= 201103L 00813 const_iterator 00814 cbegin() const noexcept 00815 { return this->_M_impl._M_start; } 00816 00817 const_iterator 00818 cend() const noexcept 00819 { return this->_M_impl._M_finish; } 00820 00821 const_reverse_iterator 00822 crbegin() const noexcept 00823 { return const_reverse_iterator(end()); } 00824 00825 const_reverse_iterator 00826 crend() const noexcept 00827 { return const_reverse_iterator(begin()); } 00828 #endif 00829 00830 size_type 00831 size() const _GLIBCXX_NOEXCEPT 00832 { return size_type(end() - begin()); } 00833 00834 size_type 00835 max_size() const _GLIBCXX_NOEXCEPT 00836 { 00837 const size_type __isize = 00838 __gnu_cxx::__numeric_traits<difference_type>::__max 00839 - int(_S_word_bit) + 1; 00840 const size_type __asize 00841 = _Bit_alloc_traits::max_size(_M_get_Bit_allocator()); 00842 return (__asize <= __isize / int(_S_word_bit) 00843 ? __asize * int(_S_word_bit) : __isize); 00844 } 00845 00846 size_type 00847 capacity() const _GLIBCXX_NOEXCEPT 00848 { return size_type(const_iterator(this->_M_impl._M_end_addr(), 0) 00849 - begin()); } 00850 00851 bool 00852 empty() const _GLIBCXX_NOEXCEPT 00853 { return begin() == end(); } 00854 00855 reference 00856 operator[](size_type __n) 00857 { 00858 return *iterator(this->_M_impl._M_start._M_p 00859 + __n / int(_S_word_bit), __n % int(_S_word_bit)); 00860 } 00861 00862 const_reference 00863 operator[](size_type __n) const 00864 { 00865 return *const_iterator(this->_M_impl._M_start._M_p 00866 + __n / int(_S_word_bit), __n % int(_S_word_bit)); 00867 } 00868 00869 protected: 00870 void 00871 _M_range_check(size_type __n) const 00872 { 00873 if (__n >= this->size()) 00874 __throw_out_of_range_fmt(__N("vector<bool>::_M_range_check: __n " 00875 "(which is %zu) >= this->size() " 00876 "(which is %zu)"), 00877 __n, this->size()); 00878 } 00879 00880 public: 00881 reference 00882 at(size_type __n) 00883 { _M_range_check(__n); return (*this)[__n]; } 00884 00885 const_reference 00886 at(size_type __n) const 00887 { _M_range_check(__n); return (*this)[__n]; } 00888 00889 void 00890 reserve(size_type __n) 00891 { 00892 if (__n > max_size()) 00893 __throw_length_error(__N("vector::reserve")); 00894 if (capacity() < __n) 00895 _M_reallocate(__n); 00896 } 00897 00898 reference 00899 front() 00900 { return *begin(); } 00901 00902 const_reference 00903 front() const 00904 { return *begin(); } 00905 00906 reference 00907 back() 00908 { return *(end() - 1); } 00909 00910 const_reference 00911 back() const 00912 { return *(end() - 1); } 00913 00914 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00915 // DR 464. Suggestion for new member functions in standard containers. 00916 // N.B. DR 464 says nothing about vector<bool> but we need something 00917 // here due to the way we are implementing DR 464 in the debug-mode 00918 // vector class. 00919 void 00920 data() _GLIBCXX_NOEXCEPT { } 00921 00922 void 00923 push_back(bool __x) 00924 { 00925 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()) 00926 *this->_M_impl._M_finish++ = __x; 00927 else 00928 _M_insert_aux(end(), __x); 00929 } 00930 00931 void 00932 swap(vector& __x) _GLIBCXX_NOEXCEPT 00933 { 00934 std::swap(this->_M_impl._M_start, __x._M_impl._M_start); 00935 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); 00936 std::swap(this->_M_impl._M_end_of_storage, 00937 __x._M_impl._M_end_of_storage); 00938 _Bit_alloc_traits::_S_on_swap(_M_get_Bit_allocator(), 00939 __x._M_get_Bit_allocator()); 00940 } 00941 00942 // [23.2.5]/1, third-to-last entry in synopsis listing 00943 static void 00944 swap(reference __x, reference __y) _GLIBCXX_NOEXCEPT 00945 { 00946 bool __tmp = __x; 00947 __x = __y; 00948 __y = __tmp; 00949 } 00950 00951 iterator 00952 #if __cplusplus >= 201103L 00953 insert(const_iterator __position, const bool& __x = bool()) 00954 #else 00955 insert(iterator __position, const bool& __x = bool()) 00956 #endif 00957 { 00958 const difference_type __n = __position - begin(); 00959 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr() 00960 && __position == end()) 00961 *this->_M_impl._M_finish++ = __x; 00962 else 00963 _M_insert_aux(__position._M_const_cast(), __x); 00964 return begin() + __n; 00965 } 00966 00967 #if __cplusplus >= 201103L 00968 template<typename _InputIterator, 00969 typename = std::_RequireInputIter<_InputIterator>> 00970 iterator 00971 insert(const_iterator __position, 00972 _InputIterator __first, _InputIterator __last) 00973 { 00974 difference_type __offset = __position - cbegin(); 00975 _M_insert_dispatch(__position._M_const_cast(), 00976 __first, __last, __false_type()); 00977 return begin() + __offset; 00978 } 00979 #else 00980 template<typename _InputIterator> 00981 void 00982 insert(iterator __position, 00983 _InputIterator __first, _InputIterator __last) 00984 { 00985 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00986 _M_insert_dispatch(__position, __first, __last, _Integral()); 00987 } 00988 #endif 00989 00990 #if __cplusplus >= 201103L 00991 iterator 00992 insert(const_iterator __position, size_type __n, const bool& __x) 00993 { 00994 difference_type __offset = __position - cbegin(); 00995 _M_fill_insert(__position._M_const_cast(), __n, __x); 00996 return begin() + __offset; 00997 } 00998 #else 00999 void 01000 insert(iterator __position, size_type __n, const bool& __x) 01001 { _M_fill_insert(__position, __n, __x); } 01002 #endif 01003 01004 #if __cplusplus >= 201103L 01005 iterator 01006 insert(const_iterator __p, initializer_list<bool> __l) 01007 { return this->insert(__p, __l.begin(), __l.end()); } 01008 #endif 01009 01010 void 01011 pop_back() 01012 { --this->_M_impl._M_finish; } 01013 01014 iterator 01015 #if __cplusplus >= 201103L 01016 erase(const_iterator __position) 01017 #else 01018 erase(iterator __position) 01019 #endif 01020 { return _M_erase(__position._M_const_cast()); } 01021 01022 iterator 01023 #if __cplusplus >= 201103L 01024 erase(const_iterator __first, const_iterator __last) 01025 #else 01026 erase(iterator __first, iterator __last) 01027 #endif 01028 { return _M_erase(__first._M_const_cast(), __last._M_const_cast()); } 01029 01030 void 01031 resize(size_type __new_size, bool __x = bool()) 01032 { 01033 if (__new_size < size()) 01034 _M_erase_at_end(begin() + difference_type(__new_size)); 01035 else 01036 insert(end(), __new_size - size(), __x); 01037 } 01038 01039 #if __cplusplus >= 201103L 01040 void 01041 shrink_to_fit() 01042 { _M_shrink_to_fit(); } 01043 #endif 01044 01045 void 01046 flip() _GLIBCXX_NOEXCEPT 01047 { 01048 _Bit_type * const __end = this->_M_impl._M_end_addr(); 01049 for (_Bit_type * __p = this->_M_impl._M_start._M_p; __p != __end; ++__p) 01050 *__p = ~*__p; 01051 } 01052 01053 void 01054 clear() _GLIBCXX_NOEXCEPT 01055 { _M_erase_at_end(begin()); } 01056 01057 #if __cplusplus >= 201103L 01058 template<typename... _Args> 01059 #if __cplusplus > 201402L 01060 reference 01061 #else 01062 void 01063 #endif 01064 emplace_back(_Args&&... __args) 01065 { 01066 push_back(bool(__args...)); 01067 #if __cplusplus > 201402L 01068 return back(); 01069 #endif 01070 } 01071 01072 template<typename... _Args> 01073 iterator 01074 emplace(const_iterator __pos, _Args&&... __args) 01075 { return insert(__pos, bool(__args...)); } 01076 #endif 01077 01078 protected: 01079 // Precondition: __first._M_offset == 0 && __result._M_offset == 0. 01080 iterator 01081 _M_copy_aligned(const_iterator __first, const_iterator __last, 01082 iterator __result) 01083 { 01084 _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p); 01085 return std::copy(const_iterator(__last._M_p, 0), __last, 01086 iterator(__q, 0)); 01087 } 01088 01089 void 01090 _M_initialize(size_type __n) 01091 { 01092 _Bit_pointer __q = this->_M_allocate(__n); 01093 this->_M_impl._M_end_of_storage = __q + _S_nword(__n); 01094 this->_M_impl._M_start = iterator(std::__addressof(*__q), 0); 01095 this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n); 01096 } 01097 01098 void 01099 _M_reallocate(size_type __n); 01100 01101 #if __cplusplus >= 201103L 01102 bool 01103 _M_shrink_to_fit(); 01104 #endif 01105 01106 // Check whether it's an integral type. If so, it's not an iterator. 01107 01108 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01109 // 438. Ambiguity in the "do the right thing" clause 01110 template<typename _Integer> 01111 void 01112 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) 01113 { 01114 _M_initialize(static_cast<size_type>(__n)); 01115 std::fill(this->_M_impl._M_start._M_p, 01116 this->_M_impl._M_end_addr(), __x ? ~0 : 0); 01117 } 01118 01119 template<typename _InputIterator> 01120 void 01121 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 01122 __false_type) 01123 { _M_initialize_range(__first, __last, 01124 std::__iterator_category(__first)); } 01125 01126 template<typename _InputIterator> 01127 void 01128 _M_initialize_range(_InputIterator __first, _InputIterator __last, 01129 std::input_iterator_tag) 01130 { 01131 for (; __first != __last; ++__first) 01132 push_back(*__first); 01133 } 01134 01135 template<typename _ForwardIterator> 01136 void 01137 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last, 01138 std::forward_iterator_tag) 01139 { 01140 const size_type __n = std::distance(__first, __last); 01141 _M_initialize(__n); 01142 std::copy(__first, __last, this->_M_impl._M_start); 01143 } 01144 01145 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01146 // 438. Ambiguity in the "do the right thing" clause 01147 template<typename _Integer> 01148 void 01149 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 01150 { _M_fill_assign(__n, __val); } 01151 01152 template<class _InputIterator> 01153 void 01154 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 01155 __false_type) 01156 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } 01157 01158 void 01159 _M_fill_assign(size_t __n, bool __x) 01160 { 01161 if (__n > size()) 01162 { 01163 std::fill(this->_M_impl._M_start._M_p, 01164 this->_M_impl._M_end_addr(), __x ? ~0 : 0); 01165 insert(end(), __n - size(), __x); 01166 } 01167 else 01168 { 01169 _M_erase_at_end(begin() + __n); 01170 std::fill(this->_M_impl._M_start._M_p, 01171 this->_M_impl._M_end_addr(), __x ? ~0 : 0); 01172 } 01173 } 01174 01175 template<typename _InputIterator> 01176 void 01177 _M_assign_aux(_InputIterator __first, _InputIterator __last, 01178 std::input_iterator_tag) 01179 { 01180 iterator __cur = begin(); 01181 for (; __first != __last && __cur != end(); ++__cur, ++__first) 01182 *__cur = *__first; 01183 if (__first == __last) 01184 _M_erase_at_end(__cur); 01185 else 01186 insert(end(), __first, __last); 01187 } 01188 01189 template<typename _ForwardIterator> 01190 void 01191 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 01192 std::forward_iterator_tag) 01193 { 01194 const size_type __len = std::distance(__first, __last); 01195 if (__len < size()) 01196 _M_erase_at_end(std::copy(__first, __last, begin())); 01197 else 01198 { 01199 _ForwardIterator __mid = __first; 01200 std::advance(__mid, size()); 01201 std::copy(__first, __mid, begin()); 01202 insert(end(), __mid, __last); 01203 } 01204 } 01205 01206 // Check whether it's an integral type. If so, it's not an iterator. 01207 01208 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01209 // 438. Ambiguity in the "do the right thing" clause 01210 template<typename _Integer> 01211 void 01212 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, 01213 __true_type) 01214 { _M_fill_insert(__pos, __n, __x); } 01215 01216 template<typename _InputIterator> 01217 void 01218 _M_insert_dispatch(iterator __pos, 01219 _InputIterator __first, _InputIterator __last, 01220 __false_type) 01221 { _M_insert_range(__pos, __first, __last, 01222 std::__iterator_category(__first)); } 01223 01224 void 01225 _M_fill_insert(iterator __position, size_type __n, bool __x); 01226 01227 template<typename _InputIterator> 01228 void 01229 _M_insert_range(iterator __pos, _InputIterator __first, 01230 _InputIterator __last, std::input_iterator_tag) 01231 { 01232 for (; __first != __last; ++__first) 01233 { 01234 __pos = insert(__pos, *__first); 01235 ++__pos; 01236 } 01237 } 01238 01239 template<typename _ForwardIterator> 01240 void 01241 _M_insert_range(iterator __position, _ForwardIterator __first, 01242 _ForwardIterator __last, std::forward_iterator_tag); 01243 01244 void 01245 _M_insert_aux(iterator __position, bool __x); 01246 01247 size_type 01248 _M_check_len(size_type __n, const char* __s) const 01249 { 01250 if (max_size() - size() < __n) 01251 __throw_length_error(__N(__s)); 01252 01253 const size_type __len = size() + std::max(size(), __n); 01254 return (__len < size() || __len > max_size()) ? max_size() : __len; 01255 } 01256 01257 void 01258 _M_erase_at_end(iterator __pos) 01259 { this->_M_impl._M_finish = __pos; } 01260 01261 iterator 01262 _M_erase(iterator __pos); 01263 01264 iterator 01265 _M_erase(iterator __first, iterator __last); 01266 }; 01267 01268 _GLIBCXX_END_NAMESPACE_CONTAINER 01269 } // namespace std 01270 01271 #if __cplusplus >= 201103L 01272 01273 #include <bits/functional_hash.h> 01274 01275 namespace std _GLIBCXX_VISIBILITY(default) 01276 { 01277 _GLIBCXX_BEGIN_NAMESPACE_VERSION 01278 01279 // DR 1182. 01280 /// std::hash specialization for vector<bool>. 01281 template<typename _Alloc> 01282 struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>> 01283 : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>> 01284 { 01285 size_t 01286 operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept; 01287 }; 01288 01289 _GLIBCXX_END_NAMESPACE_VERSION 01290 }// namespace std 01291 01292 #endif // C++11 01293 01294 #endif