Where Online Learning is simpler!
The C and C++ Include Header Files
/usr/include/c++/13/bitset
$ cat -n /usr/include/c++/13/bitset 1 // <bitset> -*- C++ -*- 2 3 // Copyright (C) 2001-2023 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /* 26 * Copyright (c) 1998 27 * Silicon Graphics Computer Systems, Inc. 28 * 29 * Permission to use, copy, modify, distribute and sell this software 30 * and its documentation for any purpose is hereby granted without fee, 31 * provided that the above copyright notice appear in all copies and 32 * that both that copyright notice and this permission notice appear 33 * in supporting documentation. Silicon Graphics makes no 34 * representations about the suitability of this software for any 35 * purpose. It is provided "as is" without express or implied warranty. 36 */ 37 38 /** @file include/bitset 39 * This is a Standard C++ Library header. 40 */ 41 42 #ifndef _GLIBCXX_BITSET 43 #define _GLIBCXX_BITSET 1 44 45 #pragma GCC system_header 46 47 #include <bits/functexcept.h> // For invalid_argument, out_of_range, 48 // overflow_error 49 #include <bits/stl_algobase.h> // For std::fill 50 51 #if _GLIBCXX_HOSTED 52 # include <string> 53 # include <iosfwd> 54 # include <bits/cxxabi_forced.h> 55 #endif 56 57 #if __cplusplus >= 201103L 58 # include <bits/functional_hash.h> 59 #endif 60 61 #define _GLIBCXX_BITSET_BITS_PER_WORD (__CHAR_BIT__ * __SIZEOF_LONG__) 62 #define _GLIBCXX_BITSET_WORDS(__n) \ 63 ((__n) / _GLIBCXX_BITSET_BITS_PER_WORD + \ 64 ((__n) % _GLIBCXX_BITSET_BITS_PER_WORD == 0 ? 0 : 1)) 65 66 #define _GLIBCXX_BITSET_BITS_PER_ULL (__CHAR_BIT__ * __SIZEOF_LONG_LONG__) 67 68 namespace std _GLIBCXX_VISIBILITY(default) 69 { 70 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 71 72 #if __cplusplus > 202002L && _GLIBCXX_HOSTED 73 # define __cpp_lib_constexpr_bitset 202202L 74 #endif 75 76 /** 77 * Base class, general case. It is a class invariant that _Nw will be 78 * nonnegative. 79 * 80 * See documentation for bitset. 81 */ 82 template<size_t _Nw> 83 struct _Base_bitset 84 { 85 typedef unsigned long _WordT; 86 87 /// 0 is the least significant word. 88 _WordT _M_w[_Nw]; 89 90 _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT 91 : _M_w() { } 92 93 #if __cplusplus >= 201103L 94 constexpr _Base_bitset(unsigned long long __val) noexcept 95 : _M_w{ _WordT(__val) 96 #if __SIZEOF_LONG_LONG__ > __SIZEOF_LONG__ 97 , _WordT(__val >> _GLIBCXX_BITSET_BITS_PER_WORD) 98 #endif 99 } { } 100 #else 101 _Base_bitset(unsigned long __val) 102 : _M_w() 103 { _M_w[0] = __val; } 104 #endif 105 106 static _GLIBCXX_CONSTEXPR size_t 107 _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT 108 { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } 109 110 static _GLIBCXX_CONSTEXPR size_t 111 _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT 112 { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } 113 114 static _GLIBCXX_CONSTEXPR size_t 115 _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT 116 { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } 117 118 static _GLIBCXX_CONSTEXPR _WordT 119 _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT 120 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 121 122 _GLIBCXX14_CONSTEXPR _WordT& 123 _M_getword(size_t __pos) _GLIBCXX_NOEXCEPT 124 { return _M_w[_S_whichword(__pos)]; } 125 126 _GLIBCXX_CONSTEXPR _WordT 127 _M_getword(size_t __pos) const _GLIBCXX_NOEXCEPT 128 { return _M_w[_S_whichword(__pos)]; } 129 130 #if __cplusplus >= 201103L 131 constexpr const _WordT* 132 _M_getdata() const noexcept 133 { return _M_w; } 134 #endif 135 136 _GLIBCXX23_CONSTEXPR _WordT& 137 _M_hiword() _GLIBCXX_NOEXCEPT 138 { return _M_w[_Nw - 1]; } 139 140 _GLIBCXX_CONSTEXPR _WordT 141 _M_hiword() const _GLIBCXX_NOEXCEPT 142 { return _M_w[_Nw - 1]; } 143 144 _GLIBCXX23_CONSTEXPR void 145 _M_do_and(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT 146 { 147 for (size_t __i = 0; __i < _Nw; __i++) 148 _M_w[__i] &= __x._M_w[__i]; 149 } 150 151 _GLIBCXX14_CONSTEXPR void 152 _M_do_or(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT 153 { 154 for (size_t __i = 0; __i < _Nw; __i++) 155 _M_w[__i] |= __x._M_w[__i]; 156 } 157 158 _GLIBCXX14_CONSTEXPR void 159 _M_do_xor(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT 160 { 161 for (size_t __i = 0; __i < _Nw; __i++) 162 _M_w[__i] ^= __x._M_w[__i]; 163 } 164 165 _GLIBCXX14_CONSTEXPR void 166 _M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT; 167 168 _GLIBCXX14_CONSTEXPR void 169 _M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT; 170 171 _GLIBCXX14_CONSTEXPR void 172 _M_do_flip() _GLIBCXX_NOEXCEPT 173 { 174 for (size_t __i = 0; __i < _Nw; __i++) 175 _M_w[__i] = ~_M_w[__i]; 176 } 177 178 _GLIBCXX14_CONSTEXPR void 179 _M_do_set() _GLIBCXX_NOEXCEPT 180 { 181 for (size_t __i = 0; __i < _Nw; __i++) 182 _M_w[__i] = ~static_cast<_WordT>(0); 183 } 184 185 _GLIBCXX14_CONSTEXPR void 186 _M_do_reset() _GLIBCXX_NOEXCEPT 187 { 188 #if __cplusplus >= 201402L 189 if (__builtin_is_constant_evaluated()) 190 { 191 for (_WordT& __w : _M_w) 192 __w = 0; 193 return; 194 } 195 #endif 196 __builtin_memset(_M_w, 0, _Nw * sizeof(_WordT)); 197 } 198 199 _GLIBCXX14_CONSTEXPR bool 200 _M_is_equal(const _Base_bitset<_Nw>& __x) const _GLIBCXX_NOEXCEPT 201 { 202 for (size_t __i = 0; __i < _Nw; ++__i) 203 if (_M_w[__i] != __x._M_w[__i]) 204 return false; 205 return true; 206 } 207 208 template<size_t _Nb> 209 _GLIBCXX14_CONSTEXPR bool 210 _M_are_all() const _GLIBCXX_NOEXCEPT 211 { 212 for (size_t __i = 0; __i < _Nw - 1; __i++) 213 if (_M_w[__i] != ~static_cast<_WordT>(0)) 214 return false; 215 return _M_hiword() == (~static_cast<_WordT>(0) 216 >> (_Nw * _GLIBCXX_BITSET_BITS_PER_WORD 217 - _Nb)); 218 } 219 220 _GLIBCXX14_CONSTEXPR bool 221 _M_is_any() const _GLIBCXX_NOEXCEPT 222 { 223 for (size_t __i = 0; __i < _Nw; __i++) 224 if (_M_w[__i] != static_cast<_WordT>(0)) 225 return true; 226 return false; 227 } 228 229 _GLIBCXX14_CONSTEXPR size_t 230 _M_do_count() const _GLIBCXX_NOEXCEPT 231 { 232 size_t __result = 0; 233 for (size_t __i = 0; __i < _Nw; __i++) 234 __result += __builtin_popcountl(_M_w[__i]); 235 return __result; 236 } 237 238 _GLIBCXX14_CONSTEXPR unsigned long 239 _M_do_to_ulong() const; 240 241 #if __cplusplus >= 201103L 242 _GLIBCXX14_CONSTEXPR unsigned long long 243 _M_do_to_ullong() const; 244 #endif 245 246 // find first "on" bit 247 _GLIBCXX14_CONSTEXPR size_t 248 _M_do_find_first(size_t) const _GLIBCXX_NOEXCEPT; 249 250 // find the next "on" bit that follows "prev" 251 _GLIBCXX14_CONSTEXPR size_t 252 _M_do_find_next(size_t, size_t) const _GLIBCXX_NOEXCEPT; 253 }; 254 255 // Definitions of non-inline functions from _Base_bitset. 256 template<size_t _Nw> 257 _GLIBCXX14_CONSTEXPR void 258 _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT 259 { 260 if (__builtin_expect(__shift != 0, 1)) 261 { 262 const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD; 263 const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD; 264 265 if (__offset == 0) 266 for (size_t __n = _Nw - 1; __n >= __wshift; --__n) 267 _M_w[__n] = _M_w[__n - __wshift]; 268 else 269 { 270 const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD 271 - __offset); 272 for (size_t __n = _Nw - 1; __n > __wshift; --__n) 273 _M_w[__n] = ((_M_w[__n - __wshift] << __offset) 274 | (_M_w[__n - __wshift - 1] >> __sub_offset)); 275 _M_w[__wshift] = _M_w[0] << __offset; 276 } 277 278 std::fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0)); 279 } 280 } 281 282 template<size_t _Nw> 283 _GLIBCXX14_CONSTEXPR void 284 _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT 285 { 286 if (__builtin_expect(__shift != 0, 1)) 287 { 288 const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD; 289 const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD; 290 const size_t __limit = _Nw - __wshift - 1; 291 292 if (__offset == 0) 293 for (size_t __n = 0; __n <= __limit; ++__n) 294 _M_w[__n] = _M_w[__n + __wshift]; 295 else 296 { 297 const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD 298 - __offset); 299 for (size_t __n = 0; __n < __limit; ++__n) 300 _M_w[__n] = ((_M_w[__n + __wshift] >> __offset) 301 | (_M_w[__n + __wshift + 1] << __sub_offset)); 302 _M_w[__limit] = _M_w[_Nw-1] >> __offset; 303 } 304 305 std::fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0)); 306 } 307 } 308 309 template<size_t _Nw> 310 _GLIBCXX14_CONSTEXPR unsigned long 311 _Base_bitset<_Nw>::_M_do_to_ulong() const 312 { 313 for (size_t __i = 1; __i < _Nw; ++__i) 314 if (_M_w[__i]) 315 __throw_overflow_error(__N("_Base_bitset::_M_do_to_ulong")); 316 return _M_w[0]; 317 } 318 319 #if __cplusplus >= 201103L 320 template<size_t _Nw> 321 _GLIBCXX14_CONSTEXPR unsigned long long 322 _Base_bitset<_Nw>::_M_do_to_ullong() const 323 { 324 const bool __dw = sizeof(unsigned long long) > sizeof(unsigned long); 325 for (size_t __i = 1 + __dw; __i < _Nw; ++__i) 326 if (_M_w[__i]) 327 __throw_overflow_error(__N("_Base_bitset::_M_do_to_ullong")); 328 329 if (__dw) 330 return _M_w[0] + (static_cast<unsigned long long>(_M_w[1]) 331 << _GLIBCXX_BITSET_BITS_PER_WORD); 332 return _M_w[0]; 333 } 334 #endif 335 336 template<size_t _Nw> 337 _GLIBCXX14_CONSTEXPR size_t 338 _Base_bitset<_Nw>:: 339 _M_do_find_first(size_t __not_found) const _GLIBCXX_NOEXCEPT 340 { 341 for (size_t __i = 0; __i < _Nw; __i++) 342 { 343 _WordT __thisword = _M_w[__i]; 344 if (__thisword != static_cast<_WordT>(0)) 345 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD 346 + __builtin_ctzl(__thisword)); 347 } 348 // not found, so return an indication of failure. 349 return __not_found; 350 } 351 352 template<size_t _Nw> 353 _GLIBCXX14_CONSTEXPR size_t 354 _Base_bitset<_Nw>:: 355 _M_do_find_next(size_t __prev, size_t __not_found) const _GLIBCXX_NOEXCEPT 356 { 357 // make bound inclusive 358 ++__prev; 359 360 // check out of bounds 361 if (__prev >= _Nw * _GLIBCXX_BITSET_BITS_PER_WORD) 362 return __not_found; 363 364 // search first word 365 size_t __i = _S_whichword(__prev); 366 _WordT __thisword = _M_w[__i]; 367 368 // mask off bits below bound 369 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev); 370 371 if (__thisword != static_cast<_WordT>(0)) 372 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD 373 + __builtin_ctzl(__thisword)); 374 375 // check subsequent words 376 __i++; 377 for (; __i < _Nw; __i++) 378 { 379 __thisword = _M_w[__i]; 380 if (__thisword != static_cast<_WordT>(0)) 381 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD 382 + __builtin_ctzl(__thisword)); 383 } 384 // not found, so return an indication of failure. 385 return __not_found; 386 } // end _M_do_find_next 387 388 /** 389 * Base class, specialization for a single word. 390 * 391 * See documentation for bitset. 392 */ 393 template<> 394 struct _Base_bitset<1> 395 { 396 typedef unsigned long _WordT; 397 _WordT _M_w; 398 399 _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT 400 : _M_w(0) 401 { } 402 403 #if __cplusplus >= 201103L 404 constexpr _Base_bitset(unsigned long long __val) noexcept 405 #else 406 _Base_bitset(unsigned long __val) 407 #endif 408 : _M_w(__val) 409 { } 410 411 static _GLIBCXX_CONSTEXPR size_t 412 _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT 413 { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } 414 415 static _GLIBCXX_CONSTEXPR size_t 416 _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT 417 { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } 418 419 static _GLIBCXX_CONSTEXPR size_t 420 _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT 421 { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } 422 423 static _GLIBCXX_CONSTEXPR _WordT 424 _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT 425 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 426 427 _GLIBCXX14_CONSTEXPR _WordT& 428 _M_getword(size_t) _GLIBCXX_NOEXCEPT 429 { return _M_w; } 430 431 _GLIBCXX_CONSTEXPR _WordT 432 _M_getword(size_t) const _GLIBCXX_NOEXCEPT 433 { return _M_w; } 434 435 #if __cplusplus >= 201103L 436 constexpr const _WordT* 437 _M_getdata() const noexcept 438 { return &_M_w; } 439 #endif 440 441 _GLIBCXX14_CONSTEXPR _WordT& 442 _M_hiword() _GLIBCXX_NOEXCEPT 443 { return _M_w; } 444 445 _GLIBCXX_CONSTEXPR _WordT 446 _M_hiword() const _GLIBCXX_NOEXCEPT 447 { return _M_w; } 448 449 _GLIBCXX14_CONSTEXPR void 450 _M_do_and(const _Base_bitset<1>& __x) _GLIBCXX_NOEXCEPT 451 { _M_w &= __x._M_w; } 452 453 _GLIBCXX14_CONSTEXPR void 454 _M_do_or(const _Base_bitset<1>& __x) _GLIBCXX_NOEXCEPT 455 { _M_w |= __x._M_w; } 456 457 _GLIBCXX14_CONSTEXPR void 458 _M_do_xor(const _Base_bitset<1>& __x) _GLIBCXX_NOEXCEPT 459 { _M_w ^= __x._M_w; } 460 461 _GLIBCXX14_CONSTEXPR void 462 _M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT 463 { _M_w <<= __shift; } 464 465 _GLIBCXX14_CONSTEXPR void 466 _M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT 467 { _M_w >>= __shift; } 468 469 _GLIBCXX14_CONSTEXPR void 470 _M_do_flip() _GLIBCXX_NOEXCEPT 471 { _M_w = ~_M_w; } 472 473 _GLIBCXX14_CONSTEXPR void 474 _M_do_set() _GLIBCXX_NOEXCEPT 475 { _M_w = ~static_cast<_WordT>(0); } 476 477 _GLIBCXX14_CONSTEXPR void 478 _M_do_reset() _GLIBCXX_NOEXCEPT 479 { _M_w = 0; } 480 481 _GLIBCXX14_CONSTEXPR bool 482 _M_is_equal(const _Base_bitset<1>& __x) const _GLIBCXX_NOEXCEPT 483 { return _M_w == __x._M_w; } 484 485 template<size_t _Nb> 486 _GLIBCXX14_CONSTEXPR bool 487 _M_are_all() const _GLIBCXX_NOEXCEPT 488 { return _M_w == (~static_cast<_WordT>(0) 489 >> (_GLIBCXX_BITSET_BITS_PER_WORD - _Nb)); } 490 491 _GLIBCXX14_CONSTEXPR bool 492 _M_is_any() const _GLIBCXX_NOEXCEPT 493 { return _M_w != 0; } 494 495 _GLIBCXX14_CONSTEXPR size_t 496 _M_do_count() const _GLIBCXX_NOEXCEPT 497 { return __builtin_popcountl(_M_w); } 498 499 _GLIBCXX14_CONSTEXPR unsigned long 500 _M_do_to_ulong() const _GLIBCXX_NOEXCEPT 501 { return _M_w; } 502 503 #if __cplusplus >= 201103L 504 constexpr unsigned long long 505 _M_do_to_ullong() const noexcept 506 { return _M_w; } 507 #endif 508 509 _GLIBCXX14_CONSTEXPR size_t 510 _M_do_find_first(size_t __not_found) const _GLIBCXX_NOEXCEPT 511 { 512 if (_M_w != 0) 513 return __builtin_ctzl(_M_w); 514 else 515 return __not_found; 516 } 517 518 // find the next "on" bit that follows "prev" 519 _GLIBCXX14_CONSTEXPR size_t 520 _M_do_find_next(size_t __prev, size_t __not_found) const 521 _GLIBCXX_NOEXCEPT 522 { 523 ++__prev; 524 if (__prev >= ((size_t) _GLIBCXX_BITSET_BITS_PER_WORD)) 525 return __not_found; 526 527 _WordT __x = _M_w >> __prev; 528 if (__x != 0) 529 return __builtin_ctzl(__x) + __prev; 530 else 531 return __not_found; 532 } 533 }; 534 535 /** 536 * Base class, specialization for no storage (zero-length %bitset). 537 * 538 * See documentation for bitset. 539 */ 540 template<> 541 struct _Base_bitset<0> 542 { 543 typedef unsigned long _WordT; 544 545 _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT 546 { } 547 548 #if __cplusplus >= 201103L 549 constexpr _Base_bitset(unsigned long long) noexcept 550 #else 551 _Base_bitset(unsigned long) 552 #endif 553 { } 554 555 static _GLIBCXX_CONSTEXPR size_t 556 _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT 557 { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } 558 559 static _GLIBCXX_CONSTEXPR size_t 560 _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT 561 { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } 562 563 static _GLIBCXX_CONSTEXPR size_t 564 _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT 565 { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } 566 567 static _GLIBCXX_CONSTEXPR _WordT 568 _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT 569 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 570 571 // This would normally give access to the data. The bounds-checking 572 // in the bitset class will prevent the user from getting this far, 573 // but this must fail if the user calls _Unchecked_set directly. 574 // Let's not penalize zero-length users unless they actually 575 // make an unchecked call; all the memory ugliness is therefore 576 // localized to this single should-never-get-this-far function. 577 __attribute__((__noreturn__)) 578 _WordT& 579 _M_getword(size_t) _GLIBCXX_NOEXCEPT 580 { __throw_out_of_range(__N("_Base_bitset::_M_getword")); } 581 582 _GLIBCXX_CONSTEXPR _WordT 583 _M_getword(size_t) const _GLIBCXX_NOEXCEPT 584 { return 0; } 585 586 _GLIBCXX_CONSTEXPR _WordT 587 _M_hiword() const _GLIBCXX_NOEXCEPT 588 { return 0; } 589 590 _GLIBCXX14_CONSTEXPR void 591 _M_do_and(const _Base_bitset<0>&) _GLIBCXX_NOEXCEPT 592 { } 593 594 _GLIBCXX14_CONSTEXPR void 595 _M_do_or(const _Base_bitset<0>&) _GLIBCXX_NOEXCEPT 596 { } 597 598 _GLIBCXX14_CONSTEXPR void 599 _M_do_xor(const _Base_bitset<0>&) _GLIBCXX_NOEXCEPT 600 { } 601 602 _GLIBCXX14_CONSTEXPR void 603 _M_do_left_shift(size_t) _GLIBCXX_NOEXCEPT 604 { } 605 606 _GLIBCXX14_CONSTEXPR void 607 _M_do_right_shift(size_t) _GLIBCXX_NOEXCEPT 608 { } 609 610 _GLIBCXX14_CONSTEXPR void 611 _M_do_flip() _GLIBCXX_NOEXCEPT 612 { } 613 614 _GLIBCXX14_CONSTEXPR void 615 _M_do_set() _GLIBCXX_NOEXCEPT 616 { } 617 618 _GLIBCXX14_CONSTEXPR void 619 _M_do_reset() _GLIBCXX_NOEXCEPT 620 { } 621 622 // Are all empty bitsets equal to each other? Are they equal to 623 // themselves? How to compare a thing which has no state? What is 624 // the sound of one zero-length bitset clapping? 625 _GLIBCXX_CONSTEXPR bool 626 _M_is_equal(const _Base_bitset<0>&) const _GLIBCXX_NOEXCEPT 627 { return true; } 628 629 template<size_t _Nb> 630 _GLIBCXX_CONSTEXPR bool 631 _M_are_all() const _GLIBCXX_NOEXCEPT 632 { return true; } 633 634 _GLIBCXX_CONSTEXPR bool 635 _M_is_any() const _GLIBCXX_NOEXCEPT 636 { return false; } 637 638 _GLIBCXX_CONSTEXPR size_t 639 _M_do_count() const _GLIBCXX_NOEXCEPT 640 { return 0; } 641 642 _GLIBCXX_CONSTEXPR unsigned long 643 _M_do_to_ulong() const _GLIBCXX_NOEXCEPT 644 { return 0; } 645 646 #if __cplusplus >= 201103L 647 constexpr unsigned long long 648 _M_do_to_ullong() const noexcept 649 { return 0; } 650 #endif 651 652 // Normally "not found" is the size, but that could also be 653 // misinterpreted as an index in this corner case. Oh well. 654 _GLIBCXX_CONSTEXPR size_t 655 _M_do_find_first(size_t) const _GLIBCXX_NOEXCEPT 656 { return 0; } 657 658 _GLIBCXX_CONSTEXPR size_t 659 _M_do_find_next(size_t, size_t) const _GLIBCXX_NOEXCEPT 660 { return 0; } 661 }; 662 663 664 // Helper class to zero out the unused high-order bits in the highest word. 665 template<size_t _Extrabits> 666 struct _Sanitize 667 { 668 typedef unsigned long _WordT; 669 670 static _GLIBCXX14_CONSTEXPR void 671 _S_do_sanitize(_WordT& __val) _GLIBCXX_NOEXCEPT 672 { __val &= ~((~static_cast<_WordT>(0)) << _Extrabits); } 673 }; 674 675 template<> 676 struct _Sanitize<0> 677 { 678 typedef unsigned long _WordT; 679 680 static _GLIBCXX14_CONSTEXPR void 681 _S_do_sanitize(_WordT) _GLIBCXX_NOEXCEPT { } 682 }; 683 684 #if __cplusplus >= 201103L 685 template<size_t _Nb, bool = (_Nb < _GLIBCXX_BITSET_BITS_PER_ULL)> 686 struct _Sanitize_val 687 { 688 static constexpr unsigned long long 689 _S_do_sanitize_val(unsigned long long __val) 690 { return __val; } 691 }; 692 693 template<size_t _Nb> 694 struct _Sanitize_val<_Nb, true> 695 { 696 static constexpr unsigned long long 697 _S_do_sanitize_val(unsigned long long __val) 698 { return __val & ~((~static_cast<unsigned long long>(0)) << _Nb); } 699 }; 700 701 namespace __bitset 702 { 703 #if _GLIBCXX_HOSTED 704 template<typename _CharT> 705 using __string = std::basic_string<_CharT>; 706 #else 707 template<typename _CharT> 708 struct __string 709 { 710 using size_type = size_t; 711 static constexpr size_type npos = size_type(-1); 712 713 struct traits_type 714 { 715 static _GLIBCXX14_CONSTEXPR size_t 716 length(const _CharT* __s) noexcept 717 { 718 size_t __n = 0; 719 while (__s[__n]) 720 __n++; 721 return __n; 722 } 723 724 static constexpr bool 725 eq(_CharT __l, _CharT __r) noexcept 726 { return __l == __r; } 727 }; 728 }; 729 #endif // HOSTED 730 } // namespace __bitset 731 #endif // C++11 732 733 /** 734 * @brief The %bitset class represents a @e fixed-size sequence of bits. 735 * @ingroup utilities 736 * 737 * (Note that %bitset does @e not meet the formal requirements of a 738 * <a href="tables.html#65">container</a>. Mainly, it lacks iterators.) 739 * 740 * The template argument, @a Nb, may be any non-negative number, 741 * specifying the number of bits (e.g., "0", "12", "1024*1024"). 742 * 743 * In the general unoptimized case, storage is allocated in word-sized 744 * blocks. Let B be the number of bits in a word, then (Nb+(B-1))/B 745 * words will be used for storage. B - Nb%B bits are unused. (They are 746 * the high-order bits in the highest word.) It is a class invariant 747 * that those unused bits are always zero. 748 * 749 * If you think of %bitset as <em>a simple array of bits</em>, be 750 * aware that your mental picture is reversed: a %bitset behaves 751 * the same way as bits in integers do, with the bit at index 0 in 752 * the <em>least significant / right-hand</em> position, and the bit at 753 * index Nb-1 in the <em>most significant / left-hand</em> position. 754 * Thus, unlike other containers, a %bitset's index <em>counts from 755 * right to left</em>, to put it very loosely. 756 * 757 * This behavior is preserved when translating to and from strings. For 758 * example, the first line of the following program probably prints 759 * <em>b('a') is 0001100001</em> on a modern ASCII system. 760 * 761 * @code 762 * #include <bitset> 763 * #include <iostream> 764 * #include <sstream> 765 * 766 * using namespace std; 767 * 768 * int main() 769 * { 770 * long a = 'a'; 771 * bitset<10> b(a); 772 * 773 * cout << "b('a') is " << b << endl; 774 * 775 * ostringstream s; 776 * s << b; 777 * string str = s.str(); 778 * cout << "index 3 in the string is " << str[3] << " but\n" 779 * << "index 3 in the bitset is " << b[3] << endl; 780 * } 781 * @endcode 782 * 783 * Also see: 784 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/ext_containers.html 785 * for a description of extensions. 786 * 787 * Most of the actual code isn't contained in %bitset<> itself, but in the 788 * base class _Base_bitset. The base class works with whole words, not with 789 * individual bits. This allows us to specialize _Base_bitset for the 790 * important special case where the %bitset is only a single word. 791 * 792 * Extra confusion can result due to the fact that the storage for 793 * _Base_bitset @e is a regular array, and is indexed as such. This is 794 * carefully encapsulated. 795 */ 796 template<size_t _Nb> 797 class bitset 798 : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> 799 { 800 private: 801 typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base; 802 typedef unsigned long _WordT; 803 804 #if _GLIBCXX_HOSTED 805 template<class _CharT, class _Traits, class _Alloc> 806 _GLIBCXX23_CONSTEXPR 807 void 808 _M_check_initial_position(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 809 size_t __position) const 810 { 811 if (__position > __s.size()) 812 __throw_out_of_range_fmt(__N("bitset::bitset: __position " 813 "(which is %zu) > __s.size() " 814 "(which is %zu)"), 815 __position, __s.size()); 816 } 817 #endif // HOSTED 818 819 _GLIBCXX23_CONSTEXPR 820 void _M_check(size_t __position, const char *__s) const 821 { 822 if (__position >= _Nb) 823 __throw_out_of_range_fmt(__N("%s: __position (which is %zu) " 824 ">= _Nb (which is %zu)"), 825 __s, __position, _Nb); 826 } 827 828 _GLIBCXX23_CONSTEXPR 829 void 830 _M_do_sanitize() _GLIBCXX_NOEXCEPT 831 { 832 typedef _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD> __sanitize_type; 833 __sanitize_type::_S_do_sanitize(this->_M_hiword()); 834 } 835 836 #if __cplusplus >= 201103L 837 friend struct std::hash<bitset>; 838 #endif 839 840 public: 841 /** 842 * This encapsulates the concept of a single bit. An instance of this 843 * class is a proxy for an actual bit; this way the individual bit 844 * operations are done as faster word-size bitwise instructions. 845 * 846 * Most users will never need to use this class directly; conversions 847 * to and from bool are automatic and should be transparent. Overloaded 848 * operators help to preserve the illusion. 849 * 850 * (On a typical system, this <em>bit %reference</em> is 64 851 * times the size of an actual bit. Ha.) 852 */ 853 class reference 854 { 855 friend class bitset; 856 857 _WordT* _M_wp; 858 size_t _M_bpos; 859 860 // left undefined 861 reference(); 862 863 public: 864 _GLIBCXX23_CONSTEXPR 865 reference(bitset& __b, size_t __pos) _GLIBCXX_NOEXCEPT 866 { 867 _M_wp = &__b._M_getword(__pos); 868 _M_bpos = _Base::_S_whichbit(__pos); 869 } 870 871 #if __cplusplus >= 201103L 872 reference(const reference&) = default; 873 #endif 874 875 #if __cplusplus > 202002L && __cpp_constexpr_dynamic_alloc 876 constexpr 877 #endif 878 ~reference() _GLIBCXX_NOEXCEPT 879 { } 880 881 // For b[i] = __x; 882 _GLIBCXX23_CONSTEXPR 883 reference& 884 operator=(bool __x) _GLIBCXX_NOEXCEPT 885 { 886 if (__x) 887 *_M_wp |= _Base::_S_maskbit(_M_bpos); 888 else 889 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 890 return *this; 891 } 892 893 // For b[i] = b[__j]; 894 _GLIBCXX23_CONSTEXPR 895 reference& 896 operator=(const reference& __j) _GLIBCXX_NOEXCEPT 897 { 898 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos))) 899 *_M_wp |= _Base::_S_maskbit(_M_bpos); 900 else 901 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 902 return *this; 903 } 904 905 // Flips the bit 906 _GLIBCXX23_CONSTEXPR 907 bool 908 operator~() const _GLIBCXX_NOEXCEPT 909 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; } 910 911 // For __x = b[i]; 912 _GLIBCXX23_CONSTEXPR 913 operator bool() const _GLIBCXX_NOEXCEPT 914 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; } 915 916 // For b[i].flip(); 917 _GLIBCXX23_CONSTEXPR 918 reference& 919 flip() _GLIBCXX_NOEXCEPT 920 { 921 *_M_wp ^= _Base::_S_maskbit(_M_bpos); 922 return *this; 923 } 924 }; 925 friend class reference; 926 927 // 23.3.5.1 constructors: 928 /// All bits set to zero. 929 _GLIBCXX_CONSTEXPR bitset() _GLIBCXX_NOEXCEPT 930 { } 931 932 /// Initial bits bitwise-copied from a single word (others set to zero). 933 #if __cplusplus >= 201103L 934 constexpr bitset(unsigned long long __val) noexcept 935 : _Base(_Sanitize_val<_Nb>::_S_do_sanitize_val(__val)) { } 936 #else 937 bitset(unsigned long __val) 938 : _Base(__val) 939 { _M_do_sanitize(); } 940 #endif 941 942 #if _GLIBCXX_HOSTED 943 /** 944 * Use a subset of a string. 945 * @param __s A string of @a 0 and @a 1 characters. 946 * @param __position Index of the first character in @a __s to use; 947 * defaults to zero. 948 * @throw std::out_of_range If @a pos is bigger the size of @a __s. 949 * @throw std::invalid_argument If a character appears in the string 950 * which is neither @a 0 nor @a 1. 951 */ 952 template<class _CharT, class _Traits, class _Alloc> 953 _GLIBCXX23_CONSTEXPR 954 explicit 955 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 956 size_t __position = 0) 957 : _Base() 958 { 959 _M_check_initial_position(__s, __position); 960 _M_copy_from_string(__s, __position, 961 std::basic_string<_CharT, _Traits, _Alloc>::npos, 962 _CharT('0'), _CharT('1')); 963 } 964 965 /** 966 * Use a subset of a string. 967 * @param __s A string of @a 0 and @a 1 characters. 968 * @param __position Index of the first character in @a __s to use. 969 * @param __n The number of characters to copy. 970 * @throw std::out_of_range If @a __position is bigger the size 971 * of @a __s. 972 * @throw std::invalid_argument If a character appears in the string 973 * which is neither @a 0 nor @a 1. 974 */ 975 template<class _CharT, class _Traits, class _Alloc> 976 _GLIBCXX23_CONSTEXPR 977 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 978 size_t __position, size_t __n) 979 : _Base() 980 { 981 _M_check_initial_position(__s, __position); 982 _M_copy_from_string(__s, __position, __n, _CharT('0'), _CharT('1')); 983 } 984 985 // _GLIBCXX_RESOLVE_LIB_DEFECTS 986 // 396. what are characters zero and one. 987 template<class _CharT, class _Traits, class _Alloc> 988 _GLIBCXX23_CONSTEXPR 989 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 990 size_t __position, size_t __n, 991 _CharT __zero, _CharT __one = _CharT('1')) 992 : _Base() 993 { 994 _M_check_initial_position(__s, __position); 995 _M_copy_from_string(__s, __position, __n, __zero, __one); 996 } 997 #endif // HOSTED 998 999 #if __cplusplus >= 201103L 1000 /** 1001 * Construct from a character %array. 1002 * @param __str An %array of characters @a zero and @a one. 1003 * @param __n The number of characters to use. 1004 * @param __zero The character corresponding to the value 0. 1005 * @param __one The character corresponding to the value 1. 1006 * @throw std::invalid_argument If a character appears in the string 1007 * which is neither @a __zero nor @a __one. 1008 */ 1009 template<typename _CharT> 1010 [[__gnu__::__nonnull__]] 1011 _GLIBCXX23_CONSTEXPR 1012 explicit 1013 bitset(const _CharT* __str, 1014 typename __bitset::__string<_CharT>::size_type __n 1015 = __bitset::__string<_CharT>::npos, 1016 _CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) 1017 : _Base() 1018 { 1019 #if _GLIBCXX_HOSTED 1020 if (!__str) 1021 __throw_logic_error(__N("bitset::bitset(const _CharT*, ...)")); 1022 #endif 1023 using _Traits = typename __bitset::__string<_CharT>::traits_type; 1024 1025 if (__n == __bitset::__string<_CharT>::npos) 1026 __n = _Traits::length(__str); 1027 _M_copy_from_ptr<_CharT, _Traits>(__str, __n, 0, __n, __zero, __one); 1028 } 1029 #endif // C++11 1030 1031 // 23.3.5.2 bitset operations: 1032 ///@{ 1033 /** 1034 * Operations on bitsets. 1035 * @param __rhs A same-sized bitset. 1036 * 1037 * These should be self-explanatory. 1038 */ 1039 _GLIBCXX23_CONSTEXPR 1040 bitset<_Nb>& 1041 operator&=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT 1042 { 1043 this->_M_do_and(__rhs); 1044 return *this; 1045 } 1046 1047 _GLIBCXX23_CONSTEXPR 1048 bitset<_Nb>& 1049 operator|=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT 1050 { 1051 this->_M_do_or(__rhs); 1052 return *this; 1053 } 1054 1055 _GLIBCXX23_CONSTEXPR 1056 bitset<_Nb>& 1057 operator^=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT 1058 { 1059 this->_M_do_xor(__rhs); 1060 return *this; 1061 } 1062 ///@} 1063 1064 ///@{ 1065 /** 1066 * Operations on bitsets. 1067 * @param __position The number of places to shift. 1068 * 1069 * These should be self-explanatory. 1070 */ 1071 _GLIBCXX23_CONSTEXPR 1072 bitset<_Nb>& 1073 operator<<=(size_t __position) _GLIBCXX_NOEXCEPT 1074 { 1075 if (__builtin_expect(__position < _Nb, 1)) 1076 { 1077 this->_M_do_left_shift(__position); 1078 this->_M_do_sanitize(); 1079 } 1080 else 1081 this->_M_do_reset(); 1082 return *this; 1083 } 1084 1085 _GLIBCXX23_CONSTEXPR 1086 bitset<_Nb>& 1087 operator>>=(size_t __position) _GLIBCXX_NOEXCEPT 1088 { 1089 if (__builtin_expect(__position < _Nb, 1)) 1090 { 1091 this->_M_do_right_shift(__position); 1092 this->_M_do_sanitize(); 1093 } 1094 else 1095 this->_M_do_reset(); 1096 return *this; 1097 } 1098 ///@} 1099 1100 ///@{ 1101 /** 1102 * These versions of single-bit set, reset, flip, and test are 1103 * extensions from the SGI version. They do no range checking. 1104 * @ingroup SGIextensions 1105 */ 1106 _GLIBCXX23_CONSTEXPR 1107 bitset<_Nb>& 1108 _Unchecked_set(size_t __pos) _GLIBCXX_NOEXCEPT 1109 { 1110 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 1111 return *this; 1112 } 1113 1114 _GLIBCXX23_CONSTEXPR 1115 bitset<_Nb>& 1116 _Unchecked_set(size_t __pos, int __val) _GLIBCXX_NOEXCEPT 1117 { 1118 if (__val) 1119 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 1120 else 1121 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 1122 return *this; 1123 } 1124 1125 _GLIBCXX23_CONSTEXPR 1126 bitset<_Nb>& 1127 _Unchecked_reset(size_t __pos) _GLIBCXX_NOEXCEPT 1128 { 1129 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 1130 return *this; 1131 } 1132 1133 _GLIBCXX23_CONSTEXPR 1134 bitset<_Nb>& 1135 _Unchecked_flip(size_t __pos) _GLIBCXX_NOEXCEPT 1136 { 1137 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); 1138 return *this; 1139 } 1140 1141 _GLIBCXX_CONSTEXPR bool 1142 _Unchecked_test(size_t __pos) const _GLIBCXX_NOEXCEPT 1143 { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) 1144 != static_cast<_WordT>(0)); } 1145 ///@} 1146 1147 // Set, reset, and flip. 1148 /** 1149 * @brief Sets every bit to true. 1150 */ 1151 _GLIBCXX23_CONSTEXPR 1152 bitset<_Nb>& 1153 set() _GLIBCXX_NOEXCEPT 1154 { 1155 this->_M_do_set(); 1156 this->_M_do_sanitize(); 1157 return *this; 1158 } 1159 1160 /** 1161 * @brief Sets a given bit to a particular value. 1162 * @param __position The index of the bit. 1163 * @param __val Either true or false, defaults to true. 1164 * @throw std::out_of_range If @a pos is bigger the size of the %set. 1165 */ 1166 _GLIBCXX23_CONSTEXPR 1167 bitset<_Nb>& 1168 set(size_t __position, bool __val = true) 1169 { 1170 this->_M_check(__position, __N("bitset::set")); 1171 return _Unchecked_set(__position, __val); 1172 } 1173 1174 /** 1175 * @brief Sets every bit to false. 1176 */ 1177 _GLIBCXX23_CONSTEXPR 1178 bitset<_Nb>& 1179 reset() _GLIBCXX_NOEXCEPT 1180 { 1181 this->_M_do_reset(); 1182 return *this; 1183 } 1184 1185 /** 1186 * @brief Sets a given bit to false. 1187 * @param __position The index of the bit. 1188 * @throw std::out_of_range If @a pos is bigger the size of the %set. 1189 * 1190 * Same as writing @c set(pos,false). 1191 */ 1192 _GLIBCXX23_CONSTEXPR 1193 bitset<_Nb>& 1194 reset(size_t __position) 1195 { 1196 this->_M_check(__position, __N("bitset::reset")); 1197 return _Unchecked_reset(__position); 1198 } 1199 1200 /** 1201 * @brief Toggles every bit to its opposite value. 1202 */ 1203 _GLIBCXX23_CONSTEXPR 1204 bitset<_Nb>& 1205 flip() _GLIBCXX_NOEXCEPT 1206 { 1207 this->_M_do_flip(); 1208 this->_M_do_sanitize(); 1209 return *this; 1210 } 1211 1212 /** 1213 * @brief Toggles a given bit to its opposite value. 1214 * @param __position The index of the bit. 1215 * @throw std::out_of_range If @a pos is bigger the size of the %set. 1216 */ 1217 _GLIBCXX23_CONSTEXPR 1218 bitset<_Nb>& 1219 flip(size_t __position) 1220 { 1221 this->_M_check(__position, __N("bitset::flip")); 1222 return _Unchecked_flip(__position); 1223 } 1224 1225 /// See the no-argument flip(). 1226 _GLIBCXX23_CONSTEXPR 1227 bitset<_Nb> 1228 operator~() const _GLIBCXX_NOEXCEPT 1229 { return bitset<_Nb>(*this).flip(); } 1230 1231 ///@{ 1232 /** 1233 * @brief Array-indexing support. 1234 * @param __position Index into the %bitset. 1235 * @return A bool for a <em>const %bitset</em>. For non-const 1236 * bitsets, an instance of the reference proxy class. 1237 * @note These operators do no range checking and throw no exceptions, 1238 * as required by DR 11 to the standard. 1239 * 1240 * _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already 1241 * resolves DR 11 (items 1 and 2), but does not do the range-checking 1242 * required by that DR's resolution. -pme 1243 * The DR has since been changed: range-checking is a precondition 1244 * (users' responsibility), and these functions must not throw. -pme 1245 */ 1246 _GLIBCXX23_CONSTEXPR 1247 reference 1248 operator[](size_t __position) 1249 { return reference(*this, __position); } 1250 1251 _GLIBCXX_CONSTEXPR bool 1252 operator[](size_t __position) const 1253 { return _Unchecked_test(__position); } 1254 ///@} 1255 1256 /** 1257 * @brief Returns a numerical interpretation of the %bitset. 1258 * @return The integral equivalent of the bits. 1259 * @throw std::overflow_error If there are too many bits to be 1260 * represented in an @c unsigned @c long. 1261 */ 1262 _GLIBCXX23_CONSTEXPR 1263 unsigned long 1264 to_ulong() const 1265 { return this->_M_do_to_ulong(); } 1266 1267 #if __cplusplus >= 201103L 1268 _GLIBCXX23_CONSTEXPR 1269 unsigned long long 1270 to_ullong() const 1271 { return this->_M_do_to_ullong(); } 1272 #endif 1273 1274 #if _GLIBCXX_HOSTED 1275 /** 1276 * @brief Returns a character interpretation of the %bitset. 1277 * @return The string equivalent of the bits. 1278 * 1279 * Note the ordering of the bits: decreasing character positions 1280 * correspond to increasing bit positions (see the main class notes for 1281 * an example). 1282 */ 1283 template<class _CharT, class _Traits, class _Alloc> 1284 _GLIBCXX23_CONSTEXPR 1285 std::basic_string<_CharT, _Traits, _Alloc> 1286 to_string() const 1287 { 1288 std::basic_string<_CharT, _Traits, _Alloc> __result; 1289 _M_copy_to_string(__result, _CharT('0'), _CharT('1')); 1290 return __result; 1291 } 1292 1293 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1294 // 396. what are characters zero and one. 1295 template<class _CharT, class _Traits, class _Alloc> 1296 _GLIBCXX23_CONSTEXPR 1297 std::basic_string<_CharT, _Traits, _Alloc> 1298 to_string(_CharT __zero, _CharT __one = _CharT('1')) const 1299 { 1300 std::basic_string<_CharT, _Traits, _Alloc> __result; 1301 _M_copy_to_string(__result, __zero, __one); 1302 return __result; 1303 } 1304 1305 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1306 // 434. bitset::to_string() hard to use. 1307 template<class _CharT, class _Traits> 1308 _GLIBCXX23_CONSTEXPR 1309 std::basic_string<_CharT, _Traits, std::allocator<_CharT> > 1310 to_string() const 1311 { return to_string<_CharT, _Traits, std::allocator<_CharT> >(); } 1312 1313 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1314 // 853. to_string needs updating with zero and one. 1315 template<class _CharT, class _Traits> 1316 _GLIBCXX23_CONSTEXPR 1317 std::basic_string<_CharT, _Traits, std::allocator<_CharT> > 1318 to_string(_CharT __zero, _CharT __one = _CharT('1')) const 1319 { return to_string<_CharT, _Traits, 1320 std::allocator<_CharT> >(__zero, __one); } 1321 1322 template<class _CharT> 1323 _GLIBCXX23_CONSTEXPR 1324 std::basic_string<_CharT, std::char_traits<_CharT>, 1325 std::allocator<_CharT> > 1326 to_string() const 1327 { 1328 return to_string<_CharT, std::char_traits<_CharT>, 1329 std::allocator<_CharT> >(); 1330 } 1331 1332 template<class _CharT> 1333 _GLIBCXX23_CONSTEXPR 1334 std::basic_string<_CharT, std::char_traits<_CharT>, 1335 std::allocator<_CharT> > 1336 to_string(_CharT __zero, _CharT __one = _CharT('1')) const 1337 { 1338 return to_string<_CharT, std::char_traits<_CharT>, 1339 std::allocator<_CharT> >(__zero, __one); 1340 } 1341 1342 _GLIBCXX23_CONSTEXPR 1343 std::basic_string<char, std::char_traits<char>, std::allocator<char> > 1344 to_string() const 1345 { 1346 return to_string<char, std::char_traits<char>, 1347 std::allocator<char> >(); 1348 } 1349 1350 _GLIBCXX23_CONSTEXPR 1351 std::basic_string<char, std::char_traits<char>, std::allocator<char> > 1352 to_string(char __zero, char __one = '1') const 1353 { 1354 return to_string<char, std::char_traits<char>, 1355 std::allocator<char> >(__zero, __one); 1356 } 1357 #endif // HOSTED 1358 1359 /// Returns the number of bits which are set. 1360 _GLIBCXX23_CONSTEXPR 1361 size_t 1362 count() const _GLIBCXX_NOEXCEPT 1363 { return this->_M_do_count(); } 1364 1365 /// Returns the total number of bits. 1366 _GLIBCXX_CONSTEXPR size_t 1367 size() const _GLIBCXX_NOEXCEPT 1368 { return _Nb; } 1369 1370 ///@{ 1371 /// These comparisons for equality/inequality are, well, @e bitwise. 1372 _GLIBCXX23_CONSTEXPR 1373 bool 1374 operator==(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT 1375 { return this->_M_is_equal(__rhs); } 1376 1377 #if __cpp_impl_three_way_comparison < 201907L 1378 _GLIBCXX23_CONSTEXPR 1379 bool 1380 operator!=(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT 1381 { return !this->_M_is_equal(__rhs); } 1382 #endif 1383 ///@} 1384 1385 /** 1386 * @brief Tests the value of a bit. 1387 * @param __position The index of a bit. 1388 * @return The value at @a pos. 1389 * @throw std::out_of_range If @a pos is bigger the size of the %set. 1390 */ 1391 _GLIBCXX23_CONSTEXPR 1392 bool 1393 test(size_t __position) const 1394 { 1395 this->_M_check(__position, __N("bitset::test")); 1396 return _Unchecked_test(__position); 1397 } 1398 1399 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1400 // DR 693. std::bitset::all() missing. 1401 /** 1402 * @brief Tests whether all the bits are on. 1403 * @return True if all the bits are set. 1404 */ 1405 _GLIBCXX23_CONSTEXPR 1406 bool 1407 all() const _GLIBCXX_NOEXCEPT 1408 { return this->template _M_are_all<_Nb>(); } 1409 1410 /** 1411 * @brief Tests whether any of the bits are on. 1412 * @return True if at least one bit is set. 1413 */ 1414 _GLIBCXX23_CONSTEXPR 1415 bool 1416 any() const _GLIBCXX_NOEXCEPT 1417 { return this->_M_is_any(); } 1418 1419 /** 1420 * @brief Tests whether any of the bits are on. 1421 * @return True if none of the bits are set. 1422 */ 1423 _GLIBCXX23_CONSTEXPR 1424 bool 1425 none() const _GLIBCXX_NOEXCEPT 1426 { return !this->_M_is_any(); } 1427 1428 ///@{ 1429 /// Self-explanatory. 1430 _GLIBCXX23_CONSTEXPR 1431 bitset<_Nb> 1432 operator<<(size_t __position) const _GLIBCXX_NOEXCEPT 1433 { return bitset<_Nb>(*this) <<= __position; } 1434 1435 _GLIBCXX23_CONSTEXPR 1436 bitset<_Nb> 1437 operator>>(size_t __position) const _GLIBCXX_NOEXCEPT 1438 { return bitset<_Nb>(*this) >>= __position; } 1439 ///@} 1440 1441 /** 1442 * @brief Finds the index of the first "on" bit. 1443 * @return The index of the first bit set, or size() if not found. 1444 * @ingroup SGIextensions 1445 * @sa _Find_next 1446 */ 1447 _GLIBCXX23_CONSTEXPR 1448 size_t 1449 _Find_first() const _GLIBCXX_NOEXCEPT 1450 { return this->_M_do_find_first(_Nb); } 1451 1452 /** 1453 * @brief Finds the index of the next "on" bit after prev. 1454 * @return The index of the next bit set, or size() if not found. 1455 * @param __prev Where to start searching. 1456 * @ingroup SGIextensions 1457 * @sa _Find_first 1458 */ 1459 _GLIBCXX23_CONSTEXPR 1460 size_t 1461 _Find_next(size_t __prev) const _GLIBCXX_NOEXCEPT 1462 { return this->_M_do_find_next(__prev, _Nb); } 1463 1464 private: 1465 // Helper functions for string operations. 1466 template<class _CharT, class _Traits> 1467 _GLIBCXX23_CONSTEXPR 1468 void 1469 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t, 1470 _CharT, _CharT); 1471 1472 #if _GLIBCXX_HOSTED 1473 template<class _CharT, class _Traits, class _Alloc> 1474 _GLIBCXX23_CONSTEXPR 1475 void 1476 _M_copy_from_string(const std::basic_string<_CharT, 1477 _Traits, _Alloc>& __s, size_t __pos, size_t __n, 1478 _CharT __zero, _CharT __one) 1479 { _M_copy_from_ptr<_CharT, _Traits>(__s.data(), __s.size(), __pos, __n, 1480 __zero, __one); } 1481 1482 template<class _CharT, class _Traits, class _Alloc> 1483 _GLIBCXX23_CONSTEXPR 1484 void 1485 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>&, 1486 _CharT, _CharT) const; 1487 1488 template<class _CharT, class _Traits, size_t _Nb2> 1489 friend std::basic_istream<_CharT, _Traits>& 1490 operator>>(std::basic_istream<_CharT, _Traits>&, bitset<_Nb2>&); 1491 1492 template <class _CharT, class _Traits, size_t _Nb2> 1493 friend std::basic_ostream<_CharT, _Traits>& 1494 operator<<(std::basic_ostream<_CharT, _Traits>&, const bitset<_Nb2>&); 1495 #endif 1496 }; 1497 1498 // Definitions of non-inline member functions. 1499 template<size_t _Nb> 1500 template<class _CharT, class _Traits> 1501 _GLIBCXX23_CONSTEXPR 1502 void 1503 bitset<_Nb>:: 1504 _M_copy_from_ptr(const _CharT* __s, size_t __len, 1505 size_t __pos, size_t __n, _CharT __zero, _CharT __one) 1506 { 1507 reset(); 1508 const size_t __nbits = std::min(_Nb, std::min(__n, size_t(__len - __pos))); 1509 for (size_t __i = __nbits; __i > 0; --__i) 1510 { 1511 const _CharT __c = __s[__pos + __nbits - __i]; 1512 if (_Traits::eq(__c, __zero)) 1513 ; 1514 else if (_Traits::eq(__c, __one)) 1515 _Unchecked_set(__i - 1); 1516 else 1517 __throw_invalid_argument(__N("bitset::_M_copy_from_ptr")); 1518 } 1519 } 1520 1521 #if _GLIBCXX_HOSTED 1522 template<size_t _Nb> 1523 template<class _CharT, class _Traits, class _Alloc> 1524 _GLIBCXX23_CONSTEXPR 1525 void 1526 bitset<_Nb>:: 1527 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>& __s, 1528 _CharT __zero, _CharT __one) const 1529 { 1530 __s.assign(_Nb, __zero); 1531 size_t __n = this->_Find_first(); 1532 while (__n < _Nb) 1533 { 1534 __s[_Nb - __n - 1] = __one; 1535 __n = _Find_next(__n); 1536 } 1537 } 1538 #endif // HOSTED 1539 1540 // 23.3.5.3 bitset operations: 1541 ///@{ 1542 /** 1543 * @brief Global bitwise operations on bitsets. 1544 * @param __x A bitset. 1545 * @param __y A bitset of the same size as @a __x. 1546 * @return A new bitset. 1547 * 1548 * These should be self-explanatory. 1549 */ 1550 template<size_t _Nb> 1551 _GLIBCXX23_CONSTEXPR 1552 inline bitset<_Nb> 1553 operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT 1554 { 1555 bitset<_Nb> __result(__x); 1556 __result &= __y; 1557 return __result; 1558 } 1559 1560 template<size_t _Nb> 1561 _GLIBCXX23_CONSTEXPR 1562 inline bitset<_Nb> 1563 operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT 1564 { 1565 bitset<_Nb> __result(__x); 1566 __result |= __y; 1567 return __result; 1568 } 1569 1570 template <size_t _Nb> 1571 _GLIBCXX23_CONSTEXPR 1572 inline bitset<_Nb> 1573 operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT 1574 { 1575 bitset<_Nb> __result(__x); 1576 __result ^= __y; 1577 return __result; 1578 } 1579 ///@} 1580 1581 #if _GLIBCXX_HOSTED 1582 ///@{ 1583 /** 1584 * @brief Global I/O operators for bitsets. 1585 * 1586 * Direct I/O between streams and bitsets is supported. Output is 1587 * straightforward. Input will skip whitespace, only accept @a 0 and @a 1 1588 * characters, and will only extract as many digits as the %bitset will 1589 * hold. 1590 */ 1591 template<class _CharT, class _Traits, size_t _Nb> 1592 std::basic_istream<_CharT, _Traits>& 1593 operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x) 1594 { 1595 typedef typename _Traits::char_type char_type; 1596 typedef std::basic_istream<_CharT, _Traits> __istream_type; 1597 typedef typename __istream_type::ios_base __ios_base; 1598 1599 struct _Buffer 1600 { 1601 static _GLIBCXX_CONSTEXPR bool _S_use_alloca() { return _Nb <= 256; } 1602 1603 explicit _Buffer(_CharT* __p) : _M_ptr(__p) { } 1604 1605 ~_Buffer() 1606 { 1607 if _GLIBCXX17_CONSTEXPR (!_S_use_alloca()) 1608 delete[] _M_ptr; 1609 } 1610 1611 _CharT* const _M_ptr; 1612 }; 1613 _CharT* __ptr; 1614 if _GLIBCXX17_CONSTEXPR (_Buffer::_S_use_alloca()) 1615 __ptr = (_CharT*)__builtin_alloca(_Nb); 1616 else 1617 __ptr = new _CharT[_Nb]; 1618 const _Buffer __buf(__ptr); 1619 1620 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1621 // 303. Bitset input operator underspecified 1622 const char_type __zero = __is.widen('0'); 1623 const char_type __one = __is.widen('1'); 1624 1625 typename __ios_base::iostate __state = __ios_base::goodbit; 1626 typename __istream_type::sentry __sentry(__is); 1627 if (__sentry) 1628 { 1629 __try 1630 { 1631 for (size_t __i = _Nb; __i > 0; --__i) 1632 { 1633 static typename _Traits::int_type __eof = _Traits::eof(); 1634 1635 typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc(); 1636 if (_Traits::eq_int_type(__c1, __eof)) 1637 { 1638 __state |= __ios_base::eofbit; 1639 break; 1640 } 1641 else 1642 { 1643 const char_type __c2 = _Traits::to_char_type(__c1); 1644 if (_Traits::eq(__c2, __zero)) 1645 *__ptr++ = __zero; 1646 else if (_Traits::eq(__c2, __one)) 1647 *__ptr++ = __one; 1648 else if (_Traits:: 1649 eq_int_type(__is.rdbuf()->sputbackc(__c2), 1650 __eof)) 1651 { 1652 __state |= __ios_base::failbit; 1653 break; 1654 } 1655 } 1656 } 1657 } 1658 __catch(__cxxabiv1::__forced_unwind&) 1659 { 1660 __is._M_setstate(__ios_base::badbit); 1661 __throw_exception_again; 1662 } 1663 __catch(...) 1664 { __is._M_setstate(__ios_base::badbit); } 1665 } 1666 1667 if _GLIBCXX17_CONSTEXPR (_Nb) 1668 { 1669 if (size_t __len = __ptr - __buf._M_ptr) 1670 __x.template _M_copy_from_ptr<_CharT, _Traits>(__buf._M_ptr, __len, 1671 0, __len, 1672 __zero, __one); 1673 else 1674 __state |= __ios_base::failbit; 1675 } 1676 if (__state) 1677 __is.setstate(__state); 1678 return __is; 1679 } 1680 1681 template <class _CharT, class _Traits, size_t _Nb> 1682 std::basic_ostream<_CharT, _Traits>& 1683 operator<<(std::basic_ostream<_CharT, _Traits>& __os, 1684 const bitset<_Nb>& __x) 1685 { 1686 std::basic_string<_CharT, _Traits> __tmp; 1687 1688 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1689 // 396. what are characters zero and one. 1690 const ctype<_CharT>& __ct = use_facet<ctype<_CharT> >(__os.getloc()); 1691 __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1')); 1692 return __os << __tmp; 1693 } 1694 ///@} 1695 #endif // HOSTED 1696 1697 _GLIBCXX_END_NAMESPACE_CONTAINER 1698 } // namespace std 1699 1700 #undef _GLIBCXX_BITSET_WORDS 1701 #undef _GLIBCXX_BITSET_BITS_PER_WORD 1702 #undef _GLIBCXX_BITSET_BITS_PER_ULL 1703 1704 #if __cplusplus >= 201103L 1705 1706 namespace std _GLIBCXX_VISIBILITY(default) 1707 { 1708 _GLIBCXX_BEGIN_NAMESPACE_VERSION 1709 1710 // DR 1182. 1711 /// std::hash specialization for bitset. 1712 template<size_t _Nb> 1713 struct hash<_GLIBCXX_STD_C::bitset<_Nb>> 1714 : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<_Nb>> 1715 { 1716 size_t 1717 operator()(const _GLIBCXX_STD_C::bitset<_Nb>& __b) const noexcept 1718 { 1719 const size_t __clength = (_Nb + __CHAR_BIT__ - 1) / __CHAR_BIT__; 1720 return std::_Hash_impl::hash(__b._M_getdata(), __clength); 1721 } 1722 }; 1723 1724 template<> 1725 struct hash<_GLIBCXX_STD_C::bitset<0>> 1726 : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<0>> 1727 { 1728 size_t 1729 operator()(const _GLIBCXX_STD_C::bitset<0>&) const noexcept 1730 { return 0; } 1731 }; 1732 1733 _GLIBCXX_END_NAMESPACE_VERSION 1734 } // namespace 1735 1736 #endif // C++11 1737 1738 #if defined _GLIBCXX_DEBUG && _GLIBCXX_HOSTED 1739 # include <debug/bitset> 1740 #endif 1741 1742 #endif /* _GLIBCXX_BITSET */
Contact us
|
About us
|
Term of use
|
Copyright © 2000-2025 MyWebUniversity.com ™
