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