1// TR2 <dynamic_bitset> -*- C++ -*- 2 3// Copyright (C) 2009-2013 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/** @file tr2/dynamic_bitset 26 * This is a TR2 C++ Library header. 27 */ 28 29#ifndef _GLIBCXX_TR2_DYNAMIC_BITSET 30#define _GLIBCXX_TR2_DYNAMIC_BITSET 1 31 32#pragma GCC system_header 33 34#include <limits> 35#include <vector> 36#include <string> 37#include <memory> // For std::allocator 38#include <bits/functexcept.h> // For invalid_argument, out_of_range, 39 // overflow_error 40#include <iosfwd> 41#include <bits/cxxabi_forced.h> 42 43namespace std _GLIBCXX_VISIBILITY(default) 44{ 45namespace tr2 46{ 47_GLIBCXX_BEGIN_NAMESPACE_VERSION 48 49 /** 50 * Dynamic Bitset. 51 * 52 * See N2050, 53 * Proposal to Add a Dynamically Sizeable Bitset to the Standard Library. 54 */ 55namespace __detail 56{ 57 58template<typename T> 59class _Bool2UChar 60{ 61 typedef T type; 62}; 63 64template<> 65class _Bool2UChar<bool> 66{ 67public: 68 typedef unsigned char type; 69}; 70 71} 72 73 /** 74 * Base class, general case. 75 * 76 * See documentation for dynamic_bitset. 77 */ 78 template<typename _WordT = unsigned long long, 79 typename _Alloc = std::allocator<_WordT>> 80 struct __dynamic_bitset_base 81 { 82 static_assert(std::is_unsigned<_WordT>::value, "template argument " 83 "_WordT not an unsigned integral type"); 84 85 typedef _WordT block_type; 86 typedef _Alloc allocator_type; 87 typedef size_t size_type; 88 89 static const size_type _S_bits_per_block = __CHAR_BIT__ * sizeof(block_type); 90 static const size_type npos = static_cast<size_type>(-1); 91 92 /// 0 is the least significant word. 93 std::vector<block_type, allocator_type> _M_w; 94 95 explicit 96 __dynamic_bitset_base(const allocator_type& __alloc = allocator_type()) 97 : _M_w(__alloc) 98 { } 99 100 explicit 101 __dynamic_bitset_base(__dynamic_bitset_base&& __b) 102 { this->_M_w.swap(__b._M_w); } 103 104 explicit 105 __dynamic_bitset_base(size_type __nbits, unsigned long long __val = 0ULL, 106 const allocator_type& __alloc = allocator_type()) 107 : _M_w(__nbits / _S_bits_per_block 108 + (__nbits % _S_bits_per_block > 0), 109 __val, __alloc) 110 { 111 unsigned long long __mask = ~static_cast<block_type>(0); 112 size_t __n = std::min(this->_M_w.size(), 113 sizeof(unsigned long long) / sizeof(block_type)); 114 for (size_t __i = 0; __i < __n; ++__i) 115 { 116 this->_M_w[__i] = (__val & __mask) >> (__i * _S_bits_per_block); 117 __mask <<= _S_bits_per_block; 118 } 119 } 120 121 void 122 _M_assign(const __dynamic_bitset_base& __b) 123 { this->_M_w = __b._M_w; } 124 125 void 126 _M_swap(__dynamic_bitset_base& __b) 127 { this->_M_w.swap(__b._M_w); } 128 129 void 130 _M_clear() 131 { this->_M_w.clear(); } 132 133 void 134 _M_resize(size_t __nbits, bool __value) 135 { 136 size_t __sz = __nbits / _S_bits_per_block; 137 if (__nbits % _S_bits_per_block > 0) 138 ++__sz; 139 if (__sz != this->_M_w.size()) 140 this->_M_w.resize(__sz); 141 } 142 143 allocator_type 144 _M_get_allocator() const 145 { return this->_M_w.get_allocator(); } 146 147 static size_type 148 _S_whichword(size_type __pos) noexcept 149 { return __pos / _S_bits_per_block; } 150 151 static size_type 152 _S_whichbyte(size_type __pos) noexcept 153 { return (__pos % _S_bits_per_block) / __CHAR_BIT__; } 154 155 static size_type 156 _S_whichbit(size_type __pos) noexcept 157 { return __pos % _S_bits_per_block; } 158 159 static block_type 160 _S_maskbit(size_type __pos) noexcept 161 { return (static_cast<block_type>(1)) << _S_whichbit(__pos); } 162 163 block_type& 164 _M_getword(size_type __pos) 165 { return this->_M_w[_S_whichword(__pos)]; } 166 167 block_type 168 _M_getword(size_type __pos) const 169 { return this->_M_w[_S_whichword(__pos)]; } 170 171 block_type& 172 _M_hiword() 173 { return this->_M_w[_M_w.size() - 1]; } 174 175 block_type 176 _M_hiword() const 177 { return this->_M_w[_M_w.size() - 1]; } 178 179 void 180 _M_do_and(const __dynamic_bitset_base& __x) 181 { 182 if (__x._M_w.size() == this->_M_w.size()) 183 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 184 this->_M_w[__i] &= __x._M_w[__i]; 185 else 186 return; 187 } 188 189 void 190 _M_do_or(const __dynamic_bitset_base& __x) 191 { 192 if (__x._M_w.size() == this->_M_w.size()) 193 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 194 this->_M_w[__i] |= __x._M_w[__i]; 195 else 196 return; 197 } 198 199 void 200 _M_do_xor(const __dynamic_bitset_base& __x) 201 { 202 if (__x._M_w.size() == this->_M_w.size()) 203 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 204 this->_M_w[__i] ^= __x._M_w[__i]; 205 else 206 return; 207 } 208 209 void 210 _M_do_dif(const __dynamic_bitset_base& __x) 211 { 212 if (__x._M_w.size() == this->_M_w.size()) 213 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 214 this->_M_w[__i] &= ~__x._M_w[__i]; 215 else 216 return; 217 } 218 219 void 220 _M_do_left_shift(size_t __shift); 221 222 void 223 _M_do_right_shift(size_t __shift); 224 225 void 226 _M_do_flip() 227 { 228 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 229 this->_M_w[__i] = ~this->_M_w[__i]; 230 } 231 232 void 233 _M_do_set() 234 { 235 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 236 this->_M_w[__i] = ~static_cast<block_type>(0); 237 } 238 239 void 240 _M_do_reset() 241 { 242 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 243 this->_M_w[__i] = static_cast<block_type>(0); 244 } 245 246 bool 247 _M_is_equal(const __dynamic_bitset_base& __x) const 248 { 249 if (__x.size() == this->size()) 250 { 251 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 252 if (this->_M_w[__i] != __x._M_w[__i]) 253 return false; 254 return true; 255 } 256 else 257 return false; 258 } 259 260 bool 261 _M_is_less(const __dynamic_bitset_base& __x) const 262 { 263 if (__x.size() == this->size()) 264 { 265 for (size_t __i = this->_M_w.size(); __i > 0; --__i) 266 { 267 if (this->_M_w[__i-1] < __x._M_w[__i-1]) 268 return true; 269 else if (this->_M_w[__i-1] > __x._M_w[__i-1]) 270 return false; 271 } 272 return false; 273 } 274 else 275 return false; 276 } 277 278 size_t 279 _M_are_all_aux() const 280 { 281 for (size_t __i = 0; __i < this->_M_w.size() - 1; ++__i) 282 if (_M_w[__i] != ~static_cast<block_type>(0)) 283 return 0; 284 return ((this->_M_w.size() - 1) * _S_bits_per_block 285 + __builtin_popcountl(this->_M_hiword())); 286 } 287 288 bool 289 _M_is_any() const 290 { 291 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 292 if (this->_M_w[__i] != static_cast<block_type>(0)) 293 return true; 294 return false; 295 } 296 297 bool 298 _M_is_subset_of(const __dynamic_bitset_base& __b) 299 { 300 if (__b.size() == this->size()) 301 { 302 for (size_t __i = 0; __i < _M_w.size(); ++__i) 303 if (this->_M_w[__i] != (this->_M_w[__i] | __b._M_w[__i])) 304 return false; 305 return true; 306 } 307 else 308 return false; 309 } 310 311 bool 312 _M_is_proper_subset_of(const __dynamic_bitset_base& __b) const 313 { 314 if (this->is_subset_of(__b)) 315 { 316 if (*this == __b) 317 return false; 318 else 319 return true; 320 } 321 else 322 return false; 323 } 324 325 size_t 326 _M_do_count() const 327 { 328 size_t __result = 0; 329 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 330 __result += __builtin_popcountl(this->_M_w[__i]); 331 return __result; 332 } 333 334 size_type 335 _M_size() const noexcept 336 { return this->_M_w.size(); } 337 338 unsigned long 339 _M_do_to_ulong() const; 340 341 unsigned long long 342 _M_do_to_ullong() const; 343 344 // find first "on" bit 345 size_type 346 _M_do_find_first(size_t __not_found) const; 347 348 // find the next "on" bit that follows "prev" 349 size_type 350 _M_do_find_next(size_t __prev, size_t __not_found) const; 351 352 // do append of block 353 void 354 _M_do_append_block(block_type __block, size_type __pos) 355 { 356 size_t __offset = __pos % _S_bits_per_block; 357 if (__offset == 0) 358 this->_M_w.push_back(__block); 359 else 360 { 361 this->_M_hiword() |= (__block << __offset); 362 this->_M_w.push_back(__block >> (_S_bits_per_block - __offset)); 363 } 364 } 365 }; 366 367 // Definitions of non-inline functions from __dynamic_bitset_base. 368 template<typename _WordT, typename _Alloc> 369 void 370 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_left_shift(size_t __shift) 371 { 372 if (__builtin_expect(__shift != 0, 1)) 373 { 374 const size_t __wshift = __shift / _S_bits_per_block; 375 const size_t __offset = __shift % _S_bits_per_block; 376 377 if (__offset == 0) 378 for (size_t __n = this->_M_w.size() - 1; __n >= __wshift; --__n) 379 this->_M_w[__n] = this->_M_w[__n - __wshift]; 380 else 381 { 382 const size_t __sub_offset = _S_bits_per_block - __offset; 383 for (size_t __n = _M_w.size() - 1; __n > __wshift; --__n) 384 this->_M_w[__n] = ((this->_M_w[__n - __wshift] << __offset) 385 | (this->_M_w[__n - __wshift - 1] >> __sub_offset)); 386 this->_M_w[__wshift] = this->_M_w[0] << __offset; 387 } 388 389 //// std::fill(this->_M_w.begin(), this->_M_w.begin() + __wshift, 390 //// static_cast<_WordT>(0)); 391 } 392 } 393 394 template<typename _WordT, typename _Alloc> 395 void 396 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_right_shift(size_t __shift) 397 { 398 if (__builtin_expect(__shift != 0, 1)) 399 { 400 const size_t __wshift = __shift / _S_bits_per_block; 401 const size_t __offset = __shift % _S_bits_per_block; 402 const size_t __limit = this->_M_w.size() - __wshift - 1; 403 404 if (__offset == 0) 405 for (size_t __n = 0; __n <= __limit; ++__n) 406 this->_M_w[__n] = this->_M_w[__n + __wshift]; 407 else 408 { 409 const size_t __sub_offset = (_S_bits_per_block 410 - __offset); 411 for (size_t __n = 0; __n < __limit; ++__n) 412 this->_M_w[__n] = ((this->_M_w[__n + __wshift] >> __offset) 413 | (this->_M_w[__n + __wshift + 1] << __sub_offset)); 414 this->_M_w[__limit] = this->_M_w[_M_w.size()-1] >> __offset; 415 } 416 417 ////std::fill(this->_M_w.begin() + __limit + 1, this->_M_w.end(), 418 //// static_cast<_WordT>(0)); 419 } 420 } 421 422 template<typename _WordT, typename _Alloc> 423 unsigned long 424 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ulong() const 425 { 426 size_t __n = sizeof(unsigned long) / sizeof(block_type); 427 for (size_t __i = __n; __i < this->_M_w.size(); ++__i) 428 if (this->_M_w[__i]) 429 __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ulong")); 430 unsigned long __res = 0UL; 431 for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i) 432 __res += this->_M_w[__i] << (__i * _S_bits_per_block); 433 return __res; 434 } 435 436 template<typename _WordT, typename _Alloc> 437 unsigned long long 438 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ullong() const 439 { 440 size_t __n = sizeof(unsigned long long) / sizeof(block_type); 441 for (size_t __i = __n; __i < this->_M_w.size(); ++__i) 442 if (this->_M_w[__i]) 443 __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ullong")); 444 unsigned long long __res = 0ULL; 445 for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i) 446 __res += this->_M_w[__i] << (__i * _S_bits_per_block); 447 return __res; 448 } 449 450 template<typename _WordT, typename _Alloc> 451 size_t 452 __dynamic_bitset_base<_WordT, _Alloc> 453 ::_M_do_find_first(size_t __not_found) const 454 { 455 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 456 { 457 _WordT __thisword = this->_M_w[__i]; 458 if (__thisword != static_cast<_WordT>(0)) 459 return (__i * _S_bits_per_block 460 + __builtin_ctzl(__thisword)); 461 } 462 // not found, so return an indication of failure. 463 return __not_found; 464 } 465 466 template<typename _WordT, typename _Alloc> 467 size_t 468 __dynamic_bitset_base<_WordT, _Alloc> 469 ::_M_do_find_next(size_t __prev, size_t __not_found) const 470 { 471 // make bound inclusive 472 ++__prev; 473 474 // check out of bounds 475 if (__prev >= this->_M_w.size() * _S_bits_per_block) 476 return __not_found; 477 478 // search first word 479 size_t __i = _S_whichword(__prev); 480 _WordT __thisword = this->_M_w[__i]; 481 482 // mask off bits below bound 483 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev); 484 485 if (__thisword != static_cast<_WordT>(0)) 486 return (__i * _S_bits_per_block 487 + __builtin_ctzl(__thisword)); 488 489 // check subsequent words 490 for (++__i; __i < this->_M_w.size(); ++__i) 491 { 492 __thisword = this->_M_w[__i]; 493 if (__thisword != static_cast<_WordT>(0)) 494 return (__i * _S_bits_per_block 495 + __builtin_ctzl(__thisword)); 496 } 497 // not found, so return an indication of failure. 498 return __not_found; 499 } // end _M_do_find_next 500 501 /** 502 * @brief The %dynamic_bitset class represents a sequence of bits. 503 * 504 * @ingroup containers 505 * 506 * (Note that %dynamic_bitset does @e not meet the formal 507 * requirements of a <a href="tables.html#65">container</a>. 508 * Mainly, it lacks iterators.) 509 * 510 * The template argument, @a Nb, may be any non-negative number, 511 * specifying the number of bits (e.g., "0", "12", "1024*1024"). 512 * 513 * In the general unoptimized case, storage is allocated in 514 * word-sized blocks. Let B be the number of bits in a word, then 515 * (Nb+(B-1))/B words will be used for storage. B - Nb%B bits are 516 * unused. (They are the high-order bits in the highest word.) It 517 * is a class invariant that those unused bits are always zero. 518 * 519 * If you think of %dynamic_bitset as "a simple array of bits," be 520 * aware that your mental picture is reversed: a %dynamic_bitset 521 * behaves the same way as bits in integers do, with the bit at 522 * index 0 in the "least significant / right-hand" position, and 523 * the bit at index Nb-1 in the "most significant / left-hand" 524 * position. Thus, unlike other containers, a %dynamic_bitset's 525 * index "counts from right to left," to put it very loosely. 526 * 527 * This behavior is preserved when translating to and from strings. 528 * For example, the first line of the following program probably 529 * prints "b('a') is 0001100001" on a modern ASCII system. 530 * 531 * @code 532 * #include <dynamic_bitset> 533 * #include <iostream> 534 * #include <sstream> 535 * 536 * using namespace std; 537 * 538 * int main() 539 * { 540 * long a = 'a'; 541 * dynamic_bitset b(a); 542 * 543 * cout << "b('a') is " << b << endl; 544 * 545 * ostringstream s; 546 * s << b; 547 * string str = s.str(); 548 * cout << "index 3 in the string is " << str[3] << " but\n" 549 * << "index 3 in the bitset is " << b[3] << endl; 550 * } 551 * @endcode 552 * 553 * Also see: 554 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch33s02.html 555 * for a description of extensions. 556 * 557 * Most of the actual code isn't contained in %dynamic_bitset<> 558 * itself, but in the base class __dynamic_bitset_base. The base 559 * class works with whole words, not with individual bits. This 560 * allows us to specialize __dynamic_bitset_base for the important 561 * special case where the %dynamic_bitset is only a single word. 562 * 563 * Extra confusion can result due to the fact that the storage for 564 * __dynamic_bitset_base @e is a vector, and is indexed as such. This is 565 * carefully encapsulated. 566 */ 567 template<typename _WordT = unsigned long long, 568 typename _Alloc = std::allocator<_WordT>> 569 class dynamic_bitset 570 : private __dynamic_bitset_base<_WordT, _Alloc> 571 { 572 static_assert(std::is_unsigned<_WordT>::value, "template argument " 573 "_WordT not an unsigned integral type"); 574 575 public: 576 577 typedef __dynamic_bitset_base<_WordT, _Alloc> _Base; 578 typedef _WordT block_type; 579 typedef _Alloc allocator_type; 580 typedef size_t size_type; 581 582 static const size_type bits_per_block = __CHAR_BIT__ * sizeof(block_type); 583 // Use this: constexpr size_type std::numeric_limits<size_type>::max(). 584 static const size_type npos = static_cast<size_type>(-1); 585 586 private: 587 588 // Clear the unused bits in the uppermost word. 589 void 590 _M_do_sanitize() 591 { 592 size_type __shift = this->_M_Nb % bits_per_block; 593 if (__shift > 0) 594 this->_M_hiword() &= ~((~static_cast<block_type>(0)) << __shift); 595 } 596 597 /** 598 * These versions of single-bit set, reset, flip, and test 599 * do no range checking. 600 */ 601 dynamic_bitset<_WordT, _Alloc>& 602 _M_unchecked_set(size_type __pos) 603 { 604 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 605 return *this; 606 } 607 608 dynamic_bitset<_WordT, _Alloc>& 609 _M_unchecked_set(size_type __pos, int __val) 610 { 611 if (__val) 612 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 613 else 614 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 615 return *this; 616 } 617 618 dynamic_bitset<_WordT, _Alloc>& 619 _M_unchecked_reset(size_type __pos) 620 { 621 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 622 return *this; 623 } 624 625 dynamic_bitset<_WordT, _Alloc>& 626 _M_unchecked_flip(size_type __pos) 627 { 628 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); 629 return *this; 630 } 631 632 bool 633 _M_unchecked_test(size_type __pos) const 634 { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) 635 != static_cast<_WordT>(0)); } 636 637 size_type _M_Nb; 638 639 public: 640 /** 641 * This encapsulates the concept of a single bit. An instance 642 * of this class is a proxy for an actual bit; this way the 643 * individual bit operations are done as faster word-size 644 * bitwise instructions. 645 * 646 * Most users will never need to use this class directly; 647 * conversions to and from bool are automatic and should be 648 * transparent. Overloaded operators help to preserve the 649 * illusion. 650 * 651 * (On a typical system, this "bit %reference" is 64 times the 652 * size of an actual bit. Ha.) 653 */ 654 class reference 655 { 656 friend class dynamic_bitset; 657 658 block_type *_M_wp; 659 size_type _M_bpos; 660 661 // left undefined 662 reference(); 663 664 public: 665 reference(dynamic_bitset& __b, size_type __pos) 666 { 667 this->_M_wp = &__b._M_getword(__pos); 668 this->_M_bpos = _Base::_S_whichbit(__pos); 669 } 670 671 ~reference() 672 { } 673 674 // For b[i] = __x; 675 reference& 676 operator=(bool __x) 677 { 678 if (__x) 679 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos); 680 else 681 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos); 682 return *this; 683 } 684 685 // For b[i] = b[__j]; 686 reference& 687 operator=(const reference& __j) 688 { 689 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos))) 690 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos); 691 else 692 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos); 693 return *this; 694 } 695 696 // Flips the bit 697 bool 698 operator~() const 699 { return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; } 700 701 // For __x = b[i]; 702 operator bool() const 703 { return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; } 704 705 // For b[i].flip(); 706 reference& 707 flip() 708 { 709 *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos); 710 return *this; 711 } 712 }; 713 714 friend class reference; 715 716 typedef bool const_reference; 717 718 // 23.3.5.1 constructors: 719 /// All bits set to zero. 720 explicit 721 dynamic_bitset(const allocator_type& __alloc = allocator_type()) 722 : _Base(__alloc), _M_Nb(0) 723 { } 724 725 /// Initial bits bitwise-copied from a single word (others set to zero). 726 explicit 727 dynamic_bitset(size_type __nbits, unsigned long long __val = 0ULL, 728 const allocator_type& __alloc = allocator_type()) 729 : _Base(__nbits, __val, __alloc), 730 _M_Nb(__nbits) 731 { } 732 733 dynamic_bitset(initializer_list<block_type> __il, 734 const allocator_type& __alloc = allocator_type()) 735 : _Base(__alloc), _M_Nb(0) 736 { this->append(__il); } 737 738 /** 739 * @brief Use a subset of a string. 740 * @param __str A string of '0' and '1' characters. 741 * @param __pos Index of the first character in @p __str to use. 742 * @param __n The number of characters to copy. 743 * @throw std::out_of_range If @p __pos is bigger the size of @p __str. 744 * @throw std::invalid_argument If a character appears in the string 745 * which is neither '0' nor '1'. 746 */ 747 template<typename _CharT, typename _Traits, typename _Alloc1> 748 explicit 749 dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc1>& __str, 750 typename basic_string<_CharT,_Traits,_Alloc1>::size_type 751 __pos = 0, 752 typename basic_string<_CharT,_Traits,_Alloc1>::size_type 753 __n = std::basic_string<_CharT, _Traits, _Alloc1>::npos, 754 _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'), 755 const allocator_type& __alloc = allocator_type()) 756 : _Base(__alloc), 757 _M_Nb(0) // Watch for npos. 758 { 759 if (__pos > __str.size()) 760 __throw_out_of_range(__N("dynamic_bitset::bitset initial position " 761 "not valid")); 762 763 // Watch for npos. 764 this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n); 765 this->resize(this->_M_Nb); 766 this->_M_copy_from_string(__str, __pos, __n, 767 _CharT('0'), _CharT('1')); 768 } 769 770 /** 771 * @brief Construct from a string. 772 * @param __str A string of '0' and '1' characters. 773 * @throw std::invalid_argument If a character appears in the string 774 * which is neither '0' nor '1'. 775 */ 776 explicit 777 dynamic_bitset(const char* __str, 778 const allocator_type& __alloc = allocator_type()) 779 : _Base(__alloc) 780 { 781 size_t __len = 0; 782 if (__str) 783 while (__str[__len] != '\0') 784 ++__len; 785 this->resize(__len); 786 this->_M_copy_from_ptr<char,std::char_traits<char>> 787 (__str, __len, 0, __len, '0', '1'); 788 } 789 790 /** 791 * @brief Copy constructor. 792 */ 793 dynamic_bitset(const dynamic_bitset& __b) 794 : _Base(__b), _M_Nb(__b.size()) 795 { } 796 797 /** 798 * @brief Move constructor. 799 */ 800 dynamic_bitset(dynamic_bitset&& __b) 801 : _Base(std::forward<_Base>(__b)), _M_Nb(__b.size()) 802 { } 803 804 /** 805 * @brief Swap with another bitset. 806 */ 807 void 808 swap(dynamic_bitset& __b) 809 { 810 this->_M_swap(__b); 811 std::swap(this->_M_Nb, __b._M_Nb); 812 } 813 814 /** 815 * @brief Assignment. 816 */ 817 dynamic_bitset& 818 operator=(const dynamic_bitset& __b) 819 { 820 if (&__b != this) 821 { 822 this->_M_assign(__b); 823 this->_M_Nb = __b._M_Nb; 824 } 825 } 826 827 /** 828 * @brief Move assignment. 829 */ 830 dynamic_bitset& 831 operator=(dynamic_bitset&& __b) 832 { 833 this->swap(__b); 834 return *this; 835 } 836 837 /** 838 * @brief Return the allocator for the bitset. 839 */ 840 allocator_type 841 get_allocator() const 842 { return this->_M_get_allocator(); } 843 844 /** 845 * @brief Resize the bitset. 846 */ 847 void 848 resize(size_type __nbits, bool __value = false) 849 { 850 this->_M_resize(__nbits, __value); 851 this->_M_Nb = __nbits; 852 this->_M_do_sanitize(); 853 } 854 855 /** 856 * @brief Clear the bitset. 857 */ 858 void 859 clear() 860 { 861 this->_M_clear(); 862 this->_M_Nb = 0; 863 } 864 865 /** 866 * @brief Push a bit onto the high end of the bitset. 867 */ 868 void 869 push_back(bool __bit) 870 { 871 if (size_t __offset = this->size() % bits_per_block == 0) 872 this->_M_do_append_block(block_type(0), this->_M_Nb); 873 ++this->_M_Nb; 874 this->_M_unchecked_set(this->_M_Nb, __bit); 875 } 876 877 /** 878 * @brief Append a block. 879 */ 880 void 881 append(block_type __block) 882 { 883 this->_M_do_append_block(__block, this->_M_Nb); 884 this->_M_Nb += bits_per_block; 885 } 886 887 /** 888 * @brief 889 */ 890 void 891 append(initializer_list<block_type> __il) 892 { this->append(__il.begin(), __il.end()); } 893 894 /** 895 * @brief Append an iterator range of blocks. 896 */ 897 template <typename _BlockInputIterator> 898 void 899 append(_BlockInputIterator __first, _BlockInputIterator __last) 900 { 901 for (; __first != __last; ++__first) 902 this->append(*__first); 903 } 904 905 // 23.3.5.2 dynamic_bitset operations: 906 //@{ 907 /** 908 * @brief Operations on dynamic_bitsets. 909 * @param __rhs A same-sized dynamic_bitset. 910 * 911 * These should be self-explanatory. 912 */ 913 dynamic_bitset<_WordT, _Alloc>& 914 operator&=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 915 { 916 this->_M_do_and(__rhs); 917 return *this; 918 } 919 920 dynamic_bitset<_WordT, _Alloc>& 921 operator&=(dynamic_bitset<_WordT, _Alloc>&& __rhs) 922 { 923 this->_M_do_and(std::move(__rhs)); 924 return *this; 925 } 926 927 dynamic_bitset<_WordT, _Alloc>& 928 operator|=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 929 { 930 this->_M_do_or(__rhs); 931 return *this; 932 } 933 934 dynamic_bitset<_WordT, _Alloc>& 935 operator^=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 936 { 937 this->_M_do_xor(__rhs); 938 return *this; 939 } 940 941 dynamic_bitset<_WordT, _Alloc>& 942 operator-=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 943 { 944 this->_M_do_dif(__rhs); 945 return *this; 946 } 947 //@} 948 949 //@{ 950 /** 951 * @brief Operations on dynamic_bitsets. 952 * @param __pos The number of places to shift. 953 * 954 * These should be self-explanatory. 955 */ 956 dynamic_bitset<_WordT, _Alloc>& 957 operator<<=(size_type __pos) 958 { 959 if (__builtin_expect(__pos < this->_M_Nb, 1)) 960 { 961 this->_M_do_left_shift(__pos); 962 this->_M_do_sanitize(); 963 } 964 else 965 this->_M_do_reset(); 966 return *this; 967 } 968 969 dynamic_bitset<_WordT, _Alloc>& 970 operator>>=(size_type __pos) 971 { 972 if (__builtin_expect(__pos < this->_M_Nb, 1)) 973 { 974 this->_M_do_right_shift(__pos); 975 this->_M_do_sanitize(); 976 } 977 else 978 this->_M_do_reset(); 979 return *this; 980 } 981 //@} 982 983 // Set, reset, and flip. 984 /** 985 * @brief Sets every bit to true. 986 */ 987 dynamic_bitset<_WordT, _Alloc>& 988 set() 989 { 990 this->_M_do_set(); 991 this->_M_do_sanitize(); 992 return *this; 993 } 994 995 /** 996 * @brief Sets a given bit to a particular value. 997 * @param __pos The index of the bit. 998 * @param __val Either true or false, defaults to true. 999 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 1000 */ 1001 dynamic_bitset<_WordT, _Alloc>& 1002 set(size_type __pos, bool __val = true) 1003 { 1004 if (__pos >= _M_Nb) 1005 __throw_out_of_range(__N("dynamic_bitset::set")); 1006 return this->_M_unchecked_set(__pos, __val); 1007 } 1008 1009 /** 1010 * @brief Sets every bit to false. 1011 */ 1012 dynamic_bitset<_WordT, _Alloc>& 1013 reset() 1014 { 1015 this->_M_do_reset(); 1016 return *this; 1017 } 1018 1019 /** 1020 * @brief Sets a given bit to false. 1021 * @param __pos The index of the bit. 1022 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 1023 * 1024 * Same as writing @c set(__pos, false). 1025 */ 1026 dynamic_bitset<_WordT, _Alloc>& 1027 reset(size_type __pos) 1028 { 1029 if (__pos >= _M_Nb) 1030 __throw_out_of_range(__N("dynamic_bitset::reset")); 1031 return this->_M_unchecked_reset(__pos); 1032 } 1033 1034 /** 1035 * @brief Toggles every bit to its opposite value. 1036 */ 1037 dynamic_bitset<_WordT, _Alloc>& 1038 flip() 1039 { 1040 this->_M_do_flip(); 1041 this->_M_do_sanitize(); 1042 return *this; 1043 } 1044 1045 /** 1046 * @brief Toggles a given bit to its opposite value. 1047 * @param __pos The index of the bit. 1048 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 1049 */ 1050 dynamic_bitset<_WordT, _Alloc>& 1051 flip(size_type __pos) 1052 { 1053 if (__pos >= _M_Nb) 1054 __throw_out_of_range(__N("dynamic_bitset::flip")); 1055 return this->_M_unchecked_flip(__pos); 1056 } 1057 1058 /// See the no-argument flip(). 1059 dynamic_bitset<_WordT, _Alloc> 1060 operator~() const 1061 { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); } 1062 1063 //@{ 1064 /** 1065 * @brief Array-indexing support. 1066 * @param __pos Index into the %dynamic_bitset. 1067 * @return A bool for a 'const %dynamic_bitset'. For non-const 1068 * bitsets, an instance of the reference proxy class. 1069 * @note These operators do no range checking and throw no 1070 * exceptions, as required by DR 11 to the standard. 1071 */ 1072 reference 1073 operator[](size_type __pos) 1074 { return reference(*this,__pos); } 1075 1076 const_reference 1077 operator[](size_type __pos) const 1078 { return _M_unchecked_test(__pos); } 1079 //@} 1080 1081 /** 1082 * @brief Returns a numerical interpretation of the %dynamic_bitset. 1083 * @return The integral equivalent of the bits. 1084 * @throw std::overflow_error If there are too many bits to be 1085 * represented in an @c unsigned @c long. 1086 */ 1087 unsigned long 1088 to_ulong() const 1089 { return this->_M_do_to_ulong(); } 1090 1091 /** 1092 * @brief Returns a numerical interpretation of the %dynamic_bitset. 1093 * @return The integral equivalent of the bits. 1094 * @throw std::overflow_error If there are too many bits to be 1095 * represented in an @c unsigned @c long. 1096 */ 1097 unsigned long long 1098 to_ullong() const 1099 { return this->_M_do_to_ullong(); } 1100 1101 /** 1102 * @brief Returns a character interpretation of the %dynamic_bitset. 1103 * @return The string equivalent of the bits. 1104 * 1105 * Note the ordering of the bits: decreasing character positions 1106 * correspond to increasing bit positions (see the main class notes for 1107 * an example). 1108 */ 1109 template<typename _CharT = char, 1110 typename _Traits = std::char_traits<_CharT>, 1111 typename _Alloc1 = std::allocator<_CharT>> 1112 std::basic_string<_CharT, _Traits, _Alloc1> 1113 to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const 1114 { 1115 std::basic_string<_CharT, _Traits, _Alloc1> __result; 1116 _M_copy_to_string(__result, __zero, __one); 1117 return __result; 1118 } 1119 1120 // Helper functions for string operations. 1121 template<typename _CharT, typename _Traits> 1122 void 1123 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t, 1124 _CharT, _CharT); 1125 1126 template<typename _CharT, typename _Traits, typename _Alloc1> 1127 void 1128 _M_copy_from_string(const std::basic_string<_CharT, 1129 _Traits, _Alloc1>& __str, size_t __pos, size_t __n, 1130 _CharT __zero = _CharT('0'), 1131 _CharT __one = _CharT('1')) 1132 { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(), 1133 __pos, __n, __zero, __one); } 1134 1135 template<typename _CharT, typename _Traits, typename _Alloc1> 1136 void 1137 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str, 1138 _CharT __zero = _CharT('0'), 1139 _CharT __one = _CharT('1')) const; 1140 1141 /// Returns the number of bits which are set. 1142 size_type 1143 count() const noexcept 1144 { return this->_M_do_count(); } 1145 1146 /// Returns the total number of bits. 1147 size_type 1148 size() const noexcept 1149 { return this->_M_Nb; } 1150 1151 /// Returns the total number of blocks. 1152 size_type 1153 num_blocks() const noexcept 1154 { return this->_M_size(); } 1155 1156 /// Returns true if the dynamic_bitset is empty. 1157 bool 1158 empty() const noexcept 1159 { return (this->_M_Nb == 0); } 1160 1161 /// Returns the maximum size of a dynamic_bitset object having the same 1162 /// type as *this. 1163 /// The real answer is max() * bits_per_block but is likely to overflow. 1164 constexpr size_type 1165 max_size() noexcept 1166 { return std::numeric_limits<block_type>::max(); } 1167 1168 /** 1169 * @brief Tests the value of a bit. 1170 * @param __pos The index of a bit. 1171 * @return The value at @a __pos. 1172 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 1173 */ 1174 bool 1175 test(size_type __pos) const 1176 { 1177 if (__pos >= _M_Nb) 1178 __throw_out_of_range(__N("dynamic_bitset::test")); 1179 return _M_unchecked_test(__pos); 1180 } 1181 1182 /** 1183 * @brief Tests whether all the bits are on. 1184 * @return True if all the bits are set. 1185 */ 1186 bool 1187 all() const 1188 { return this->_M_are_all_aux() == _M_Nb; } 1189 1190 /** 1191 * @brief Tests whether any of the bits are on. 1192 * @return True if at least one bit is set. 1193 */ 1194 bool 1195 any() const 1196 { return this->_M_is_any(); } 1197 1198 /** 1199 * @brief Tests whether any of the bits are on. 1200 * @return True if none of the bits are set. 1201 */ 1202 bool 1203 none() const 1204 { return !this->_M_is_any(); } 1205 1206 //@{ 1207 /// Self-explanatory. 1208 dynamic_bitset<_WordT, _Alloc> 1209 operator<<(size_type __pos) const 1210 { return dynamic_bitset<_WordT, _Alloc>(*this) <<= __pos; } 1211 1212 dynamic_bitset<_WordT, _Alloc> 1213 operator>>(size_type __pos) const 1214 { return dynamic_bitset<_WordT, _Alloc>(*this) >>= __pos; } 1215 //@} 1216 1217 /** 1218 * @brief Finds the index of the first "on" bit. 1219 * @return The index of the first bit set, or size() if not found. 1220 * @sa find_next 1221 */ 1222 size_type 1223 find_first() const 1224 { return this->_M_do_find_first(this->_M_Nb); } 1225 1226 /** 1227 * @brief Finds the index of the next "on" bit after prev. 1228 * @return The index of the next bit set, or size() if not found. 1229 * @param __prev Where to start searching. 1230 * @sa find_first 1231 */ 1232 size_type 1233 find_next(size_t __prev) const 1234 { return this->_M_do_find_next(__prev, this->_M_Nb); } 1235 1236 bool 1237 is_subset_of(const dynamic_bitset& __b) const 1238 { return this->_M_is_subset_of(__b); } 1239 1240 bool 1241 is_proper_subset_of(const dynamic_bitset& __b) const 1242 { return this->_M_is_proper_subset_of(__b); } 1243 }; 1244 1245 // Definitions of non-inline member functions. 1246 template<typename _WordT, typename _Alloc> 1247 template<typename _CharT, typename _Traits> 1248 void 1249 dynamic_bitset<_WordT, _Alloc>:: 1250 _M_copy_from_ptr(const _CharT* __str, size_t __len, 1251 size_t __pos, size_t __n, _CharT __zero, _CharT __one) 1252 { 1253 reset(); 1254 const size_t __nbits = std::min(_M_Nb, std::min(__n, __len - __pos)); 1255 for (size_t __i = __nbits; __i > 0; --__i) 1256 { 1257 const _CharT __c = __str[__pos + __nbits - __i]; 1258 if (_Traits::eq(__c, __zero)) 1259 ; 1260 else if (_Traits::eq(__c, __one)) 1261 _M_unchecked_set(__i - 1); 1262 else 1263 __throw_invalid_argument(__N("dynamic_bitset::_M_copy_from_ptr")); 1264 } 1265 } 1266 1267 template<typename _WordT, typename _Alloc> 1268 template<typename _CharT, typename _Traits, typename _Alloc1> 1269 void 1270 dynamic_bitset<_WordT, _Alloc>:: 1271 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str, 1272 _CharT __zero, _CharT __one) const 1273 { 1274 __str.assign(_M_Nb, __zero); 1275 for (size_t __i = _M_Nb; __i > 0; --__i) 1276 if (_M_unchecked_test(__i - 1)) 1277 _Traits::assign(__str[_M_Nb - __i], __one); 1278 } 1279 1280 1281 //@{ 1282 /// These comparisons for equality/inequality are, well, @e bitwise. 1283 template<typename _WordT, typename _Alloc> 1284 bool 1285 operator==(const dynamic_bitset<_WordT, _Alloc>& __lhs, 1286 const dynamic_bitset<_WordT, _Alloc>& __rhs) 1287 { return __lhs._M_is_equal(__rhs); } 1288 1289 template<typename _WordT, typename _Alloc> 1290 bool 1291 operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs, 1292 const dynamic_bitset<_WordT, _Alloc>& __rhs) 1293 { return !__lhs._M_is_equal(__rhs); } 1294 1295 template<typename _WordT, typename _Alloc> 1296 bool 1297 operator<(const dynamic_bitset<_WordT, _Alloc>& __lhs, 1298 const dynamic_bitset<_WordT, _Alloc>& __rhs) 1299 { return __lhs._M_is_less(__rhs); } 1300 1301 template<typename _WordT, typename _Alloc> 1302 bool 1303 operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs, 1304 const dynamic_bitset<_WordT, _Alloc>& __rhs) 1305 { return !(__lhs > __rhs); } 1306 1307 template<typename _WordT, typename _Alloc> 1308 bool 1309 operator>(const dynamic_bitset<_WordT, _Alloc>& __lhs, 1310 const dynamic_bitset<_WordT, _Alloc>& __rhs) 1311 { return __rhs < __lhs; } 1312 1313 template<typename _WordT, typename _Alloc> 1314 bool 1315 operator>=(const dynamic_bitset<_WordT, _Alloc>& __lhs, 1316 const dynamic_bitset<_WordT, _Alloc>& __rhs) 1317 { return !(__lhs < __rhs); } 1318 //@} 1319 1320 // 23.3.5.3 bitset operations: 1321 //@{ 1322 /** 1323 * @brief Global bitwise operations on bitsets. 1324 * @param __x A bitset. 1325 * @param __y A bitset of the same size as @a __x. 1326 * @return A new bitset. 1327 * 1328 * These should be self-explanatory. 1329 */ 1330 template<typename _WordT, typename _Alloc> 1331 inline dynamic_bitset<_WordT, _Alloc> 1332 operator&(const dynamic_bitset<_WordT, _Alloc>& __x, 1333 const dynamic_bitset<_WordT, _Alloc>& __y) 1334 { 1335 dynamic_bitset<_WordT, _Alloc> __result(__x); 1336 __result &= __y; 1337 return __result; 1338 } 1339 1340 template<typename _WordT, typename _Alloc> 1341 inline dynamic_bitset<_WordT, _Alloc> 1342 operator|(const dynamic_bitset<_WordT, _Alloc>& __x, 1343 const dynamic_bitset<_WordT, _Alloc>& __y) 1344 { 1345 dynamic_bitset<_WordT, _Alloc> __result(__x); 1346 __result |= __y; 1347 return __result; 1348 } 1349 1350 template <typename _WordT, typename _Alloc> 1351 inline dynamic_bitset<_WordT, _Alloc> 1352 operator^(const dynamic_bitset<_WordT, _Alloc>& __x, 1353 const dynamic_bitset<_WordT, _Alloc>& __y) 1354 { 1355 dynamic_bitset<_WordT, _Alloc> __result(__x); 1356 __result ^= __y; 1357 return __result; 1358 } 1359 1360 template <typename _WordT, typename _Alloc> 1361 inline dynamic_bitset<_WordT, _Alloc> 1362 operator-(const dynamic_bitset<_WordT, _Alloc>& __x, 1363 const dynamic_bitset<_WordT, _Alloc>& __y) 1364 { 1365 dynamic_bitset<_WordT, _Alloc> __result(__x); 1366 __result -= __y; 1367 return __result; 1368 } 1369 //@} 1370 1371 //@{ 1372 /** 1373 * @brief Global I/O operators for bitsets. 1374 * 1375 * Direct I/O between streams and bitsets is supported. Output is 1376 * straightforward. Input will skip whitespace and only accept '0' 1377 * and '1' characters. The %dynamic_bitset will grow as necessary 1378 * to hold the string of bits. 1379 */ 1380 template<typename _CharT, typename _Traits, 1381 typename _WordT, typename _Alloc> 1382 std::basic_istream<_CharT, _Traits>& 1383 operator>>(std::basic_istream<_CharT, _Traits>& __is, 1384 dynamic_bitset<_WordT, _Alloc>& __x) 1385 { 1386 typedef typename _Traits::char_type char_type; 1387 typedef std::basic_istream<_CharT, _Traits> __istream_type; 1388 typedef typename __istream_type::ios_base __ios_base; 1389 1390 std::basic_string<_CharT, _Traits> __tmp; 1391 __tmp.reserve(__x.size()); 1392 1393 const char_type __zero = __is.widen('0'); 1394 const char_type __one = __is.widen('1'); 1395 1396 typename __ios_base::iostate __state = __ios_base::goodbit; 1397 typename __istream_type::sentry __sentry(__is); 1398 if (__sentry) 1399 { 1400 __try 1401 { 1402 while (1) 1403 { 1404 static typename _Traits::int_type __eof = _Traits::eof(); 1405 1406 typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc(); 1407 if (_Traits::eq_int_type(__c1, __eof)) 1408 { 1409 __state |= __ios_base::eofbit; 1410 break; 1411 } 1412 else 1413 { 1414 const char_type __c2 = _Traits::to_char_type(__c1); 1415 if (_Traits::eq(__c2, __zero)) 1416 __tmp.push_back(__zero); 1417 else if (_Traits::eq(__c2, __one)) 1418 __tmp.push_back(__one); 1419 else if (_Traits:: 1420 eq_int_type(__is.rdbuf()->sputbackc(__c2), 1421 __eof)) 1422 { 1423 __state |= __ios_base::failbit; 1424 break; 1425 } 1426 else 1427 break; 1428 } 1429 } 1430 } 1431 __catch(__cxxabiv1::__forced_unwind&) 1432 { 1433 __is._M_setstate(__ios_base::badbit); 1434 __throw_exception_again; 1435 } 1436 __catch(...) 1437 { __is._M_setstate(__ios_base::badbit); } 1438 } 1439 1440 __x.resize(__tmp.size()); 1441 1442 if (__tmp.empty() && __x.size()) 1443 __state |= __ios_base::failbit; 1444 else 1445 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), __x.size(), 1446 __zero, __one); 1447 if (__state) 1448 __is.setstate(__state); 1449 return __is; 1450 } 1451 1452 template <typename _CharT, typename _Traits, 1453 typename _WordT, typename _Alloc> 1454 std::basic_ostream<_CharT, _Traits>& 1455 operator<<(std::basic_ostream<_CharT, _Traits>& __os, 1456 const dynamic_bitset<_WordT, _Alloc>& __x) 1457 { 1458 std::basic_string<_CharT, _Traits> __tmp; 1459 1460 const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc()); 1461 __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1')); 1462 return __os << __tmp; 1463 } 1464 //@} 1465 1466_GLIBCXX_END_NAMESPACE_VERSION 1467} // tr2 1468} // std 1469 1470#undef _GLIBCXX_BITSET_BITS_PER_WORD 1471 1472#endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */ 1473