libstdc++-v3/include/tr2/dynamic_bitset

   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
  44 namespace std _GLIBCXX_VISIBILITY(default)
  45 {
  46 namespace 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    */
  56 namespace __detail
  57 {
  58
  59 template<typename T>
  60 class _Bool2UChar
  61 {
  62   typedef T type;
  63 };
  64
  65 template<>
  66 class _Bool2UChar<bool>
  67 {
  68 public:
  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 @a s to use.
 743        *  @param  n    The number of characters to copy.
 744        *  @throw  std::out_of_range  If @a pos is bigger the size of @a s.
 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  position  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  position  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  position  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  position  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  position  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  position  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 */