l4/pkg/l4re-core/libstdc++-v3/contrib/libstdc++-v3-4.8/include/tr2/dynamic_bitset

   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
  43 namespace std _GLIBCXX_VISIBILITY(default)
  44 {
  45 namespace 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    */
  55 namespace __detail
  56 {
  57
  58 template<typename T>
  59 class _Bool2UChar
  60 {
  61   typedef T type;
  62 };
  63
  64 template<>
  65 class _Bool2UChar<bool>
  66 {
  67 public:
  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 */