libstdc++
|
00001 // <bitset> -*- C++ -*- 00002 00003 // Copyright (C) 2001-2018 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /* 00026 * Copyright (c) 1998 00027 * Silicon Graphics Computer Systems, Inc. 00028 * 00029 * Permission to use, copy, modify, distribute and sell this software 00030 * and its documentation for any purpose is hereby granted without fee, 00031 * provided that the above copyright notice appear in all copies and 00032 * that both that copyright notice and this permission notice appear 00033 * in supporting documentation. Silicon Graphics makes no 00034 * representations about the suitability of this software for any 00035 * purpose. It is provided "as is" without express or implied warranty. 00036 */ 00037 00038 /** @file include/bitset 00039 * This is a Standard C++ Library header. 00040 */ 00041 00042 #ifndef _GLIBCXX_BITSET 00043 #define _GLIBCXX_BITSET 1 00044 00045 #pragma GCC system_header 00046 00047 #include <string> 00048 #include <bits/functexcept.h> // For invalid_argument, out_of_range, 00049 // overflow_error 00050 #include <iosfwd> 00051 #include <bits/cxxabi_forced.h> 00052 00053 #if __cplusplus >= 201103L 00054 # include <bits/functional_hash.h> 00055 #endif 00056 00057 #define _GLIBCXX_BITSET_BITS_PER_WORD (__CHAR_BIT__ * __SIZEOF_LONG__) 00058 #define _GLIBCXX_BITSET_WORDS(__n) \ 00059 ((__n) / _GLIBCXX_BITSET_BITS_PER_WORD + \ 00060 ((__n) % _GLIBCXX_BITSET_BITS_PER_WORD == 0 ? 0 : 1)) 00061 00062 #define _GLIBCXX_BITSET_BITS_PER_ULL (__CHAR_BIT__ * __SIZEOF_LONG_LONG__) 00063 00064 namespace std _GLIBCXX_VISIBILITY(default) 00065 { 00066 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 00067 00068 /** 00069 * Base class, general case. It is a class invariant that _Nw will be 00070 * nonnegative. 00071 * 00072 * See documentation for bitset. 00073 */ 00074 template<size_t _Nw> 00075 struct _Base_bitset 00076 { 00077 typedef unsigned long _WordT; 00078 00079 /// 0 is the least significant word. 00080 _WordT _M_w[_Nw]; 00081 00082 _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT 00083 : _M_w() { } 00084 00085 #if __cplusplus >= 201103L 00086 constexpr _Base_bitset(unsigned long long __val) noexcept 00087 : _M_w{ _WordT(__val) 00088 #if __SIZEOF_LONG_LONG__ > __SIZEOF_LONG__ 00089 , _WordT(__val >> _GLIBCXX_BITSET_BITS_PER_WORD) 00090 #endif 00091 } { } 00092 #else 00093 _Base_bitset(unsigned long __val) 00094 : _M_w() 00095 { _M_w[0] = __val; } 00096 #endif 00097 00098 static _GLIBCXX_CONSTEXPR size_t 00099 _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT 00100 { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } 00101 00102 static _GLIBCXX_CONSTEXPR size_t 00103 _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT 00104 { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } 00105 00106 static _GLIBCXX_CONSTEXPR size_t 00107 _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT 00108 { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } 00109 00110 static _GLIBCXX_CONSTEXPR _WordT 00111 _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT 00112 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 00113 00114 _WordT& 00115 _M_getword(size_t __pos) _GLIBCXX_NOEXCEPT 00116 { return _M_w[_S_whichword(__pos)]; } 00117 00118 _GLIBCXX_CONSTEXPR _WordT 00119 _M_getword(size_t __pos) const _GLIBCXX_NOEXCEPT 00120 { return _M_w[_S_whichword(__pos)]; } 00121 00122 #if __cplusplus >= 201103L 00123 const _WordT* 00124 _M_getdata() const noexcept 00125 { return _M_w; } 00126 #endif 00127 00128 _WordT& 00129 _M_hiword() _GLIBCXX_NOEXCEPT 00130 { return _M_w[_Nw - 1]; } 00131 00132 _GLIBCXX_CONSTEXPR _WordT 00133 _M_hiword() const _GLIBCXX_NOEXCEPT 00134 { return _M_w[_Nw - 1]; } 00135 00136 void 00137 _M_do_and(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT 00138 { 00139 for (size_t __i = 0; __i < _Nw; __i++) 00140 _M_w[__i] &= __x._M_w[__i]; 00141 } 00142 00143 void 00144 _M_do_or(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT 00145 { 00146 for (size_t __i = 0; __i < _Nw; __i++) 00147 _M_w[__i] |= __x._M_w[__i]; 00148 } 00149 00150 void 00151 _M_do_xor(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT 00152 { 00153 for (size_t __i = 0; __i < _Nw; __i++) 00154 _M_w[__i] ^= __x._M_w[__i]; 00155 } 00156 00157 void 00158 _M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT; 00159 00160 void 00161 _M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT; 00162 00163 void 00164 _M_do_flip() _GLIBCXX_NOEXCEPT 00165 { 00166 for (size_t __i = 0; __i < _Nw; __i++) 00167 _M_w[__i] = ~_M_w[__i]; 00168 } 00169 00170 void 00171 _M_do_set() _GLIBCXX_NOEXCEPT 00172 { 00173 for (size_t __i = 0; __i < _Nw; __i++) 00174 _M_w[__i] = ~static_cast<_WordT>(0); 00175 } 00176 00177 void 00178 _M_do_reset() _GLIBCXX_NOEXCEPT 00179 { __builtin_memset(_M_w, 0, _Nw * sizeof(_WordT)); } 00180 00181 bool 00182 _M_is_equal(const _Base_bitset<_Nw>& __x) const _GLIBCXX_NOEXCEPT 00183 { 00184 for (size_t __i = 0; __i < _Nw; ++__i) 00185 if (_M_w[__i] != __x._M_w[__i]) 00186 return false; 00187 return true; 00188 } 00189 00190 template<size_t _Nb> 00191 bool 00192 _M_are_all() const _GLIBCXX_NOEXCEPT 00193 { 00194 for (size_t __i = 0; __i < _Nw - 1; __i++) 00195 if (_M_w[__i] != ~static_cast<_WordT>(0)) 00196 return false; 00197 return _M_hiword() == (~static_cast<_WordT>(0) 00198 >> (_Nw * _GLIBCXX_BITSET_BITS_PER_WORD 00199 - _Nb)); 00200 } 00201 00202 bool 00203 _M_is_any() const _GLIBCXX_NOEXCEPT 00204 { 00205 for (size_t __i = 0; __i < _Nw; __i++) 00206 if (_M_w[__i] != static_cast<_WordT>(0)) 00207 return true; 00208 return false; 00209 } 00210 00211 size_t 00212 _M_do_count() const _GLIBCXX_NOEXCEPT 00213 { 00214 size_t __result = 0; 00215 for (size_t __i = 0; __i < _Nw; __i++) 00216 __result += __builtin_popcountl(_M_w[__i]); 00217 return __result; 00218 } 00219 00220 unsigned long 00221 _M_do_to_ulong() const; 00222 00223 #if __cplusplus >= 201103L 00224 unsigned long long 00225 _M_do_to_ullong() const; 00226 #endif 00227 00228 // find first "on" bit 00229 size_t 00230 _M_do_find_first(size_t) const _GLIBCXX_NOEXCEPT; 00231 00232 // find the next "on" bit that follows "prev" 00233 size_t 00234 _M_do_find_next(size_t, size_t) const _GLIBCXX_NOEXCEPT; 00235 }; 00236 00237 // Definitions of non-inline functions from _Base_bitset. 00238 template<size_t _Nw> 00239 void 00240 _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT 00241 { 00242 if (__builtin_expect(__shift != 0, 1)) 00243 { 00244 const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD; 00245 const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD; 00246 00247 if (__offset == 0) 00248 for (size_t __n = _Nw - 1; __n >= __wshift; --__n) 00249 _M_w[__n] = _M_w[__n - __wshift]; 00250 else 00251 { 00252 const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD 00253 - __offset); 00254 for (size_t __n = _Nw - 1; __n > __wshift; --__n) 00255 _M_w[__n] = ((_M_w[__n - __wshift] << __offset) 00256 | (_M_w[__n - __wshift - 1] >> __sub_offset)); 00257 _M_w[__wshift] = _M_w[0] << __offset; 00258 } 00259 00260 std::fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0)); 00261 } 00262 } 00263 00264 template<size_t _Nw> 00265 void 00266 _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT 00267 { 00268 if (__builtin_expect(__shift != 0, 1)) 00269 { 00270 const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD; 00271 const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD; 00272 const size_t __limit = _Nw - __wshift - 1; 00273 00274 if (__offset == 0) 00275 for (size_t __n = 0; __n <= __limit; ++__n) 00276 _M_w[__n] = _M_w[__n + __wshift]; 00277 else 00278 { 00279 const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD 00280 - __offset); 00281 for (size_t __n = 0; __n < __limit; ++__n) 00282 _M_w[__n] = ((_M_w[__n + __wshift] >> __offset) 00283 | (_M_w[__n + __wshift + 1] << __sub_offset)); 00284 _M_w[__limit] = _M_w[_Nw-1] >> __offset; 00285 } 00286 00287 std::fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0)); 00288 } 00289 } 00290 00291 template<size_t _Nw> 00292 unsigned long 00293 _Base_bitset<_Nw>::_M_do_to_ulong() const 00294 { 00295 for (size_t __i = 1; __i < _Nw; ++__i) 00296 if (_M_w[__i]) 00297 __throw_overflow_error(__N("_Base_bitset::_M_do_to_ulong")); 00298 return _M_w[0]; 00299 } 00300 00301 #if __cplusplus >= 201103L 00302 template<size_t _Nw> 00303 unsigned long long 00304 _Base_bitset<_Nw>::_M_do_to_ullong() const 00305 { 00306 const bool __dw = sizeof(unsigned long long) > sizeof(unsigned long); 00307 for (size_t __i = 1 + __dw; __i < _Nw; ++__i) 00308 if (_M_w[__i]) 00309 __throw_overflow_error(__N("_Base_bitset::_M_do_to_ullong")); 00310 00311 if (__dw) 00312 return _M_w[0] + (static_cast<unsigned long long>(_M_w[1]) 00313 << _GLIBCXX_BITSET_BITS_PER_WORD); 00314 return _M_w[0]; 00315 } 00316 #endif 00317 00318 template<size_t _Nw> 00319 size_t 00320 _Base_bitset<_Nw>:: 00321 _M_do_find_first(size_t __not_found) const _GLIBCXX_NOEXCEPT 00322 { 00323 for (size_t __i = 0; __i < _Nw; __i++) 00324 { 00325 _WordT __thisword = _M_w[__i]; 00326 if (__thisword != static_cast<_WordT>(0)) 00327 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD 00328 + __builtin_ctzl(__thisword)); 00329 } 00330 // not found, so return an indication of failure. 00331 return __not_found; 00332 } 00333 00334 template<size_t _Nw> 00335 size_t 00336 _Base_bitset<_Nw>:: 00337 _M_do_find_next(size_t __prev, size_t __not_found) const _GLIBCXX_NOEXCEPT 00338 { 00339 // make bound inclusive 00340 ++__prev; 00341 00342 // check out of bounds 00343 if (__prev >= _Nw * _GLIBCXX_BITSET_BITS_PER_WORD) 00344 return __not_found; 00345 00346 // search first word 00347 size_t __i = _S_whichword(__prev); 00348 _WordT __thisword = _M_w[__i]; 00349 00350 // mask off bits below bound 00351 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev); 00352 00353 if (__thisword != static_cast<_WordT>(0)) 00354 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD 00355 + __builtin_ctzl(__thisword)); 00356 00357 // check subsequent words 00358 __i++; 00359 for (; __i < _Nw; __i++) 00360 { 00361 __thisword = _M_w[__i]; 00362 if (__thisword != static_cast<_WordT>(0)) 00363 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD 00364 + __builtin_ctzl(__thisword)); 00365 } 00366 // not found, so return an indication of failure. 00367 return __not_found; 00368 } // end _M_do_find_next 00369 00370 /** 00371 * Base class, specialization for a single word. 00372 * 00373 * See documentation for bitset. 00374 */ 00375 template<> 00376 struct _Base_bitset<1> 00377 { 00378 typedef unsigned long _WordT; 00379 _WordT _M_w; 00380 00381 _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT 00382 : _M_w(0) 00383 { } 00384 00385 #if __cplusplus >= 201103L 00386 constexpr _Base_bitset(unsigned long long __val) noexcept 00387 #else 00388 _Base_bitset(unsigned long __val) 00389 #endif 00390 : _M_w(__val) 00391 { } 00392 00393 static _GLIBCXX_CONSTEXPR size_t 00394 _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT 00395 { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } 00396 00397 static _GLIBCXX_CONSTEXPR size_t 00398 _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT 00399 { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } 00400 00401 static _GLIBCXX_CONSTEXPR size_t 00402 _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT 00403 { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } 00404 00405 static _GLIBCXX_CONSTEXPR _WordT 00406 _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT 00407 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 00408 00409 _WordT& 00410 _M_getword(size_t) _GLIBCXX_NOEXCEPT 00411 { return _M_w; } 00412 00413 _GLIBCXX_CONSTEXPR _WordT 00414 _M_getword(size_t) const _GLIBCXX_NOEXCEPT 00415 { return _M_w; } 00416 00417 #if __cplusplus >= 201103L 00418 const _WordT* 00419 _M_getdata() const noexcept 00420 { return &_M_w; } 00421 #endif 00422 00423 _WordT& 00424 _M_hiword() _GLIBCXX_NOEXCEPT 00425 { return _M_w; } 00426 00427 _GLIBCXX_CONSTEXPR _WordT 00428 _M_hiword() const _GLIBCXX_NOEXCEPT 00429 { return _M_w; } 00430 00431 void 00432 _M_do_and(const _Base_bitset<1>& __x) _GLIBCXX_NOEXCEPT 00433 { _M_w &= __x._M_w; } 00434 00435 void 00436 _M_do_or(const _Base_bitset<1>& __x) _GLIBCXX_NOEXCEPT 00437 { _M_w |= __x._M_w; } 00438 00439 void 00440 _M_do_xor(const _Base_bitset<1>& __x) _GLIBCXX_NOEXCEPT 00441 { _M_w ^= __x._M_w; } 00442 00443 void 00444 _M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT 00445 { _M_w <<= __shift; } 00446 00447 void 00448 _M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT 00449 { _M_w >>= __shift; } 00450 00451 void 00452 _M_do_flip() _GLIBCXX_NOEXCEPT 00453 { _M_w = ~_M_w; } 00454 00455 void 00456 _M_do_set() _GLIBCXX_NOEXCEPT 00457 { _M_w = ~static_cast<_WordT>(0); } 00458 00459 void 00460 _M_do_reset() _GLIBCXX_NOEXCEPT 00461 { _M_w = 0; } 00462 00463 bool 00464 _M_is_equal(const _Base_bitset<1>& __x) const _GLIBCXX_NOEXCEPT 00465 { return _M_w == __x._M_w; } 00466 00467 template<size_t _Nb> 00468 bool 00469 _M_are_all() const _GLIBCXX_NOEXCEPT 00470 { return _M_w == (~static_cast<_WordT>(0) 00471 >> (_GLIBCXX_BITSET_BITS_PER_WORD - _Nb)); } 00472 00473 bool 00474 _M_is_any() const _GLIBCXX_NOEXCEPT 00475 { return _M_w != 0; } 00476 00477 size_t 00478 _M_do_count() const _GLIBCXX_NOEXCEPT 00479 { return __builtin_popcountl(_M_w); } 00480 00481 unsigned long 00482 _M_do_to_ulong() const _GLIBCXX_NOEXCEPT 00483 { return _M_w; } 00484 00485 #if __cplusplus >= 201103L 00486 unsigned long long 00487 _M_do_to_ullong() const noexcept 00488 { return _M_w; } 00489 #endif 00490 00491 size_t 00492 _M_do_find_first(size_t __not_found) const _GLIBCXX_NOEXCEPT 00493 { 00494 if (_M_w != 0) 00495 return __builtin_ctzl(_M_w); 00496 else 00497 return __not_found; 00498 } 00499 00500 // find the next "on" bit that follows "prev" 00501 size_t 00502 _M_do_find_next(size_t __prev, size_t __not_found) const 00503 _GLIBCXX_NOEXCEPT 00504 { 00505 ++__prev; 00506 if (__prev >= ((size_t) _GLIBCXX_BITSET_BITS_PER_WORD)) 00507 return __not_found; 00508 00509 _WordT __x = _M_w >> __prev; 00510 if (__x != 0) 00511 return __builtin_ctzl(__x) + __prev; 00512 else 00513 return __not_found; 00514 } 00515 }; 00516 00517 /** 00518 * Base class, specialization for no storage (zero-length %bitset). 00519 * 00520 * See documentation for bitset. 00521 */ 00522 template<> 00523 struct _Base_bitset<0> 00524 { 00525 typedef unsigned long _WordT; 00526 00527 _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT 00528 { } 00529 00530 #if __cplusplus >= 201103L 00531 constexpr _Base_bitset(unsigned long long) noexcept 00532 #else 00533 _Base_bitset(unsigned long) 00534 #endif 00535 { } 00536 00537 static _GLIBCXX_CONSTEXPR size_t 00538 _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT 00539 { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } 00540 00541 static _GLIBCXX_CONSTEXPR size_t 00542 _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT 00543 { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } 00544 00545 static _GLIBCXX_CONSTEXPR size_t 00546 _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT 00547 { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } 00548 00549 static _GLIBCXX_CONSTEXPR _WordT 00550 _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT 00551 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 00552 00553 // This would normally give access to the data. The bounds-checking 00554 // in the bitset class will prevent the user from getting this far, 00555 // but (1) it must still return an lvalue to compile, and (2) the 00556 // user might call _Unchecked_set directly, in which case this /needs/ 00557 // to fail. Let's not penalize zero-length users unless they actually 00558 // make an unchecked call; all the memory ugliness is therefore 00559 // localized to this single should-never-get-this-far function. 00560 _WordT& 00561 _M_getword(size_t) _GLIBCXX_NOEXCEPT 00562 { 00563 __throw_out_of_range(__N("_Base_bitset::_M_getword")); 00564 return *new _WordT; 00565 } 00566 00567 _GLIBCXX_CONSTEXPR _WordT 00568 _M_getword(size_t) const _GLIBCXX_NOEXCEPT 00569 { return 0; } 00570 00571 _GLIBCXX_CONSTEXPR _WordT 00572 _M_hiword() const _GLIBCXX_NOEXCEPT 00573 { return 0; } 00574 00575 void 00576 _M_do_and(const _Base_bitset<0>&) _GLIBCXX_NOEXCEPT 00577 { } 00578 00579 void 00580 _M_do_or(const _Base_bitset<0>&) _GLIBCXX_NOEXCEPT 00581 { } 00582 00583 void 00584 _M_do_xor(const _Base_bitset<0>&) _GLIBCXX_NOEXCEPT 00585 { } 00586 00587 void 00588 _M_do_left_shift(size_t) _GLIBCXX_NOEXCEPT 00589 { } 00590 00591 void 00592 _M_do_right_shift(size_t) _GLIBCXX_NOEXCEPT 00593 { } 00594 00595 void 00596 _M_do_flip() _GLIBCXX_NOEXCEPT 00597 { } 00598 00599 void 00600 _M_do_set() _GLIBCXX_NOEXCEPT 00601 { } 00602 00603 void 00604 _M_do_reset() _GLIBCXX_NOEXCEPT 00605 { } 00606 00607 // Are all empty bitsets equal to each other? Are they equal to 00608 // themselves? How to compare a thing which has no state? What is 00609 // the sound of one zero-length bitset clapping? 00610 bool 00611 _M_is_equal(const _Base_bitset<0>&) const _GLIBCXX_NOEXCEPT 00612 { return true; } 00613 00614 template<size_t _Nb> 00615 bool 00616 _M_are_all() const _GLIBCXX_NOEXCEPT 00617 { return true; } 00618 00619 bool 00620 _M_is_any() const _GLIBCXX_NOEXCEPT 00621 { return false; } 00622 00623 size_t 00624 _M_do_count() const _GLIBCXX_NOEXCEPT 00625 { return 0; } 00626 00627 unsigned long 00628 _M_do_to_ulong() const _GLIBCXX_NOEXCEPT 00629 { return 0; } 00630 00631 #if __cplusplus >= 201103L 00632 unsigned long long 00633 _M_do_to_ullong() const noexcept 00634 { return 0; } 00635 #endif 00636 00637 // Normally "not found" is the size, but that could also be 00638 // misinterpreted as an index in this corner case. Oh well. 00639 size_t 00640 _M_do_find_first(size_t) const _GLIBCXX_NOEXCEPT 00641 { return 0; } 00642 00643 size_t 00644 _M_do_find_next(size_t, size_t) const _GLIBCXX_NOEXCEPT 00645 { return 0; } 00646 }; 00647 00648 00649 // Helper class to zero out the unused high-order bits in the highest word. 00650 template<size_t _Extrabits> 00651 struct _Sanitize 00652 { 00653 typedef unsigned long _WordT; 00654 00655 static void 00656 _S_do_sanitize(_WordT& __val) _GLIBCXX_NOEXCEPT 00657 { __val &= ~((~static_cast<_WordT>(0)) << _Extrabits); } 00658 }; 00659 00660 template<> 00661 struct _Sanitize<0> 00662 { 00663 typedef unsigned long _WordT; 00664 00665 static void 00666 _S_do_sanitize(_WordT) _GLIBCXX_NOEXCEPT { } 00667 }; 00668 00669 #if __cplusplus >= 201103L 00670 template<size_t _Nb, bool = (_Nb < _GLIBCXX_BITSET_BITS_PER_ULL)> 00671 struct _Sanitize_val 00672 { 00673 static constexpr unsigned long long 00674 _S_do_sanitize_val(unsigned long long __val) 00675 { return __val; } 00676 }; 00677 00678 template<size_t _Nb> 00679 struct _Sanitize_val<_Nb, true> 00680 { 00681 static constexpr unsigned long long 00682 _S_do_sanitize_val(unsigned long long __val) 00683 { return __val & ~((~static_cast<unsigned long long>(0)) << _Nb); } 00684 }; 00685 #endif 00686 00687 /** 00688 * @brief The %bitset class represents a @e fixed-size sequence of bits. 00689 * @ingroup utilities 00690 * 00691 * (Note that %bitset does @e not meet the formal requirements of a 00692 * <a href="tables.html#65">container</a>. Mainly, it lacks iterators.) 00693 * 00694 * The template argument, @a Nb, may be any non-negative number, 00695 * specifying the number of bits (e.g., "0", "12", "1024*1024"). 00696 * 00697 * In the general unoptimized case, storage is allocated in word-sized 00698 * blocks. Let B be the number of bits in a word, then (Nb+(B-1))/B 00699 * words will be used for storage. B - Nb%B bits are unused. (They are 00700 * the high-order bits in the highest word.) It is a class invariant 00701 * that those unused bits are always zero. 00702 * 00703 * If you think of %bitset as <em>a simple array of bits</em>, be 00704 * aware that your mental picture is reversed: a %bitset behaves 00705 * the same way as bits in integers do, with the bit at index 0 in 00706 * the <em>least significant / right-hand</em> position, and the bit at 00707 * index Nb-1 in the <em>most significant / left-hand</em> position. 00708 * Thus, unlike other containers, a %bitset's index <em>counts from 00709 * right to left</em>, to put it very loosely. 00710 * 00711 * This behavior is preserved when translating to and from strings. For 00712 * example, the first line of the following program probably prints 00713 * <em>b('a') is 0001100001</em> on a modern ASCII system. 00714 * 00715 * @code 00716 * #include <bitset> 00717 * #include <iostream> 00718 * #include <sstream> 00719 * 00720 * using namespace std; 00721 * 00722 * int main() 00723 * { 00724 * long a = 'a'; 00725 * bitset<10> b(a); 00726 * 00727 * cout << "b('a') is " << b << endl; 00728 * 00729 * ostringstream s; 00730 * s << b; 00731 * string str = s.str(); 00732 * cout << "index 3 in the string is " << str[3] << " but\n" 00733 * << "index 3 in the bitset is " << b[3] << endl; 00734 * } 00735 * @endcode 00736 * 00737 * Also see: 00738 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/ext_containers.html 00739 * for a description of extensions. 00740 * 00741 * Most of the actual code isn't contained in %bitset<> itself, but in the 00742 * base class _Base_bitset. The base class works with whole words, not with 00743 * individual bits. This allows us to specialize _Base_bitset for the 00744 * important special case where the %bitset is only a single word. 00745 * 00746 * Extra confusion can result due to the fact that the storage for 00747 * _Base_bitset @e is a regular array, and is indexed as such. This is 00748 * carefully encapsulated. 00749 */ 00750 template<size_t _Nb> 00751 class bitset 00752 : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> 00753 { 00754 private: 00755 typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base; 00756 typedef unsigned long _WordT; 00757 00758 template<class _CharT, class _Traits, class _Alloc> 00759 void 00760 _M_check_initial_position(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 00761 size_t __position) const 00762 { 00763 if (__position > __s.size()) 00764 __throw_out_of_range_fmt(__N("bitset::bitset: __position " 00765 "(which is %zu) > __s.size() " 00766 "(which is %zu)"), 00767 __position, __s.size()); 00768 } 00769 00770 void _M_check(size_t __position, const char *__s) const 00771 { 00772 if (__position >= _Nb) 00773 __throw_out_of_range_fmt(__N("%s: __position (which is %zu) " 00774 ">= _Nb (which is %zu)"), 00775 __s, __position, _Nb); 00776 } 00777 00778 void 00779 _M_do_sanitize() _GLIBCXX_NOEXCEPT 00780 { 00781 typedef _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD> __sanitize_type; 00782 __sanitize_type::_S_do_sanitize(this->_M_hiword()); 00783 } 00784 00785 #if __cplusplus >= 201103L 00786 friend struct std::hash<bitset>; 00787 #endif 00788 00789 public: 00790 /** 00791 * This encapsulates the concept of a single bit. An instance of this 00792 * class is a proxy for an actual bit; this way the individual bit 00793 * operations are done as faster word-size bitwise instructions. 00794 * 00795 * Most users will never need to use this class directly; conversions 00796 * to and from bool are automatic and should be transparent. Overloaded 00797 * operators help to preserve the illusion. 00798 * 00799 * (On a typical system, this <em>bit %reference</em> is 64 00800 * times the size of an actual bit. Ha.) 00801 */ 00802 class reference 00803 { 00804 friend class bitset; 00805 00806 _WordT* _M_wp; 00807 size_t _M_bpos; 00808 00809 // left undefined 00810 reference(); 00811 00812 public: 00813 reference(bitset& __b, size_t __pos) _GLIBCXX_NOEXCEPT 00814 { 00815 _M_wp = &__b._M_getword(__pos); 00816 _M_bpos = _Base::_S_whichbit(__pos); 00817 } 00818 00819 ~reference() _GLIBCXX_NOEXCEPT 00820 { } 00821 00822 // For b[i] = __x; 00823 reference& 00824 operator=(bool __x) _GLIBCXX_NOEXCEPT 00825 { 00826 if (__x) 00827 *_M_wp |= _Base::_S_maskbit(_M_bpos); 00828 else 00829 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 00830 return *this; 00831 } 00832 00833 // For b[i] = b[__j]; 00834 reference& 00835 operator=(const reference& __j) _GLIBCXX_NOEXCEPT 00836 { 00837 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos))) 00838 *_M_wp |= _Base::_S_maskbit(_M_bpos); 00839 else 00840 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 00841 return *this; 00842 } 00843 00844 // Flips the bit 00845 bool 00846 operator~() const _GLIBCXX_NOEXCEPT 00847 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; } 00848 00849 // For __x = b[i]; 00850 operator bool() const _GLIBCXX_NOEXCEPT 00851 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; } 00852 00853 // For b[i].flip(); 00854 reference& 00855 flip() _GLIBCXX_NOEXCEPT 00856 { 00857 *_M_wp ^= _Base::_S_maskbit(_M_bpos); 00858 return *this; 00859 } 00860 }; 00861 friend class reference; 00862 00863 // 23.3.5.1 constructors: 00864 /// All bits set to zero. 00865 _GLIBCXX_CONSTEXPR bitset() _GLIBCXX_NOEXCEPT 00866 { } 00867 00868 /// Initial bits bitwise-copied from a single word (others set to zero). 00869 #if __cplusplus >= 201103L 00870 constexpr bitset(unsigned long long __val) noexcept 00871 : _Base(_Sanitize_val<_Nb>::_S_do_sanitize_val(__val)) { } 00872 #else 00873 bitset(unsigned long __val) 00874 : _Base(__val) 00875 { _M_do_sanitize(); } 00876 #endif 00877 00878 /** 00879 * Use a subset of a string. 00880 * @param __s A string of @a 0 and @a 1 characters. 00881 * @param __position Index of the first character in @a __s to use; 00882 * defaults to zero. 00883 * @throw std::out_of_range If @a pos is bigger the size of @a __s. 00884 * @throw std::invalid_argument If a character appears in the string 00885 * which is neither @a 0 nor @a 1. 00886 */ 00887 template<class _CharT, class _Traits, class _Alloc> 00888 explicit 00889 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 00890 size_t __position = 0) 00891 : _Base() 00892 { 00893 _M_check_initial_position(__s, __position); 00894 _M_copy_from_string(__s, __position, 00895 std::basic_string<_CharT, _Traits, _Alloc>::npos, 00896 _CharT('0'), _CharT('1')); 00897 } 00898 00899 /** 00900 * Use a subset of a string. 00901 * @param __s A string of @a 0 and @a 1 characters. 00902 * @param __position Index of the first character in @a __s to use. 00903 * @param __n The number of characters to copy. 00904 * @throw std::out_of_range If @a __position is bigger the size 00905 * of @a __s. 00906 * @throw std::invalid_argument If a character appears in the string 00907 * which is neither @a 0 nor @a 1. 00908 */ 00909 template<class _CharT, class _Traits, class _Alloc> 00910 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 00911 size_t __position, size_t __n) 00912 : _Base() 00913 { 00914 _M_check_initial_position(__s, __position); 00915 _M_copy_from_string(__s, __position, __n, _CharT('0'), _CharT('1')); 00916 } 00917 00918 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00919 // 396. what are characters zero and one. 00920 template<class _CharT, class _Traits, class _Alloc> 00921 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 00922 size_t __position, size_t __n, 00923 _CharT __zero, _CharT __one = _CharT('1')) 00924 : _Base() 00925 { 00926 _M_check_initial_position(__s, __position); 00927 _M_copy_from_string(__s, __position, __n, __zero, __one); 00928 } 00929 00930 #if __cplusplus >= 201103L 00931 /** 00932 * Construct from a character %array. 00933 * @param __str An %array of characters @a zero and @a one. 00934 * @param __n The number of characters to use. 00935 * @param __zero The character corresponding to the value 0. 00936 * @param __one The character corresponding to the value 1. 00937 * @throw std::invalid_argument If a character appears in the string 00938 * which is neither @a __zero nor @a __one. 00939 */ 00940 template<typename _CharT> 00941 explicit 00942 bitset(const _CharT* __str, 00943 typename std::basic_string<_CharT>::size_type __n 00944 = std::basic_string<_CharT>::npos, 00945 _CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) 00946 : _Base() 00947 { 00948 if (!__str) 00949 __throw_logic_error(__N("bitset::bitset(const _CharT*, ...)")); 00950 00951 if (__n == std::basic_string<_CharT>::npos) 00952 __n = std::char_traits<_CharT>::length(__str); 00953 _M_copy_from_ptr<_CharT, std::char_traits<_CharT>>(__str, __n, 0, 00954 __n, __zero, 00955 __one); 00956 } 00957 #endif 00958 00959 // 23.3.5.2 bitset operations: 00960 //@{ 00961 /** 00962 * Operations on bitsets. 00963 * @param __rhs A same-sized bitset. 00964 * 00965 * These should be self-explanatory. 00966 */ 00967 bitset<_Nb>& 00968 operator&=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT 00969 { 00970 this->_M_do_and(__rhs); 00971 return *this; 00972 } 00973 00974 bitset<_Nb>& 00975 operator|=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT 00976 { 00977 this->_M_do_or(__rhs); 00978 return *this; 00979 } 00980 00981 bitset<_Nb>& 00982 operator^=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT 00983 { 00984 this->_M_do_xor(__rhs); 00985 return *this; 00986 } 00987 //@} 00988 00989 //@{ 00990 /** 00991 * Operations on bitsets. 00992 * @param __position The number of places to shift. 00993 * 00994 * These should be self-explanatory. 00995 */ 00996 bitset<_Nb>& 00997 operator<<=(size_t __position) _GLIBCXX_NOEXCEPT 00998 { 00999 if (__builtin_expect(__position < _Nb, 1)) 01000 { 01001 this->_M_do_left_shift(__position); 01002 this->_M_do_sanitize(); 01003 } 01004 else 01005 this->_M_do_reset(); 01006 return *this; 01007 } 01008 01009 bitset<_Nb>& 01010 operator>>=(size_t __position) _GLIBCXX_NOEXCEPT 01011 { 01012 if (__builtin_expect(__position < _Nb, 1)) 01013 { 01014 this->_M_do_right_shift(__position); 01015 this->_M_do_sanitize(); 01016 } 01017 else 01018 this->_M_do_reset(); 01019 return *this; 01020 } 01021 //@} 01022 01023 //@{ 01024 /** 01025 * These versions of single-bit set, reset, flip, and test are 01026 * extensions from the SGI version. They do no range checking. 01027 * @ingroup SGIextensions 01028 */ 01029 bitset<_Nb>& 01030 _Unchecked_set(size_t __pos) _GLIBCXX_NOEXCEPT 01031 { 01032 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 01033 return *this; 01034 } 01035 01036 bitset<_Nb>& 01037 _Unchecked_set(size_t __pos, int __val) _GLIBCXX_NOEXCEPT 01038 { 01039 if (__val) 01040 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 01041 else 01042 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 01043 return *this; 01044 } 01045 01046 bitset<_Nb>& 01047 _Unchecked_reset(size_t __pos) _GLIBCXX_NOEXCEPT 01048 { 01049 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 01050 return *this; 01051 } 01052 01053 bitset<_Nb>& 01054 _Unchecked_flip(size_t __pos) _GLIBCXX_NOEXCEPT 01055 { 01056 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); 01057 return *this; 01058 } 01059 01060 _GLIBCXX_CONSTEXPR bool 01061 _Unchecked_test(size_t __pos) const _GLIBCXX_NOEXCEPT 01062 { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) 01063 != static_cast<_WordT>(0)); } 01064 //@} 01065 01066 // Set, reset, and flip. 01067 /** 01068 * @brief Sets every bit to true. 01069 */ 01070 bitset<_Nb>& 01071 set() _GLIBCXX_NOEXCEPT 01072 { 01073 this->_M_do_set(); 01074 this->_M_do_sanitize(); 01075 return *this; 01076 } 01077 01078 /** 01079 * @brief Sets a given bit to a particular value. 01080 * @param __position The index of the bit. 01081 * @param __val Either true or false, defaults to true. 01082 * @throw std::out_of_range If @a pos is bigger the size of the %set. 01083 */ 01084 bitset<_Nb>& 01085 set(size_t __position, bool __val = true) 01086 { 01087 this->_M_check(__position, __N("bitset::set")); 01088 return _Unchecked_set(__position, __val); 01089 } 01090 01091 /** 01092 * @brief Sets every bit to false. 01093 */ 01094 bitset<_Nb>& 01095 reset() _GLIBCXX_NOEXCEPT 01096 { 01097 this->_M_do_reset(); 01098 return *this; 01099 } 01100 01101 /** 01102 * @brief Sets a given bit to false. 01103 * @param __position The index of the bit. 01104 * @throw std::out_of_range If @a pos is bigger the size of the %set. 01105 * 01106 * Same as writing @c set(pos,false). 01107 */ 01108 bitset<_Nb>& 01109 reset(size_t __position) 01110 { 01111 this->_M_check(__position, __N("bitset::reset")); 01112 return _Unchecked_reset(__position); 01113 } 01114 01115 /** 01116 * @brief Toggles every bit to its opposite value. 01117 */ 01118 bitset<_Nb>& 01119 flip() _GLIBCXX_NOEXCEPT 01120 { 01121 this->_M_do_flip(); 01122 this->_M_do_sanitize(); 01123 return *this; 01124 } 01125 01126 /** 01127 * @brief Toggles a given bit to its opposite value. 01128 * @param __position The index of the bit. 01129 * @throw std::out_of_range If @a pos is bigger the size of the %set. 01130 */ 01131 bitset<_Nb>& 01132 flip(size_t __position) 01133 { 01134 this->_M_check(__position, __N("bitset::flip")); 01135 return _Unchecked_flip(__position); 01136 } 01137 01138 /// See the no-argument flip(). 01139 bitset<_Nb> 01140 operator~() const _GLIBCXX_NOEXCEPT 01141 { return bitset<_Nb>(*this).flip(); } 01142 01143 //@{ 01144 /** 01145 * @brief Array-indexing support. 01146 * @param __position Index into the %bitset. 01147 * @return A bool for a <em>const %bitset</em>. For non-const 01148 * bitsets, an instance of the reference proxy class. 01149 * @note These operators do no range checking and throw no exceptions, 01150 * as required by DR 11 to the standard. 01151 * 01152 * _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already 01153 * resolves DR 11 (items 1 and 2), but does not do the range-checking 01154 * required by that DR's resolution. -pme 01155 * The DR has since been changed: range-checking is a precondition 01156 * (users' responsibility), and these functions must not throw. -pme 01157 */ 01158 reference 01159 operator[](size_t __position) 01160 { return reference(*this, __position); } 01161 01162 _GLIBCXX_CONSTEXPR bool 01163 operator[](size_t __position) const 01164 { return _Unchecked_test(__position); } 01165 //@} 01166 01167 /** 01168 * @brief Returns a numerical interpretation of the %bitset. 01169 * @return The integral equivalent of the bits. 01170 * @throw std::overflow_error If there are too many bits to be 01171 * represented in an @c unsigned @c long. 01172 */ 01173 unsigned long 01174 to_ulong() const 01175 { return this->_M_do_to_ulong(); } 01176 01177 #if __cplusplus >= 201103L 01178 unsigned long long 01179 to_ullong() const 01180 { return this->_M_do_to_ullong(); } 01181 #endif 01182 01183 /** 01184 * @brief Returns a character interpretation of the %bitset. 01185 * @return The string equivalent of the bits. 01186 * 01187 * Note the ordering of the bits: decreasing character positions 01188 * correspond to increasing bit positions (see the main class notes for 01189 * an example). 01190 */ 01191 template<class _CharT, class _Traits, class _Alloc> 01192 std::basic_string<_CharT, _Traits, _Alloc> 01193 to_string() const 01194 { 01195 std::basic_string<_CharT, _Traits, _Alloc> __result; 01196 _M_copy_to_string(__result, _CharT('0'), _CharT('1')); 01197 return __result; 01198 } 01199 01200 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01201 // 396. what are characters zero and one. 01202 template<class _CharT, class _Traits, class _Alloc> 01203 std::basic_string<_CharT, _Traits, _Alloc> 01204 to_string(_CharT __zero, _CharT __one = _CharT('1')) const 01205 { 01206 std::basic_string<_CharT, _Traits, _Alloc> __result; 01207 _M_copy_to_string(__result, __zero, __one); 01208 return __result; 01209 } 01210 01211 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01212 // 434. bitset::to_string() hard to use. 01213 template<class _CharT, class _Traits> 01214 std::basic_string<_CharT, _Traits, std::allocator<_CharT> > 01215 to_string() const 01216 { return to_string<_CharT, _Traits, std::allocator<_CharT> >(); } 01217 01218 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01219 // 853. to_string needs updating with zero and one. 01220 template<class _CharT, class _Traits> 01221 std::basic_string<_CharT, _Traits, std::allocator<_CharT> > 01222 to_string(_CharT __zero, _CharT __one = _CharT('1')) const 01223 { return to_string<_CharT, _Traits, 01224 std::allocator<_CharT> >(__zero, __one); } 01225 01226 template<class _CharT> 01227 std::basic_string<_CharT, std::char_traits<_CharT>, 01228 std::allocator<_CharT> > 01229 to_string() const 01230 { 01231 return to_string<_CharT, std::char_traits<_CharT>, 01232 std::allocator<_CharT> >(); 01233 } 01234 01235 template<class _CharT> 01236 std::basic_string<_CharT, std::char_traits<_CharT>, 01237 std::allocator<_CharT> > 01238 to_string(_CharT __zero, _CharT __one = _CharT('1')) const 01239 { 01240 return to_string<_CharT, std::char_traits<_CharT>, 01241 std::allocator<_CharT> >(__zero, __one); 01242 } 01243 01244 std::basic_string<char, std::char_traits<char>, std::allocator<char> > 01245 to_string() const 01246 { 01247 return to_string<char, std::char_traits<char>, 01248 std::allocator<char> >(); 01249 } 01250 01251 std::basic_string<char, std::char_traits<char>, std::allocator<char> > 01252 to_string(char __zero, char __one = '1') const 01253 { 01254 return to_string<char, std::char_traits<char>, 01255 std::allocator<char> >(__zero, __one); 01256 } 01257 01258 // Helper functions for string operations. 01259 template<class _CharT, class _Traits> 01260 void 01261 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t, 01262 _CharT, _CharT); 01263 01264 template<class _CharT, class _Traits, class _Alloc> 01265 void 01266 _M_copy_from_string(const std::basic_string<_CharT, 01267 _Traits, _Alloc>& __s, size_t __pos, size_t __n, 01268 _CharT __zero, _CharT __one) 01269 { _M_copy_from_ptr<_CharT, _Traits>(__s.data(), __s.size(), __pos, __n, 01270 __zero, __one); } 01271 01272 template<class _CharT, class _Traits, class _Alloc> 01273 void 01274 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>&, 01275 _CharT, _CharT) const; 01276 01277 // NB: Backward compat. 01278 template<class _CharT, class _Traits, class _Alloc> 01279 void 01280 _M_copy_from_string(const std::basic_string<_CharT, 01281 _Traits, _Alloc>& __s, size_t __pos, size_t __n) 01282 { _M_copy_from_string(__s, __pos, __n, _CharT('0'), _CharT('1')); } 01283 01284 template<class _CharT, class _Traits, class _Alloc> 01285 void 01286 _M_copy_to_string(std::basic_string<_CharT, _Traits,_Alloc>& __s) const 01287 { _M_copy_to_string(__s, _CharT('0'), _CharT('1')); } 01288 01289 /// Returns the number of bits which are set. 01290 size_t 01291 count() const _GLIBCXX_NOEXCEPT 01292 { return this->_M_do_count(); } 01293 01294 /// Returns the total number of bits. 01295 _GLIBCXX_CONSTEXPR size_t 01296 size() const _GLIBCXX_NOEXCEPT 01297 { return _Nb; } 01298 01299 //@{ 01300 /// These comparisons for equality/inequality are, well, @e bitwise. 01301 bool 01302 operator==(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT 01303 { return this->_M_is_equal(__rhs); } 01304 01305 bool 01306 operator!=(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT 01307 { return !this->_M_is_equal(__rhs); } 01308 //@} 01309 01310 /** 01311 * @brief Tests the value of a bit. 01312 * @param __position The index of a bit. 01313 * @return The value at @a pos. 01314 * @throw std::out_of_range If @a pos is bigger the size of the %set. 01315 */ 01316 bool 01317 test(size_t __position) const 01318 { 01319 this->_M_check(__position, __N("bitset::test")); 01320 return _Unchecked_test(__position); 01321 } 01322 01323 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01324 // DR 693. std::bitset::all() missing. 01325 /** 01326 * @brief Tests whether all the bits are on. 01327 * @return True if all the bits are set. 01328 */ 01329 bool 01330 all() const _GLIBCXX_NOEXCEPT 01331 { return this->template _M_are_all<_Nb>(); } 01332 01333 /** 01334 * @brief Tests whether any of the bits are on. 01335 * @return True if at least one bit is set. 01336 */ 01337 bool 01338 any() const _GLIBCXX_NOEXCEPT 01339 { return this->_M_is_any(); } 01340 01341 /** 01342 * @brief Tests whether any of the bits are on. 01343 * @return True if none of the bits are set. 01344 */ 01345 bool 01346 none() const _GLIBCXX_NOEXCEPT 01347 { return !this->_M_is_any(); } 01348 01349 //@{ 01350 /// Self-explanatory. 01351 bitset<_Nb> 01352 operator<<(size_t __position) const _GLIBCXX_NOEXCEPT 01353 { return bitset<_Nb>(*this) <<= __position; } 01354 01355 bitset<_Nb> 01356 operator>>(size_t __position) const _GLIBCXX_NOEXCEPT 01357 { return bitset<_Nb>(*this) >>= __position; } 01358 //@} 01359 01360 /** 01361 * @brief Finds the index of the first "on" bit. 01362 * @return The index of the first bit set, or size() if not found. 01363 * @ingroup SGIextensions 01364 * @sa _Find_next 01365 */ 01366 size_t 01367 _Find_first() const _GLIBCXX_NOEXCEPT 01368 { return this->_M_do_find_first(_Nb); } 01369 01370 /** 01371 * @brief Finds the index of the next "on" bit after prev. 01372 * @return The index of the next bit set, or size() if not found. 01373 * @param __prev Where to start searching. 01374 * @ingroup SGIextensions 01375 * @sa _Find_first 01376 */ 01377 size_t 01378 _Find_next(size_t __prev) const _GLIBCXX_NOEXCEPT 01379 { return this->_M_do_find_next(__prev, _Nb); } 01380 }; 01381 01382 // Definitions of non-inline member functions. 01383 template<size_t _Nb> 01384 template<class _CharT, class _Traits> 01385 void 01386 bitset<_Nb>:: 01387 _M_copy_from_ptr(const _CharT* __s, size_t __len, 01388 size_t __pos, size_t __n, _CharT __zero, _CharT __one) 01389 { 01390 reset(); 01391 const size_t __nbits = std::min(_Nb, std::min(__n, size_t(__len - __pos))); 01392 for (size_t __i = __nbits; __i > 0; --__i) 01393 { 01394 const _CharT __c = __s[__pos + __nbits - __i]; 01395 if (_Traits::eq(__c, __zero)) 01396 ; 01397 else if (_Traits::eq(__c, __one)) 01398 _Unchecked_set(__i - 1); 01399 else 01400 __throw_invalid_argument(__N("bitset::_M_copy_from_ptr")); 01401 } 01402 } 01403 01404 template<size_t _Nb> 01405 template<class _CharT, class _Traits, class _Alloc> 01406 void 01407 bitset<_Nb>:: 01408 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>& __s, 01409 _CharT __zero, _CharT __one) const 01410 { 01411 __s.assign(_Nb, __zero); 01412 for (size_t __i = _Nb; __i > 0; --__i) 01413 if (_Unchecked_test(__i - 1)) 01414 _Traits::assign(__s[_Nb - __i], __one); 01415 } 01416 01417 // 23.3.5.3 bitset operations: 01418 //@{ 01419 /** 01420 * @brief Global bitwise operations on bitsets. 01421 * @param __x A bitset. 01422 * @param __y A bitset of the same size as @a __x. 01423 * @return A new bitset. 01424 * 01425 * These should be self-explanatory. 01426 */ 01427 template<size_t _Nb> 01428 inline bitset<_Nb> 01429 operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT 01430 { 01431 bitset<_Nb> __result(__x); 01432 __result &= __y; 01433 return __result; 01434 } 01435 01436 template<size_t _Nb> 01437 inline bitset<_Nb> 01438 operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT 01439 { 01440 bitset<_Nb> __result(__x); 01441 __result |= __y; 01442 return __result; 01443 } 01444 01445 template <size_t _Nb> 01446 inline bitset<_Nb> 01447 operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT 01448 { 01449 bitset<_Nb> __result(__x); 01450 __result ^= __y; 01451 return __result; 01452 } 01453 //@} 01454 01455 //@{ 01456 /** 01457 * @brief Global I/O operators for bitsets. 01458 * 01459 * Direct I/O between streams and bitsets is supported. Output is 01460 * straightforward. Input will skip whitespace, only accept @a 0 and @a 1 01461 * characters, and will only extract as many digits as the %bitset will 01462 * hold. 01463 */ 01464 template<class _CharT, class _Traits, size_t _Nb> 01465 std::basic_istream<_CharT, _Traits>& 01466 operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x) 01467 { 01468 typedef typename _Traits::char_type char_type; 01469 typedef std::basic_istream<_CharT, _Traits> __istream_type; 01470 typedef typename __istream_type::ios_base __ios_base; 01471 01472 std::basic_string<_CharT, _Traits> __tmp; 01473 __tmp.reserve(_Nb); 01474 01475 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01476 // 303. Bitset input operator underspecified 01477 const char_type __zero = __is.widen('0'); 01478 const char_type __one = __is.widen('1'); 01479 01480 typename __ios_base::iostate __state = __ios_base::goodbit; 01481 typename __istream_type::sentry __sentry(__is); 01482 if (__sentry) 01483 { 01484 __try 01485 { 01486 for (size_t __i = _Nb; __i > 0; --__i) 01487 { 01488 static typename _Traits::int_type __eof = _Traits::eof(); 01489 01490 typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc(); 01491 if (_Traits::eq_int_type(__c1, __eof)) 01492 { 01493 __state |= __ios_base::eofbit; 01494 break; 01495 } 01496 else 01497 { 01498 const char_type __c2 = _Traits::to_char_type(__c1); 01499 if (_Traits::eq(__c2, __zero)) 01500 __tmp.push_back(__zero); 01501 else if (_Traits::eq(__c2, __one)) 01502 __tmp.push_back(__one); 01503 else if (_Traits:: 01504 eq_int_type(__is.rdbuf()->sputbackc(__c2), 01505 __eof)) 01506 { 01507 __state |= __ios_base::failbit; 01508 break; 01509 } 01510 } 01511 } 01512 } 01513 __catch(__cxxabiv1::__forced_unwind&) 01514 { 01515 __is._M_setstate(__ios_base::badbit); 01516 __throw_exception_again; 01517 } 01518 __catch(...) 01519 { __is._M_setstate(__ios_base::badbit); } 01520 } 01521 01522 if (__tmp.empty() && _Nb) 01523 __state |= __ios_base::failbit; 01524 else 01525 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb, 01526 __zero, __one); 01527 if (__state) 01528 __is.setstate(__state); 01529 return __is; 01530 } 01531 01532 template <class _CharT, class _Traits, size_t _Nb> 01533 std::basic_ostream<_CharT, _Traits>& 01534 operator<<(std::basic_ostream<_CharT, _Traits>& __os, 01535 const bitset<_Nb>& __x) 01536 { 01537 std::basic_string<_CharT, _Traits> __tmp; 01538 01539 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01540 // 396. what are characters zero and one. 01541 const ctype<_CharT>& __ct = use_facet<ctype<_CharT> >(__os.getloc()); 01542 __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1')); 01543 return __os << __tmp; 01544 } 01545 //@} 01546 01547 _GLIBCXX_END_NAMESPACE_CONTAINER 01548 } // namespace std 01549 01550 #undef _GLIBCXX_BITSET_WORDS 01551 #undef _GLIBCXX_BITSET_BITS_PER_WORD 01552 #undef _GLIBCXX_BITSET_BITS_PER_ULL 01553 01554 #if __cplusplus >= 201103L 01555 01556 namespace std _GLIBCXX_VISIBILITY(default) 01557 { 01558 _GLIBCXX_BEGIN_NAMESPACE_VERSION 01559 01560 // DR 1182. 01561 /// std::hash specialization for bitset. 01562 template<size_t _Nb> 01563 struct hash<_GLIBCXX_STD_C::bitset<_Nb>> 01564 : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<_Nb>> 01565 { 01566 size_t 01567 operator()(const _GLIBCXX_STD_C::bitset<_Nb>& __b) const noexcept 01568 { 01569 const size_t __clength = (_Nb + __CHAR_BIT__ - 1) / __CHAR_BIT__; 01570 return std::_Hash_impl::hash(__b._M_getdata(), __clength); 01571 } 01572 }; 01573 01574 template<> 01575 struct hash<_GLIBCXX_STD_C::bitset<0>> 01576 : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<0>> 01577 { 01578 size_t 01579 operator()(const _GLIBCXX_STD_C::bitset<0>&) const noexcept 01580 { return 0; } 01581 }; 01582 01583 _GLIBCXX_END_NAMESPACE_VERSION 01584 } // namespace 01585 01586 #endif // C++11 01587 01588 #ifdef _GLIBCXX_DEBUG 01589 # include <debug/bitset> 01590 #endif 01591 01592 #ifdef _GLIBCXX_PROFILE 01593 # include <profile/bitset> 01594 #endif 01595 01596 #endif /* _GLIBCXX_BITSET */