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