libstdc++
|
00001 // vector<bool> specialization -*- C++ -*- 00002 00003 // Copyright (C) 2001-2015 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) 00931 #if __cplusplus >= 201103L 00932 noexcept(_Bit_alloc_traits::_S_nothrow_swap()) 00933 #endif 00934 { 00935 std::swap(this->_M_impl._M_start, __x._M_impl._M_start); 00936 std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish); 00937 std::swap(this->_M_impl._M_end_of_storage, 00938 __x._M_impl._M_end_of_storage); 00939 _Bit_alloc_traits::_S_on_swap(_M_get_Bit_allocator(), 00940 __x._M_get_Bit_allocator()); 00941 } 00942 00943 // [23.2.5]/1, third-to-last entry in synopsis listing 00944 static void 00945 swap(reference __x, reference __y) _GLIBCXX_NOEXCEPT 00946 { 00947 bool __tmp = __x; 00948 __x = __y; 00949 __y = __tmp; 00950 } 00951 00952 iterator 00953 #if __cplusplus >= 201103L 00954 insert(const_iterator __position, const bool& __x = bool()) 00955 #else 00956 insert(iterator __position, const bool& __x = bool()) 00957 #endif 00958 { 00959 const difference_type __n = __position - begin(); 00960 if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr() 00961 && __position == end()) 00962 *this->_M_impl._M_finish++ = __x; 00963 else 00964 _M_insert_aux(__position._M_const_cast(), __x); 00965 return begin() + __n; 00966 } 00967 00968 #if __cplusplus >= 201103L 00969 template<typename _InputIterator, 00970 typename = std::_RequireInputIter<_InputIterator>> 00971 iterator 00972 insert(const_iterator __position, 00973 _InputIterator __first, _InputIterator __last) 00974 { 00975 difference_type __offset = __position - cbegin(); 00976 _M_insert_dispatch(__position._M_const_cast(), 00977 __first, __last, __false_type()); 00978 return begin() + __offset; 00979 } 00980 #else 00981 template<typename _InputIterator> 00982 void 00983 insert(iterator __position, 00984 _InputIterator __first, _InputIterator __last) 00985 { 00986 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00987 _M_insert_dispatch(__position, __first, __last, _Integral()); 00988 } 00989 #endif 00990 00991 #if __cplusplus >= 201103L 00992 iterator 00993 insert(const_iterator __position, size_type __n, const bool& __x) 00994 { 00995 difference_type __offset = __position - cbegin(); 00996 _M_fill_insert(__position._M_const_cast(), __n, __x); 00997 return begin() + __offset; 00998 } 00999 #else 01000 void 01001 insert(iterator __position, size_type __n, const bool& __x) 01002 { _M_fill_insert(__position, __n, __x); } 01003 #endif 01004 01005 #if __cplusplus >= 201103L 01006 iterator 01007 insert(const_iterator __p, initializer_list<bool> __l) 01008 { return this->insert(__p, __l.begin(), __l.end()); } 01009 #endif 01010 01011 void 01012 pop_back() 01013 { --this->_M_impl._M_finish; } 01014 01015 iterator 01016 #if __cplusplus >= 201103L 01017 erase(const_iterator __position) 01018 #else 01019 erase(iterator __position) 01020 #endif 01021 { return _M_erase(__position._M_const_cast()); } 01022 01023 iterator 01024 #if __cplusplus >= 201103L 01025 erase(const_iterator __first, const_iterator __last) 01026 #else 01027 erase(iterator __first, iterator __last) 01028 #endif 01029 { return _M_erase(__first._M_const_cast(), __last._M_const_cast()); } 01030 01031 void 01032 resize(size_type __new_size, bool __x = bool()) 01033 { 01034 if (__new_size < size()) 01035 _M_erase_at_end(begin() + difference_type(__new_size)); 01036 else 01037 insert(end(), __new_size - size(), __x); 01038 } 01039 01040 #if __cplusplus >= 201103L 01041 void 01042 shrink_to_fit() 01043 { _M_shrink_to_fit(); } 01044 #endif 01045 01046 void 01047 flip() _GLIBCXX_NOEXCEPT 01048 { 01049 _Bit_type * const __end = this->_M_impl._M_end_addr(); 01050 for (_Bit_type * __p = this->_M_impl._M_start._M_p; __p != __end; ++__p) 01051 *__p = ~*__p; 01052 } 01053 01054 void 01055 clear() _GLIBCXX_NOEXCEPT 01056 { _M_erase_at_end(begin()); } 01057 01058 #if __cplusplus >= 201103L 01059 template<typename... _Args> 01060 void 01061 emplace_back(_Args&&... __args) 01062 { push_back(bool(__args...)); } 01063 01064 template<typename... _Args> 01065 iterator 01066 emplace(const_iterator __pos, _Args&&... __args) 01067 { return insert(__pos, bool(__args...)); } 01068 #endif 01069 01070 protected: 01071 // Precondition: __first._M_offset == 0 && __result._M_offset == 0. 01072 iterator 01073 _M_copy_aligned(const_iterator __first, const_iterator __last, 01074 iterator __result) 01075 { 01076 _Bit_type* __q = std::copy(__first._M_p, __last._M_p, __result._M_p); 01077 return std::copy(const_iterator(__last._M_p, 0), __last, 01078 iterator(__q, 0)); 01079 } 01080 01081 void 01082 _M_initialize(size_type __n) 01083 { 01084 _Bit_pointer __q = this->_M_allocate(__n); 01085 this->_M_impl._M_end_of_storage = __q + _S_nword(__n); 01086 this->_M_impl._M_start = iterator(std::__addressof(*__q), 0); 01087 this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n); 01088 } 01089 01090 void 01091 _M_reallocate(size_type __n); 01092 01093 #if __cplusplus >= 201103L 01094 bool 01095 _M_shrink_to_fit(); 01096 #endif 01097 01098 // Check whether it's an integral type. If so, it's not an iterator. 01099 01100 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01101 // 438. Ambiguity in the "do the right thing" clause 01102 template<typename _Integer> 01103 void 01104 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) 01105 { 01106 _M_initialize(static_cast<size_type>(__n)); 01107 std::fill(this->_M_impl._M_start._M_p, 01108 this->_M_impl._M_end_addr(), __x ? ~0 : 0); 01109 } 01110 01111 template<typename _InputIterator> 01112 void 01113 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, 01114 __false_type) 01115 { _M_initialize_range(__first, __last, 01116 std::__iterator_category(__first)); } 01117 01118 template<typename _InputIterator> 01119 void 01120 _M_initialize_range(_InputIterator __first, _InputIterator __last, 01121 std::input_iterator_tag) 01122 { 01123 for (; __first != __last; ++__first) 01124 push_back(*__first); 01125 } 01126 01127 template<typename _ForwardIterator> 01128 void 01129 _M_initialize_range(_ForwardIterator __first, _ForwardIterator __last, 01130 std::forward_iterator_tag) 01131 { 01132 const size_type __n = std::distance(__first, __last); 01133 _M_initialize(__n); 01134 std::copy(__first, __last, this->_M_impl._M_start); 01135 } 01136 01137 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01138 // 438. Ambiguity in the "do the right thing" clause 01139 template<typename _Integer> 01140 void 01141 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 01142 { _M_fill_assign(__n, __val); } 01143 01144 template<class _InputIterator> 01145 void 01146 _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 01147 __false_type) 01148 { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } 01149 01150 void 01151 _M_fill_assign(size_t __n, bool __x) 01152 { 01153 if (__n > size()) 01154 { 01155 std::fill(this->_M_impl._M_start._M_p, 01156 this->_M_impl._M_end_addr(), __x ? ~0 : 0); 01157 insert(end(), __n - size(), __x); 01158 } 01159 else 01160 { 01161 _M_erase_at_end(begin() + __n); 01162 std::fill(this->_M_impl._M_start._M_p, 01163 this->_M_impl._M_end_addr(), __x ? ~0 : 0); 01164 } 01165 } 01166 01167 template<typename _InputIterator> 01168 void 01169 _M_assign_aux(_InputIterator __first, _InputIterator __last, 01170 std::input_iterator_tag) 01171 { 01172 iterator __cur = begin(); 01173 for (; __first != __last && __cur != end(); ++__cur, ++__first) 01174 *__cur = *__first; 01175 if (__first == __last) 01176 _M_erase_at_end(__cur); 01177 else 01178 insert(end(), __first, __last); 01179 } 01180 01181 template<typename _ForwardIterator> 01182 void 01183 _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, 01184 std::forward_iterator_tag) 01185 { 01186 const size_type __len = std::distance(__first, __last); 01187 if (__len < size()) 01188 _M_erase_at_end(std::copy(__first, __last, begin())); 01189 else 01190 { 01191 _ForwardIterator __mid = __first; 01192 std::advance(__mid, size()); 01193 std::copy(__first, __mid, begin()); 01194 insert(end(), __mid, __last); 01195 } 01196 } 01197 01198 // Check whether it's an integral type. If so, it's not an iterator. 01199 01200 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01201 // 438. Ambiguity in the "do the right thing" clause 01202 template<typename _Integer> 01203 void 01204 _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x, 01205 __true_type) 01206 { _M_fill_insert(__pos, __n, __x); } 01207 01208 template<typename _InputIterator> 01209 void 01210 _M_insert_dispatch(iterator __pos, 01211 _InputIterator __first, _InputIterator __last, 01212 __false_type) 01213 { _M_insert_range(__pos, __first, __last, 01214 std::__iterator_category(__first)); } 01215 01216 void 01217 _M_fill_insert(iterator __position, size_type __n, bool __x); 01218 01219 template<typename _InputIterator> 01220 void 01221 _M_insert_range(iterator __pos, _InputIterator __first, 01222 _InputIterator __last, std::input_iterator_tag) 01223 { 01224 for (; __first != __last; ++__first) 01225 { 01226 __pos = insert(__pos, *__first); 01227 ++__pos; 01228 } 01229 } 01230 01231 template<typename _ForwardIterator> 01232 void 01233 _M_insert_range(iterator __position, _ForwardIterator __first, 01234 _ForwardIterator __last, std::forward_iterator_tag); 01235 01236 void 01237 _M_insert_aux(iterator __position, bool __x); 01238 01239 size_type 01240 _M_check_len(size_type __n, const char* __s) const 01241 { 01242 if (max_size() - size() < __n) 01243 __throw_length_error(__N(__s)); 01244 01245 const size_type __len = size() + std::max(size(), __n); 01246 return (__len < size() || __len > max_size()) ? max_size() : __len; 01247 } 01248 01249 void 01250 _M_erase_at_end(iterator __pos) 01251 { this->_M_impl._M_finish = __pos; } 01252 01253 iterator 01254 _M_erase(iterator __pos); 01255 01256 iterator 01257 _M_erase(iterator __first, iterator __last); 01258 }; 01259 01260 _GLIBCXX_END_NAMESPACE_CONTAINER 01261 } // namespace std 01262 01263 #if __cplusplus >= 201103L 01264 01265 #include <bits/functional_hash.h> 01266 01267 namespace std _GLIBCXX_VISIBILITY(default) 01268 { 01269 _GLIBCXX_BEGIN_NAMESPACE_VERSION 01270 01271 // DR 1182. 01272 /// std::hash specialization for vector<bool>. 01273 template<typename _Alloc> 01274 struct hash<_GLIBCXX_STD_C::vector<bool, _Alloc>> 01275 : public __hash_base<size_t, _GLIBCXX_STD_C::vector<bool, _Alloc>> 01276 { 01277 size_t 01278 operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>&) const noexcept; 01279 }; 01280 01281 _GLIBCXX_END_NAMESPACE_VERSION 01282 }// namespace std 01283 01284 #endif // C++11 01285 01286 #endif