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