1// TR2 <dynamic_bitset> -*- C++ -*- 2 3// Copyright (C) 2009, 2010, 2011 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 <cstddef> // For size_t 37#include <string> 38#include <memory> // For std::allocator 39#include <bits/functexcept.h> // For invalid_argument, out_of_range, 40 // overflow_error 41#include <iosfwd> 42#include <cxxabi_forced.h> 43 44namespace std _GLIBCXX_VISIBILITY(default) 45{ 46namespace tr2 47{ 48_GLIBCXX_BEGIN_NAMESPACE_VERSION 49 50 /** 51 * Dynamic Bitset. 52 * 53 * See N2050, 54 * Proposal to Add a Dynamically Sizeable Bitset to the Standard Library. 55 */ 56namespace __detail 57{ 58 59template<typename T> 60class _Bool2UChar 61{ 62 typedef T type; 63}; 64 65template<> 66class _Bool2UChar<bool> 67{ 68public: 69 typedef unsigned char type; 70}; 71 72} 73 74 /** 75 * Base class, general case. 76 * 77 * See documentation for dynamic_bitset. 78 */ 79 template<typename _WordT = unsigned long long, 80 typename _Alloc = std::allocator<_WordT>> 81 struct __dynamic_bitset_base 82 { 83 static_assert(std::is_unsigned<_WordT>::value, "template argument " 84 "_WordT not an unsigned integral type"); 85 86 typedef _WordT block_type; 87 typedef _Alloc allocator_type; 88 typedef size_t size_type; 89 90 static const size_type _S_bits_per_block = __CHAR_BIT__ * sizeof(block_type); 91 static const size_type npos = static_cast<size_type>(-1); 92 93 /// 0 is the least significant word. 94 std::vector<block_type, allocator_type> _M_w; 95 96 explicit 97 __dynamic_bitset_base(const allocator_type& __alloc = allocator_type()) 98 : _M_w(__alloc) 99 { } 100 101 explicit 102 __dynamic_bitset_base(__dynamic_bitset_base&& __b) 103 { this->_M_w.swap(__b._M_w); } 104 105 explicit 106 __dynamic_bitset_base(size_type __nbits, unsigned long long __val = 0ULL, 107 const allocator_type& __alloc = allocator_type()) 108 : _M_w(__nbits / _S_bits_per_block 109 + (__nbits % _S_bits_per_block > 0), 110 __val, __alloc) 111 { 112 unsigned long long __mask = ~static_cast<block_type>(0); 113 size_t __n = std::min(this->_M_w.size(), 114 sizeof(unsigned long long) / sizeof(block_type)); 115 for (size_t __i = 0; __i < __n; ++__i) 116 { 117 this->_M_w[__i] = (__val & __mask) >> (__i * _S_bits_per_block); 118 __mask <<= _S_bits_per_block; 119 } 120 } 121 122 void 123 _M_assign(const __dynamic_bitset_base& __b) 124 { this->_M_w = __b._M_w; } 125 126 void 127 _M_swap(__dynamic_bitset_base& __b) 128 { this->_M_w.swap(__b._M_w); } 129 130 void 131 _M_clear() 132 { this->_M_w.clear(); } 133 134 void 135 _M_resize(size_t __nbits, bool __value) 136 { 137 size_t __sz = __nbits / _S_bits_per_block; 138 if (__nbits % _S_bits_per_block > 0) 139 ++__sz; 140 if (__sz != this->_M_w.size()) 141 this->_M_w.resize(__sz); 142 } 143 144 allocator_type 145 _M_get_allocator() const 146 { return this->_M_w.get_allocator(); } 147 148 static size_type 149 _S_whichword(size_type __pos) 150 { return __pos / _S_bits_per_block; } 151 152 static size_type 153 _S_whichbyte(size_type __pos) 154 { return (__pos % _S_bits_per_block) / __CHAR_BIT__; } 155 156 static size_type 157 _S_whichbit(size_type __pos) 158 { return __pos % _S_bits_per_block; } 159 160 static block_type 161 _S_maskbit(size_type __pos) 162 { return (static_cast<block_type>(1)) << _S_whichbit(__pos); } 163 164 block_type& 165 _M_getword(size_type __pos) 166 { return this->_M_w[_S_whichword(__pos)]; } 167 168 block_type 169 _M_getword(size_type __pos) const 170 { return this->_M_w[_S_whichword(__pos)]; } 171 172 block_type& 173 _M_hiword() 174 { return this->_M_w[_M_w.size() - 1]; } 175 176 block_type 177 _M_hiword() const 178 { return this->_M_w[_M_w.size() - 1]; } 179 180 void 181 _M_do_and(const __dynamic_bitset_base& __x) 182 { 183 if (__x._M_w.size() == this->_M_w.size()) 184 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 185 this->_M_w[__i] &= __x._M_w[__i]; 186 else 187 return; 188 } 189 190 void 191 _M_do_or(const __dynamic_bitset_base& __x) 192 { 193 if (__x._M_w.size() == this->_M_w.size()) 194 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 195 this->_M_w[__i] |= __x._M_w[__i]; 196 else 197 return; 198 } 199 200 void 201 _M_do_xor(const __dynamic_bitset_base& __x) 202 { 203 if (__x._M_w.size() == this->_M_w.size()) 204 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 205 this->_M_w[__i] ^= __x._M_w[__i]; 206 else 207 return; 208 } 209 210 void 211 _M_do_dif(const __dynamic_bitset_base& __x) 212 { 213 if (__x._M_w.size() == this->_M_w.size()) 214 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 215 this->_M_w[__i] &= ~__x._M_w[__i]; 216 else 217 return; 218 } 219 220 void 221 _M_do_left_shift(size_t __shift); 222 223 void 224 _M_do_right_shift(size_t __shift); 225 226 void 227 _M_do_flip() 228 { 229 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 230 this->_M_w[__i] = ~this->_M_w[__i]; 231 } 232 233 void 234 _M_do_set() 235 { 236 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 237 this->_M_w[__i] = ~static_cast<block_type>(0); 238 } 239 240 void 241 _M_do_reset() 242 { 243 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 244 this->_M_w[__i] = static_cast<block_type>(0); 245 } 246 247 bool 248 _M_is_equal(const __dynamic_bitset_base& __x) const 249 { 250 if (__x.size() == this->size()) 251 { 252 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 253 if (this->_M_w[__i] != __x._M_w[__i]) 254 return false; 255 return true; 256 } 257 else 258 return false; 259 } 260 261 bool 262 _M_is_less(const __dynamic_bitset_base& __x) const 263 { 264 if (__x.size() == this->size()) 265 { 266 for (size_t __i = this->_M_w.size(); __i > 0; --__i) 267 { 268 if (this->_M_w[__i-1] < __x._M_w[__i-1]) 269 return true; 270 else if (this->_M_w[__i-1] > __x._M_w[__i-1]) 271 return false; 272 } 273 return false; 274 } 275 else 276 return false; 277 } 278 279 size_t 280 _M_are_all_aux() const 281 { 282 for (size_t __i = 0; __i < this->_M_w.size() - 1; ++__i) 283 if (_M_w[__i] != ~static_cast<block_type>(0)) 284 return 0; 285 return ((this->_M_w.size() - 1) * _S_bits_per_block 286 + __builtin_popcountl(this->_M_hiword())); 287 } 288 289 bool 290 _M_is_any() const 291 { 292 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 293 if (this->_M_w[__i] != static_cast<block_type>(0)) 294 return true; 295 return false; 296 } 297 298 bool 299 _M_is_subset_of(const __dynamic_bitset_base& __b) 300 { 301 if (__b.size() == this->size()) 302 { 303 for (size_t __i = 0; __i < _M_w.size(); ++__i) 304 if (this->_M_w[__i] != (this->_M_w[__i] | __b._M_w[__i])) 305 return false; 306 return true; 307 } 308 else 309 return false; 310 } 311 312 bool 313 _M_is_proper_subset_of(const __dynamic_bitset_base& __b) const 314 { 315 if (this->is_subset_of(__b)) 316 { 317 if (*this == __b) 318 return false; 319 else 320 return true; 321 } 322 else 323 return false; 324 } 325 326 size_t 327 _M_do_count() const 328 { 329 size_t __result = 0; 330 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 331 __result += __builtin_popcountl(this->_M_w[__i]); 332 return __result; 333 } 334 335 size_type 336 _M_size() const 337 { return this->_M_w.size(); } 338 339 unsigned long 340 _M_do_to_ulong() const; 341 342 unsigned long long 343 _M_do_to_ullong() const; 344 345 // find first "on" bit 346 size_type 347 _M_do_find_first(size_t __not_found) const; 348 349 // find the next "on" bit that follows "prev" 350 size_type 351 _M_do_find_next(size_t __prev, size_t __not_found) const; 352 353 // do append of block 354 void 355 _M_do_append_block(block_type __block, size_type __pos) 356 { 357 size_t __offset = __pos % _S_bits_per_block; 358 if (__offset == 0) 359 this->_M_w.push_back(__block); 360 else 361 { 362 this->_M_hiword() |= (__block << __offset); 363 this->_M_w.push_back(__block >> (_S_bits_per_block - __offset)); 364 } 365 } 366 }; 367 368 // Definitions of non-inline functions from __dynamic_bitset_base. 369 template<typename _WordT, typename _Alloc> 370 void 371 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_left_shift(size_t __shift) 372 { 373 if (__builtin_expect(__shift != 0, 1)) 374 { 375 const size_t __wshift = __shift / _S_bits_per_block; 376 const size_t __offset = __shift % _S_bits_per_block; 377 378 if (__offset == 0) 379 for (size_t __n = this->_M_w.size() - 1; __n >= __wshift; --__n) 380 this->_M_w[__n] = this->_M_w[__n - __wshift]; 381 else 382 { 383 const size_t __sub_offset = _S_bits_per_block - __offset; 384 for (size_t __n = _M_w.size() - 1; __n > __wshift; --__n) 385 this->_M_w[__n] = ((this->_M_w[__n - __wshift] << __offset) 386 | (this->_M_w[__n - __wshift - 1] >> __sub_offset)); 387 this->_M_w[__wshift] = this->_M_w[0] << __offset; 388 } 389 390 //// std::fill(this->_M_w.begin(), this->_M_w.begin() + __wshift, 391 //// static_cast<_WordT>(0)); 392 } 393 } 394 395 template<typename _WordT, typename _Alloc> 396 void 397 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_right_shift(size_t __shift) 398 { 399 if (__builtin_expect(__shift != 0, 1)) 400 { 401 const size_t __wshift = __shift / _S_bits_per_block; 402 const size_t __offset = __shift % _S_bits_per_block; 403 const size_t __limit = this->_M_w.size() - __wshift - 1; 404 405 if (__offset == 0) 406 for (size_t __n = 0; __n <= __limit; ++__n) 407 this->_M_w[__n] = this->_M_w[__n + __wshift]; 408 else 409 { 410 const size_t __sub_offset = (_S_bits_per_block 411 - __offset); 412 for (size_t __n = 0; __n < __limit; ++__n) 413 this->_M_w[__n] = ((this->_M_w[__n + __wshift] >> __offset) 414 | (this->_M_w[__n + __wshift + 1] << __sub_offset)); 415 this->_M_w[__limit] = this->_M_w[_M_w.size()-1] >> __offset; 416 } 417 418 ////std::fill(this->_M_w.begin() + __limit + 1, this->_M_w.end(), 419 //// static_cast<_WordT>(0)); 420 } 421 } 422 423 template<typename _WordT, typename _Alloc> 424 unsigned long 425 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ulong() const 426 { 427 size_t __n = sizeof(unsigned long) / sizeof(block_type); 428 for (size_t __i = __n; __i < this->_M_w.size(); ++__i) 429 if (this->_M_w[__i]) 430 __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ulong")); 431 unsigned long __res = 0UL; 432 for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i) 433 __res += this->_M_w[__i] << (__i * _S_bits_per_block); 434 return __res; 435 } 436 437 template<typename _WordT, typename _Alloc> 438 unsigned long long 439 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ullong() const 440 { 441 size_t __n = sizeof(unsigned long long) / sizeof(block_type); 442 for (size_t __i = __n; __i < this->_M_w.size(); ++__i) 443 if (this->_M_w[__i]) 444 __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ullong")); 445 unsigned long long __res = 0ULL; 446 for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i) 447 __res += this->_M_w[__i] << (__i * _S_bits_per_block); 448 return __res; 449 } 450 451 template<typename _WordT, typename _Alloc> 452 size_t 453 __dynamic_bitset_base<_WordT, _Alloc> 454 ::_M_do_find_first(size_t __not_found) const 455 { 456 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 457 { 458 _WordT __thisword = this->_M_w[__i]; 459 if (__thisword != static_cast<_WordT>(0)) 460 return (__i * _S_bits_per_block 461 + __builtin_ctzl(__thisword)); 462 } 463 // not found, so return an indication of failure. 464 return __not_found; 465 } 466 467 template<typename _WordT, typename _Alloc> 468 size_t 469 __dynamic_bitset_base<_WordT, _Alloc> 470 ::_M_do_find_next(size_t __prev, size_t __not_found) const 471 { 472 // make bound inclusive 473 ++__prev; 474 475 // check out of bounds 476 if (__prev >= this->_M_w.size() * _S_bits_per_block) 477 return __not_found; 478 479 // search first word 480 size_t __i = _S_whichword(__prev); 481 _WordT __thisword = this->_M_w[__i]; 482 483 // mask off bits below bound 484 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev); 485 486 if (__thisword != static_cast<_WordT>(0)) 487 return (__i * _S_bits_per_block 488 + __builtin_ctzl(__thisword)); 489 490 // check subsequent words 491 for (++__i; __i < this->_M_w.size(); ++__i) 492 { 493 __thisword = this->_M_w[__i]; 494 if (__thisword != static_cast<_WordT>(0)) 495 return (__i * _S_bits_per_block 496 + __builtin_ctzl(__thisword)); 497 } 498 // not found, so return an indication of failure. 499 return __not_found; 500 } // end _M_do_find_next 501 502 /** 503 * @brief The %dynamic_bitset class represents a sequence of bits. 504 * 505 * @ingroup containers 506 * 507 * (Note that %dynamic_bitset does @e not meet the formal 508 * requirements of a <a href="tables.html#65">container</a>. 509 * Mainly, it lacks iterators.) 510 * 511 * The template argument, @a Nb, may be any non-negative number, 512 * specifying the number of bits (e.g., "0", "12", "1024*1024"). 513 * 514 * In the general unoptimized case, storage is allocated in 515 * word-sized blocks. Let B be the number of bits in a word, then 516 * (Nb+(B-1))/B words will be used for storage. B - Nb%B bits are 517 * unused. (They are the high-order bits in the highest word.) It 518 * is a class invariant that those unused bits are always zero. 519 * 520 * If you think of %dynamic_bitset as "a simple array of bits," be 521 * aware that your mental picture is reversed: a %dynamic_bitset 522 * behaves the same way as bits in integers do, with the bit at 523 * index 0 in the "least significant / right-hand" position, and 524 * the bit at index Nb-1 in the "most significant / left-hand" 525 * position. Thus, unlike other containers, a %dynamic_bitset's 526 * index "counts from right to left," to put it very loosely. 527 * 528 * This behavior is preserved when translating to and from strings. 529 * For example, the first line of the following program probably 530 * prints "b('a') is 0001100001" on a modern ASCII system. 531 * 532 * @code 533 * #include <dynamic_bitset> 534 * #include <iostream> 535 * #include <sstream> 536 * 537 * using namespace std; 538 * 539 * int main() 540 * { 541 * long a = 'a'; 542 * dynamic_bitset b(a); 543 * 544 * cout << "b('a') is " << b << endl; 545 * 546 * ostringstream s; 547 * s << b; 548 * string str = s.str(); 549 * cout << "index 3 in the string is " << str[3] << " but\n" 550 * << "index 3 in the bitset is " << b[3] << endl; 551 * } 552 * @endcode 553 * 554 * Also see: 555 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch33s02.html 556 * for a description of extensions. 557 * 558 * Most of the actual code isn't contained in %dynamic_bitset<> 559 * itself, but in the base class __dynamic_bitset_base. The base 560 * class works with whole words, not with individual bits. This 561 * allows us to specialize __dynamic_bitset_base for the important 562 * special case where the %dynamic_bitset is only a single word. 563 * 564 * Extra confusion can result due to the fact that the storage for 565 * __dynamic_bitset_base @e is a vector, and is indexed as such. This is 566 * carefully encapsulated. 567 */ 568 template<typename _WordT = unsigned long long, 569 typename _Alloc = std::allocator<_WordT>> 570 class dynamic_bitset 571 : private __dynamic_bitset_base<_WordT, _Alloc> 572 { 573 static_assert(std::is_unsigned<_WordT>::value, "template argument " 574 "_WordT not an unsigned integral type"); 575 576 public: 577 578 typedef __dynamic_bitset_base<_WordT, _Alloc> _Base; 579 typedef _WordT block_type; 580 typedef _Alloc allocator_type; 581 typedef size_t size_type; 582 583 static const size_type bits_per_block = __CHAR_BIT__ * sizeof(block_type); 584 // Use this: constexpr size_type std::numeric_limits<size_type>::max(). 585 static const size_type npos = static_cast<size_type>(-1); 586 587 private: 588 589 // Clear the unused bits in the uppermost word. 590 void 591 _M_do_sanitize() 592 { 593 size_type __shift = this->_M_Nb % bits_per_block; 594 if (__shift > 0) 595 this->_M_hiword() &= ~((~static_cast<block_type>(0)) << __shift); 596 } 597 598 /** 599 * These versions of single-bit set, reset, flip, and test 600 * do no range checking. 601 */ 602 dynamic_bitset<_WordT, _Alloc>& 603 _M_unchecked_set(size_type __pos) 604 { 605 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 606 return *this; 607 } 608 609 dynamic_bitset<_WordT, _Alloc>& 610 _M_unchecked_set(size_type __pos, int __val) 611 { 612 if (__val) 613 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 614 else 615 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 616 return *this; 617 } 618 619 dynamic_bitset<_WordT, _Alloc>& 620 _M_unchecked_reset(size_type __pos) 621 { 622 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 623 return *this; 624 } 625 626 dynamic_bitset<_WordT, _Alloc>& 627 _M_unchecked_flip(size_type __pos) 628 { 629 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); 630 return *this; 631 } 632 633 bool 634 _M_unchecked_test(size_type __pos) const 635 { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) 636 != static_cast<_WordT>(0)); } 637 638 size_type _M_Nb; 639 640 public: 641 /** 642 * This encapsulates the concept of a single bit. An instance 643 * of this class is a proxy for an actual bit; this way the 644 * individual bit operations are done as faster word-size 645 * bitwise instructions. 646 * 647 * Most users will never need to use this class directly; 648 * conversions to and from bool are automatic and should be 649 * transparent. Overloaded operators help to preserve the 650 * illusion. 651 * 652 * (On a typical system, this "bit %reference" is 64 times the 653 * size of an actual bit. Ha.) 654 */ 655 class reference 656 { 657 friend class dynamic_bitset; 658 659 block_type *_M_wp; 660 size_type _M_bpos; 661 662 // left undefined 663 reference(); 664 665 public: 666 reference(dynamic_bitset& __b, size_type __pos) 667 { 668 this->_M_wp = &__b._M_getword(__pos); 669 this->_M_bpos = _Base::_S_whichbit(__pos); 670 } 671 672 ~reference() 673 { } 674 675 // For b[i] = __x; 676 reference& 677 operator=(bool __x) 678 { 679 if (__x) 680 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos); 681 else 682 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos); 683 return *this; 684 } 685 686 // For b[i] = b[__j]; 687 reference& 688 operator=(const reference& __j) 689 { 690 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos))) 691 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos); 692 else 693 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos); 694 return *this; 695 } 696 697 // Flips the bit 698 bool 699 operator~() const 700 { return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; } 701 702 // For __x = b[i]; 703 operator bool() const 704 { return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; } 705 706 // For b[i].flip(); 707 reference& 708 flip() 709 { 710 *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos); 711 return *this; 712 } 713 }; 714 715 friend class reference; 716 717 typedef bool const_reference; 718 719 // 23.3.5.1 constructors: 720 /// All bits set to zero. 721 explicit 722 dynamic_bitset(const allocator_type& __alloc = allocator_type()) 723 : _Base(__alloc), _M_Nb(0) 724 { } 725 726 /// Initial bits bitwise-copied from a single word (others set to zero). 727 explicit 728 dynamic_bitset(size_type __nbits, unsigned long long __val = 0ULL, 729 const allocator_type& __alloc = allocator_type()) 730 : _Base(__nbits, __val, __alloc), 731 _M_Nb(__nbits) 732 { } 733 734 dynamic_bitset(initializer_list<block_type> __il, 735 const allocator_type& __alloc = allocator_type()) 736 : _Base(__alloc), _M_Nb(0) 737 { this->append(__il); } 738 739 /** 740 * @brief Use a subset of a string. 741 * @param __str A string of '0' and '1' characters. 742 * @param __pos Index of the first character in @p __str to use. 743 * @param __n The number of characters to copy. 744 * @throw std::out_of_range If @p __pos is bigger the size of @p __str. 745 * @throw std::invalid_argument If a character appears in the string 746 * which is neither '0' nor '1'. 747 */ 748 template<typename _CharT, typename _Traits, typename _Alloc1> 749 explicit 750 dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc1>& __str, 751 typename basic_string<_CharT,_Traits,_Alloc1>::size_type 752 __pos = 0, 753 typename basic_string<_CharT,_Traits,_Alloc1>::size_type 754 __n = std::basic_string<_CharT, _Traits, _Alloc1>::npos, 755 _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'), 756 const allocator_type& __alloc = allocator_type()) 757 : _Base(__alloc), 758 _M_Nb(0) // Watch for npos. 759 { 760 if (__pos > __str.size()) 761 __throw_out_of_range(__N("dynamic_bitset::bitset initial position " 762 "not valid")); 763 764 // Watch for npos. 765 this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n); 766 this->resize(this->_M_Nb); 767 this->_M_copy_from_string(__str, __pos, __n, 768 _CharT('0'), _CharT('1')); 769 } 770 771 /** 772 * @brief Construct from a string. 773 * @param __str A string of '0' and '1' characters. 774 * @throw std::invalid_argument If a character appears in the string 775 * which is neither '0' nor '1'. 776 */ 777 explicit 778 dynamic_bitset(const char* __str, 779 const allocator_type& __alloc = allocator_type()) 780 : _Base(__alloc) 781 { 782 size_t __len = 0; 783 if (__str) 784 while (__str[__len] != '\0') 785 ++__len; 786 this->resize(__len); 787 this->_M_copy_from_ptr<char,std::char_traits<char>> 788 (__str, __len, 0, __len, '0', '1'); 789 } 790 791 /** 792 * @brief Copy constructor. 793 */ 794 dynamic_bitset(const dynamic_bitset& __b) 795 : _Base(__b), _M_Nb(__b.size()) 796 { } 797 798 /** 799 * @brief Move constructor. 800 */ 801 dynamic_bitset(dynamic_bitset&& __b) 802 : _Base(std::forward<_Base>(__b)), _M_Nb(__b.size()) 803 { } 804 805 /** 806 * @brief Swap with another bitset. 807 */ 808 void 809 swap(dynamic_bitset& __b) 810 { 811 this->_M_swap(__b); 812 std::swap(this->_M_Nb, __b._M_Nb); 813 } 814 815 /** 816 * @brief Assignment. 817 */ 818 dynamic_bitset& 819 operator=(const dynamic_bitset& __b) 820 { 821 if (&__b != this) 822 { 823 this->_M_assign(__b); 824 this->_M_Nb = __b._M_Nb; 825 } 826 } 827 828 /** 829 * @brief Move assignment. 830 */ 831 dynamic_bitset& 832 operator=(dynamic_bitset&& __b) 833 { 834 this->swap(__b); 835 return *this; 836 } 837 838 /** 839 * @brief Return the allocator for the bitset. 840 */ 841 allocator_type 842 get_allocator() const 843 { return this->_M_get_allocator(); } 844 845 /** 846 * @brief Resize the bitset. 847 */ 848 void 849 resize(size_type __nbits, bool __value = false) 850 { 851 this->_M_resize(__nbits, __value); 852 this->_M_Nb = __nbits; 853 this->_M_do_sanitize(); 854 } 855 856 /** 857 * @brief Clear the bitset. 858 */ 859 void 860 clear() 861 { 862 this->_M_clear(); 863 this->_M_Nb = 0; 864 } 865 866 /** 867 * @brief Push a bit onto the high end of the bitset. 868 */ 869 void 870 push_back(bool __bit) 871 { 872 if (size_t __offset = this->size() % bits_per_block == 0) 873 this->_M_do_append_block(block_type(0), this->_M_Nb); 874 ++this->_M_Nb; 875 this->_M_unchecked_set(this->_M_Nb, __bit); 876 } 877 878 /** 879 * @brief Append a block. 880 */ 881 void 882 append(block_type __block) 883 { 884 this->_M_do_append_block(__block, this->_M_Nb); 885 this->_M_Nb += bits_per_block; 886 } 887 888 /** 889 * @brief 890 */ 891 void 892 append(initializer_list<block_type> __il) 893 { this->append(__il.begin(), __il.end()); } 894 895 /** 896 * @brief Append an iterator range of blocks. 897 */ 898 template <typename _BlockInputIterator> 899 void 900 append(_BlockInputIterator __first, _BlockInputIterator __last) 901 { 902 for (; __first != __last; ++__first) 903 this->append(*__first); 904 } 905 906 // 23.3.5.2 dynamic_bitset operations: 907 //@{ 908 /** 909 * @brief Operations on dynamic_bitsets. 910 * @param __rhs A same-sized dynamic_bitset. 911 * 912 * These should be self-explanatory. 913 */ 914 dynamic_bitset<_WordT, _Alloc>& 915 operator&=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 916 { 917 this->_M_do_and(__rhs); 918 return *this; 919 } 920 921 dynamic_bitset<_WordT, _Alloc>& 922 operator&=(dynamic_bitset<_WordT, _Alloc>&& __rhs) 923 { 924 this->_M_do_and(std::move(__rhs)); 925 return *this; 926 } 927 928 dynamic_bitset<_WordT, _Alloc>& 929 operator|=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 930 { 931 this->_M_do_or(__rhs); 932 return *this; 933 } 934 935 dynamic_bitset<_WordT, _Alloc>& 936 operator^=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 937 { 938 this->_M_do_xor(__rhs); 939 return *this; 940 } 941 942 dynamic_bitset<_WordT, _Alloc>& 943 operator-=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 944 { 945 this->_M_do_dif(__rhs); 946 return *this; 947 } 948 //@} 949 950 //@{ 951 /** 952 * @brief Operations on dynamic_bitsets. 953 * @param __pos The number of places to shift. 954 * 955 * These should be self-explanatory. 956 */ 957 dynamic_bitset<_WordT, _Alloc>& 958 operator<<=(size_type __pos) 959 { 960 if (__builtin_expect(__pos < this->_M_Nb, 1)) 961 { 962 this->_M_do_left_shift(__pos); 963 this->_M_do_sanitize(); 964 } 965 else 966 this->_M_do_reset(); 967 return *this; 968 } 969 970 dynamic_bitset<_WordT, _Alloc>& 971 operator>>=(size_type __pos) 972 { 973 if (__builtin_expect(__pos < this->_M_Nb, 1)) 974 { 975 this->_M_do_right_shift(__pos); 976 this->_M_do_sanitize(); 977 } 978 else 979 this->_M_do_reset(); 980 return *this; 981 } 982 //@} 983 984 // Set, reset, and flip. 985 /** 986 * @brief Sets every bit to true. 987 */ 988 dynamic_bitset<_WordT, _Alloc>& 989 set() 990 { 991 this->_M_do_set(); 992 this->_M_do_sanitize(); 993 return *this; 994 } 995 996 /** 997 * @brief Sets a given bit to a particular value. 998 * @param __pos The index of the bit. 999 * @param __val Either true or false, defaults to true. 1000 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 1001 */ 1002 dynamic_bitset<_WordT, _Alloc>& 1003 set(size_type __pos, bool __val = true) 1004 { 1005 if (__pos >= _M_Nb) 1006 __throw_out_of_range(__N("dynamic_bitset::set")); 1007 return this->_M_unchecked_set(__pos, __val); 1008 } 1009 1010 /** 1011 * @brief Sets every bit to false. 1012 */ 1013 dynamic_bitset<_WordT, _Alloc>& 1014 reset() 1015 { 1016 this->_M_do_reset(); 1017 return *this; 1018 } 1019 1020 /** 1021 * @brief Sets a given bit to false. 1022 * @param __pos The index of the bit. 1023 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 1024 * 1025 * Same as writing @c set(__pos, false). 1026 */ 1027 dynamic_bitset<_WordT, _Alloc>& 1028 reset(size_type __pos) 1029 { 1030 if (__pos >= _M_Nb) 1031 __throw_out_of_range(__N("dynamic_bitset::reset")); 1032 return this->_M_unchecked_reset(__pos); 1033 } 1034 1035 /** 1036 * @brief Toggles every bit to its opposite value. 1037 */ 1038 dynamic_bitset<_WordT, _Alloc>& 1039 flip() 1040 { 1041 this->_M_do_flip(); 1042 this->_M_do_sanitize(); 1043 return *this; 1044 } 1045 1046 /** 1047 * @brief Toggles a given bit to its opposite value. 1048 * @param __pos The index of the bit. 1049 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 1050 */ 1051 dynamic_bitset<_WordT, _Alloc>& 1052 flip(size_type __pos) 1053 { 1054 if (__pos >= _M_Nb) 1055 __throw_out_of_range(__N("dynamic_bitset::flip")); 1056 return this->_M_unchecked_flip(__pos); 1057 } 1058 1059 /// See the no-argument flip(). 1060 dynamic_bitset<_WordT, _Alloc> 1061 operator~() const 1062 { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); } 1063 1064 //@{ 1065 /** 1066 * @brief Array-indexing support. 1067 * @param __pos Index into the %dynamic_bitset. 1068 * @return A bool for a 'const %dynamic_bitset'. For non-const 1069 * bitsets, an instance of the reference proxy class. 1070 * @note These operators do no range checking and throw no 1071 * exceptions, as required by DR 11 to the standard. 1072 */ 1073 reference 1074 operator[](size_type __pos) 1075 { return reference(*this,__pos); } 1076 1077 const_reference 1078 operator[](size_type __pos) const 1079 { return _M_unchecked_test(__pos); } 1080 //@} 1081 1082 /** 1083 * @brief Returns a numerical interpretation of the %dynamic_bitset. 1084 * @return The integral equivalent of the bits. 1085 * @throw std::overflow_error If there are too many bits to be 1086 * represented in an @c unsigned @c long. 1087 */ 1088 unsigned long 1089 to_ulong() const 1090 { return this->_M_do_to_ulong(); } 1091 1092 /** 1093 * @brief Returns a numerical interpretation of the %dynamic_bitset. 1094 * @return The integral equivalent of the bits. 1095 * @throw std::overflow_error If there are too many bits to be 1096 * represented in an @c unsigned @c long. 1097 */ 1098 unsigned long long 1099 to_ullong() const 1100 { return this->_M_do_to_ullong(); } 1101 1102 /** 1103 * @brief Returns a character interpretation of the %dynamic_bitset. 1104 * @return The string equivalent of the bits. 1105 * 1106 * Note the ordering of the bits: decreasing character positions 1107 * correspond to increasing bit positions (see the main class notes for 1108 * an example). 1109 */ 1110 template<typename _CharT = char, 1111 typename _Traits = std::char_traits<_CharT>, 1112 typename _Alloc1 = std::allocator<_CharT>> 1113 std::basic_string<_CharT, _Traits, _Alloc1> 1114 to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const 1115 { 1116 std::basic_string<_CharT, _Traits, _Alloc1> __result; 1117 _M_copy_to_string(__result, __zero, __one); 1118 return __result; 1119 } 1120 1121 // Helper functions for string operations. 1122 template<typename _CharT, typename _Traits> 1123 void 1124 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t, 1125 _CharT, _CharT); 1126 1127 template<typename _CharT, typename _Traits, typename _Alloc1> 1128 void 1129 _M_copy_from_string(const std::basic_string<_CharT, 1130 _Traits, _Alloc1>& __str, size_t __pos, size_t __n, 1131 _CharT __zero = _CharT('0'), 1132 _CharT __one = _CharT('1')) 1133 { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(), 1134 __pos, __n, __zero, __one); } 1135 1136 template<typename _CharT, typename _Traits, typename _Alloc1> 1137 void 1138 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str, 1139 _CharT __zero = _CharT('0'), 1140 _CharT __one = _CharT('1')) const; 1141 1142 /// Returns the number of bits which are set. 1143 size_type 1144 count() const 1145 { return this->_M_do_count(); } 1146 1147 /// Returns the total number of bits. 1148 size_type 1149 size() const 1150 { return this->_M_Nb; } 1151 1152 /// Returns the total number of blocks. 1153 size_type num_blocks() const 1154 { return this->_M_size(); } 1155 1156 /// Returns true if the dynamic_bitset is empty. 1157 bool 1158 empty() const 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() const 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