libstdc++
dynamic_bitset
Go to the documentation of this file.
00001 // TR2 <dynamic_bitset> -*- C++ -*-
00002 
00003 // Copyright (C) 2009-2013 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file tr2/dynamic_bitset
00026  *  This is a TR2 C++ Library header.
00027  */
00028 
00029 #ifndef _GLIBCXX_TR2_DYNAMIC_BITSET
00030 #define _GLIBCXX_TR2_DYNAMIC_BITSET 1
00031 
00032 #pragma GCC system_header
00033 
00034 #include <limits>
00035 #include <vector>
00036 #include <string>
00037 #include <memory> // For std::allocator
00038 #include <bits/functexcept.h>   // For invalid_argument, out_of_range,
00039                 // overflow_error
00040 #include <iosfwd>
00041 #include <bits/cxxabi_forced.h>
00042 
00043 namespace std _GLIBCXX_VISIBILITY(default)
00044 {
00045 namespace tr2
00046 {
00047 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00048 
00049   /**
00050    *  Dynamic Bitset.
00051    *
00052    *  See N2050,
00053    *  Proposal to Add a Dynamically Sizeable Bitset to the Standard Library.
00054    */
00055 namespace __detail
00056 {
00057 
00058 template<typename T>
00059 class _Bool2UChar
00060 {
00061   typedef T type;
00062 };
00063 
00064 template<>
00065 class _Bool2UChar<bool>
00066 {
00067 public:
00068   typedef unsigned char type;
00069 };
00070 
00071 }
00072 
00073   /**
00074    *  Base class, general case.
00075    *
00076    *  See documentation for dynamic_bitset.
00077    */
00078   template<typename _WordT = unsigned long long,
00079        typename _Alloc = std::allocator<_WordT>>
00080     struct __dynamic_bitset_base
00081     {
00082       static_assert(std::is_unsigned<_WordT>::value, "template argument "
00083             "_WordT not an unsigned integral type");
00084 
00085       typedef _WordT block_type;
00086       typedef _Alloc allocator_type;
00087       typedef size_t size_type;
00088 
00089       static const size_type _S_bits_per_block = __CHAR_BIT__ * sizeof(block_type);
00090       static const size_type npos = static_cast<size_type>(-1);
00091 
00092       /// 0 is the least significant word.
00093       std::vector<block_type, allocator_type> _M_w;
00094 
00095       explicit
00096       __dynamic_bitset_base(const allocator_type& __alloc = allocator_type())
00097       : _M_w(__alloc)
00098       { }
00099 
00100       explicit
00101       __dynamic_bitset_base(__dynamic_bitset_base&& __b)
00102       { this->_M_w.swap(__b._M_w); }
00103 
00104       explicit
00105       __dynamic_bitset_base(size_type __nbits, unsigned long long __val = 0ULL,
00106                const allocator_type& __alloc = allocator_type())
00107       : _M_w(__nbits / _S_bits_per_block
00108          + (__nbits % _S_bits_per_block > 0),
00109          __val, __alloc)
00110       {
00111     unsigned long long __mask = ~static_cast<block_type>(0);
00112     size_t __n = std::min(this->_M_w.size(),
00113                   sizeof(unsigned long long) / sizeof(block_type));
00114     for (size_t __i = 0; __i < __n; ++__i)
00115       {
00116         this->_M_w[__i] = (__val & __mask) >> (__i * _S_bits_per_block);
00117         __mask <<= _S_bits_per_block;
00118       }
00119       }
00120 
00121       void
00122       _M_assign(const __dynamic_bitset_base& __b)
00123       { this->_M_w = __b._M_w; }
00124 
00125       void
00126       _M_swap(__dynamic_bitset_base& __b)
00127       { this->_M_w.swap(__b._M_w); }
00128 
00129       void
00130       _M_clear()
00131       { this->_M_w.clear(); }
00132 
00133       void
00134       _M_resize(size_t __nbits, bool __value)
00135       {
00136     size_t __sz = __nbits / _S_bits_per_block;
00137     if (__nbits % _S_bits_per_block > 0)
00138       ++__sz;
00139     if (__sz != this->_M_w.size())
00140       this->_M_w.resize(__sz);
00141       }
00142 
00143       allocator_type
00144       _M_get_allocator() const
00145       { return this->_M_w.get_allocator(); }
00146 
00147       static size_type
00148       _S_whichword(size_type __pos) noexcept
00149       { return __pos / _S_bits_per_block; }
00150 
00151       static size_type
00152       _S_whichbyte(size_type __pos) noexcept
00153       { return (__pos % _S_bits_per_block) / __CHAR_BIT__; }
00154 
00155       static size_type
00156       _S_whichbit(size_type __pos) noexcept
00157       { return __pos % _S_bits_per_block; }
00158 
00159       static block_type
00160       _S_maskbit(size_type __pos) noexcept
00161       { return (static_cast<block_type>(1)) << _S_whichbit(__pos); }
00162 
00163       block_type&
00164       _M_getword(size_type __pos)
00165       { return this->_M_w[_S_whichword(__pos)]; }
00166 
00167       block_type
00168       _M_getword(size_type __pos) const
00169       { return this->_M_w[_S_whichword(__pos)]; }
00170 
00171       block_type&
00172       _M_hiword()
00173       { return this->_M_w[_M_w.size() - 1]; }
00174 
00175       block_type
00176       _M_hiword() const
00177       { return this->_M_w[_M_w.size() - 1]; }
00178 
00179       void
00180       _M_do_and(const __dynamic_bitset_base& __x)
00181       {
00182     if (__x._M_w.size() == this->_M_w.size())
00183       for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00184         this->_M_w[__i] &= __x._M_w[__i];
00185     else
00186       return;
00187       }
00188 
00189       void
00190       _M_do_or(const __dynamic_bitset_base& __x)
00191       {
00192     if (__x._M_w.size() == this->_M_w.size())
00193       for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00194         this->_M_w[__i] |= __x._M_w[__i];
00195     else
00196       return;
00197       }
00198 
00199       void
00200       _M_do_xor(const __dynamic_bitset_base& __x)
00201       {
00202     if (__x._M_w.size() == this->_M_w.size())
00203       for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00204         this->_M_w[__i] ^= __x._M_w[__i];
00205     else
00206       return;
00207       }
00208 
00209       void
00210       _M_do_dif(const __dynamic_bitset_base& __x)
00211       {
00212     if (__x._M_w.size() == this->_M_w.size())
00213       for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00214         this->_M_w[__i] &= ~__x._M_w[__i];
00215     else
00216       return;
00217       }
00218 
00219       void
00220       _M_do_left_shift(size_t __shift);
00221 
00222       void
00223       _M_do_right_shift(size_t __shift);
00224 
00225       void
00226       _M_do_flip()
00227       {
00228     for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00229       this->_M_w[__i] = ~this->_M_w[__i];
00230       }
00231 
00232       void
00233       _M_do_set()
00234       {
00235     for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00236       this->_M_w[__i] = ~static_cast<block_type>(0);
00237       }
00238 
00239       void
00240       _M_do_reset()
00241       {
00242     for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00243       this->_M_w[__i] = static_cast<block_type>(0);
00244       }
00245 
00246       bool
00247       _M_is_equal(const __dynamic_bitset_base& __x) const
00248       {
00249     if (__x.size() == this->size())
00250       {
00251         for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00252           if (this->_M_w[__i] != __x._M_w[__i])
00253         return false;
00254         return true;
00255       }
00256     else
00257       return false;
00258       }
00259 
00260       bool
00261       _M_is_less(const __dynamic_bitset_base& __x) const
00262       {
00263     if (__x.size() == this->size())
00264       {
00265         for (size_t __i = this->_M_w.size(); __i > 0; --__i)
00266           {
00267         if (this->_M_w[__i-1] < __x._M_w[__i-1])
00268           return true;
00269         else if (this->_M_w[__i-1] > __x._M_w[__i-1])
00270           return false;
00271           }
00272         return false;
00273       }
00274     else
00275       return false;
00276       }
00277 
00278       size_t
00279       _M_are_all_aux() const
00280       {
00281     for (size_t __i = 0; __i < this->_M_w.size() - 1; ++__i)
00282       if (_M_w[__i] != ~static_cast<block_type>(0))
00283         return 0;
00284     return ((this->_M_w.size() - 1) * _S_bits_per_block
00285         + __builtin_popcountl(this->_M_hiword()));
00286       }
00287 
00288       bool
00289       _M_is_any() const
00290       {
00291     for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00292       if (this->_M_w[__i] != static_cast<block_type>(0))
00293         return true;
00294     return false;
00295       }
00296 
00297       bool
00298       _M_is_subset_of(const __dynamic_bitset_base& __b)
00299       {
00300     if (__b.size() == this->size())
00301       {
00302         for (size_t __i = 0; __i < _M_w.size(); ++__i)
00303           if (this->_M_w[__i] != (this->_M_w[__i] | __b._M_w[__i]))
00304         return false;
00305         return true;
00306       }
00307     else
00308       return false;
00309       }
00310 
00311       bool
00312       _M_is_proper_subset_of(const __dynamic_bitset_base& __b) const
00313       {
00314     if (this->is_subset_of(__b))
00315       {
00316         if (*this == __b)
00317           return false;
00318         else
00319           return true;
00320       }
00321     else
00322       return false;
00323       }
00324 
00325       size_t
00326       _M_do_count() const
00327       {
00328     size_t __result = 0;
00329     for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00330       __result += __builtin_popcountl(this->_M_w[__i]);
00331     return __result;
00332       }
00333 
00334       size_type
00335       _M_size() const noexcept
00336       { return this->_M_w.size(); }
00337 
00338       unsigned long
00339       _M_do_to_ulong() const;
00340 
00341       unsigned long long
00342       _M_do_to_ullong() const;
00343 
00344       // find first "on" bit
00345       size_type
00346       _M_do_find_first(size_t __not_found) const;
00347 
00348       // find the next "on" bit that follows "prev"
00349       size_type
00350       _M_do_find_next(size_t __prev, size_t __not_found) const;
00351 
00352       // do append of block
00353       void
00354       _M_do_append_block(block_type __block, size_type __pos)
00355       {
00356     size_t __offset = __pos % _S_bits_per_block;
00357     if (__offset == 0)
00358       this->_M_w.push_back(__block);
00359     else
00360       {
00361         this->_M_hiword() |= (__block << __offset);
00362         this->_M_w.push_back(__block >> (_S_bits_per_block - __offset));
00363       }
00364       }
00365     };
00366 
00367   // Definitions of non-inline functions from __dynamic_bitset_base.
00368   template<typename _WordT, typename _Alloc>
00369     void
00370     __dynamic_bitset_base<_WordT, _Alloc>::_M_do_left_shift(size_t __shift)
00371     {
00372       if (__builtin_expect(__shift != 0, 1))
00373     {
00374       const size_t __wshift = __shift / _S_bits_per_block;
00375       const size_t __offset = __shift % _S_bits_per_block;
00376 
00377       if (__offset == 0)
00378         for (size_t __n = this->_M_w.size() - 1; __n >= __wshift; --__n)
00379           this->_M_w[__n] = this->_M_w[__n - __wshift];
00380       else
00381         {
00382           const size_t __sub_offset = _S_bits_per_block - __offset;
00383           for (size_t __n = _M_w.size() - 1; __n > __wshift; --__n)
00384         this->_M_w[__n] = ((this->_M_w[__n - __wshift] << __offset)
00385                  | (this->_M_w[__n - __wshift - 1] >> __sub_offset));
00386           this->_M_w[__wshift] = this->_M_w[0] << __offset;
00387         }
00388 
00389       //// std::fill(this->_M_w.begin(), this->_M_w.begin() + __wshift,
00390       ////          static_cast<_WordT>(0));
00391     }
00392     }
00393 
00394   template<typename _WordT, typename _Alloc>
00395     void
00396     __dynamic_bitset_base<_WordT, _Alloc>::_M_do_right_shift(size_t __shift)
00397     {
00398       if (__builtin_expect(__shift != 0, 1))
00399     {
00400       const size_t __wshift = __shift / _S_bits_per_block;
00401       const size_t __offset = __shift % _S_bits_per_block;
00402       const size_t __limit = this->_M_w.size() - __wshift - 1;
00403 
00404       if (__offset == 0)
00405         for (size_t __n = 0; __n <= __limit; ++__n)
00406           this->_M_w[__n] = this->_M_w[__n + __wshift];
00407       else
00408         {
00409           const size_t __sub_offset = (_S_bits_per_block
00410                        - __offset);
00411           for (size_t __n = 0; __n < __limit; ++__n)
00412         this->_M_w[__n] = ((this->_M_w[__n + __wshift] >> __offset)
00413                  | (this->_M_w[__n + __wshift + 1] << __sub_offset));
00414           this->_M_w[__limit] = this->_M_w[_M_w.size()-1] >> __offset;
00415         }
00416 
00417       ////std::fill(this->_M_w.begin() + __limit + 1, this->_M_w.end(),
00418       ////          static_cast<_WordT>(0));
00419     }
00420     }
00421 
00422   template<typename _WordT, typename _Alloc>
00423     unsigned long
00424     __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ulong() const
00425     {
00426       size_t __n = sizeof(unsigned long) / sizeof(block_type);
00427       for (size_t __i = __n; __i < this->_M_w.size(); ++__i)
00428     if (this->_M_w[__i])
00429       __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ulong"));
00430       unsigned long __res = 0UL;
00431       for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
00432     __res += this->_M_w[__i] << (__i * _S_bits_per_block);
00433       return __res;
00434     }
00435 
00436   template<typename _WordT, typename _Alloc>
00437     unsigned long long
00438     __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ullong() const
00439     {
00440       size_t __n = sizeof(unsigned long long) / sizeof(block_type);
00441       for (size_t __i = __n; __i < this->_M_w.size(); ++__i)
00442     if (this->_M_w[__i])
00443       __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ullong"));
00444       unsigned long long __res = 0ULL;
00445       for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
00446     __res += this->_M_w[__i] << (__i * _S_bits_per_block);
00447       return __res;
00448     }
00449 
00450   template<typename _WordT, typename _Alloc>
00451     size_t
00452     __dynamic_bitset_base<_WordT, _Alloc>
00453     ::_M_do_find_first(size_t __not_found) const
00454     {
00455       for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00456     {
00457       _WordT __thisword = this->_M_w[__i];
00458       if (__thisword != static_cast<_WordT>(0))
00459         return (__i * _S_bits_per_block
00460             + __builtin_ctzl(__thisword));
00461     }
00462       // not found, so return an indication of failure.
00463       return __not_found;
00464     }
00465 
00466   template<typename _WordT, typename _Alloc>
00467     size_t
00468     __dynamic_bitset_base<_WordT, _Alloc>
00469     ::_M_do_find_next(size_t __prev, size_t __not_found) const
00470     {
00471       // make bound inclusive
00472       ++__prev;
00473 
00474       // check out of bounds
00475       if (__prev >= this->_M_w.size() * _S_bits_per_block)
00476     return __not_found;
00477 
00478       // search first word
00479       size_t __i = _S_whichword(__prev);
00480       _WordT __thisword = this->_M_w[__i];
00481 
00482       // mask off bits below bound
00483       __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
00484 
00485       if (__thisword != static_cast<_WordT>(0))
00486     return (__i * _S_bits_per_block
00487         + __builtin_ctzl(__thisword));
00488 
00489       // check subsequent words
00490       for (++__i; __i < this->_M_w.size(); ++__i)
00491     {
00492       __thisword = this->_M_w[__i];
00493       if (__thisword != static_cast<_WordT>(0))
00494         return (__i * _S_bits_per_block
00495             + __builtin_ctzl(__thisword));
00496     }
00497       // not found, so return an indication of failure.
00498       return __not_found;
00499     } // end _M_do_find_next
00500 
00501   /**
00502    *  @brief  The %dynamic_bitset class represents a sequence of bits.
00503    *
00504    *  @ingroup containers
00505    *
00506    *  (Note that %dynamic_bitset does @e not meet the formal
00507    *  requirements of a <a href="tables.html#65">container</a>.
00508    *  Mainly, it lacks iterators.)
00509    *
00510    *  The template argument, @a Nb, may be any non-negative number,
00511    *  specifying the number of bits (e.g., "0", "12", "1024*1024").
00512    *
00513    *  In the general unoptimized case, storage is allocated in
00514    *  word-sized blocks.  Let B be the number of bits in a word, then
00515    *  (Nb+(B-1))/B words will be used for storage.  B - Nb%B bits are
00516    *  unused.  (They are the high-order bits in the highest word.)  It
00517    *  is a class invariant that those unused bits are always zero.
00518    *
00519    *  If you think of %dynamic_bitset as "a simple array of bits," be
00520    *  aware that your mental picture is reversed: a %dynamic_bitset
00521    *  behaves the same way as bits in integers do, with the bit at
00522    *  index 0 in the "least significant / right-hand" position, and
00523    *  the bit at index Nb-1 in the "most significant / left-hand"
00524    *  position.  Thus, unlike other containers, a %dynamic_bitset's
00525    *  index "counts from right to left," to put it very loosely.
00526    *
00527    *  This behavior is preserved when translating to and from strings.
00528    *  For example, the first line of the following program probably
00529    *  prints "b('a') is 0001100001" on a modern ASCII system.
00530    *
00531    *  @code
00532    *     #include <dynamic_bitset>
00533    *     #include <iostream>
00534    *     #include <sstream>
00535    *
00536    *     using namespace std;
00537    *
00538    *     int main()
00539    *     {
00540    *         long         a = 'a';
00541    *         dynamic_bitset   b(a);
00542    *
00543    *         cout << "b('a') is " << b << endl;
00544    *
00545    *         ostringstream s;
00546    *         s << b;
00547    *         string  str = s.str();
00548    *         cout << "index 3 in the string is " << str[3] << " but\n"
00549    *              << "index 3 in the bitset is " << b[3] << endl;
00550    *     }
00551    *  @endcode
00552    *
00553    *  Also see:
00554    *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch33s02.html
00555    *  for a description of extensions.
00556    *
00557    *  Most of the actual code isn't contained in %dynamic_bitset<>
00558    *  itself, but in the base class __dynamic_bitset_base.  The base
00559    *  class works with whole words, not with individual bits.  This
00560    *  allows us to specialize __dynamic_bitset_base for the important
00561    *  special case where the %dynamic_bitset is only a single word.
00562    *
00563    *  Extra confusion can result due to the fact that the storage for
00564    *  __dynamic_bitset_base @e is a vector, and is indexed as such.  This is
00565    *  carefully encapsulated.
00566    */
00567   template<typename _WordT = unsigned long long,
00568        typename _Alloc = std::allocator<_WordT>>
00569     class dynamic_bitset
00570     : private __dynamic_bitset_base<_WordT, _Alloc>
00571     {
00572       static_assert(std::is_unsigned<_WordT>::value, "template argument "
00573             "_WordT not an unsigned integral type");
00574 
00575     public:
00576 
00577       typedef __dynamic_bitset_base<_WordT, _Alloc> _Base;
00578       typedef _WordT block_type;
00579       typedef _Alloc allocator_type;
00580       typedef size_t size_type;
00581 
00582       static const size_type bits_per_block = __CHAR_BIT__ * sizeof(block_type);
00583       // Use this: constexpr size_type std::numeric_limits<size_type>::max().
00584       static const size_type npos = static_cast<size_type>(-1);
00585 
00586     private:
00587 
00588       //  Clear the unused bits in the uppermost word.
00589       void
00590       _M_do_sanitize()
00591       {
00592     size_type __shift = this->_M_Nb % bits_per_block;
00593     if (__shift > 0)
00594       this->_M_hiword() &= ~((~static_cast<block_type>(0)) << __shift);
00595       }
00596 
00597       /**
00598        *  These versions of single-bit set, reset, flip, and test
00599        *  do no range checking.
00600        */
00601       dynamic_bitset<_WordT, _Alloc>&
00602       _M_unchecked_set(size_type __pos)
00603       {
00604     this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
00605     return *this;
00606       }
00607 
00608       dynamic_bitset<_WordT, _Alloc>&
00609       _M_unchecked_set(size_type __pos, int __val)
00610       {
00611     if (__val)
00612       this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
00613     else
00614       this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
00615     return *this;
00616       }
00617 
00618       dynamic_bitset<_WordT, _Alloc>&
00619       _M_unchecked_reset(size_type __pos)
00620       {
00621     this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
00622     return *this;
00623       }
00624 
00625       dynamic_bitset<_WordT, _Alloc>&
00626       _M_unchecked_flip(size_type __pos)
00627       {
00628     this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
00629     return *this;
00630       }
00631 
00632       bool
00633       _M_unchecked_test(size_type __pos) const
00634       { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
00635         != static_cast<_WordT>(0)); }
00636 
00637       size_type _M_Nb;
00638 
00639     public:
00640       /**
00641        *  This encapsulates the concept of a single bit.  An instance
00642        *  of this class is a proxy for an actual bit; this way the
00643        *  individual bit operations are done as faster word-size
00644        *  bitwise instructions.
00645        *
00646        *  Most users will never need to use this class directly;
00647        *  conversions to and from bool are automatic and should be
00648        *  transparent.  Overloaded operators help to preserve the
00649        *  illusion.
00650        *
00651        *  (On a typical system, this "bit %reference" is 64 times the
00652        *  size of an actual bit.  Ha.)
00653        */
00654       class reference
00655       {
00656     friend class dynamic_bitset;
00657 
00658     block_type *_M_wp;
00659     size_type _M_bpos;
00660 
00661     // left undefined
00662     reference();
00663 
00664       public:
00665     reference(dynamic_bitset& __b, size_type __pos)
00666     {
00667       this->_M_wp = &__b._M_getword(__pos);
00668       this->_M_bpos = _Base::_S_whichbit(__pos);
00669     }
00670 
00671     ~reference()
00672     { }
00673 
00674     // For b[i] = __x;
00675     reference&
00676     operator=(bool __x)
00677     {
00678       if (__x)
00679         *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
00680       else
00681         *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
00682       return *this;
00683     }
00684 
00685     // For b[i] = b[__j];
00686     reference&
00687     operator=(const reference& __j)
00688     {
00689       if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
00690         *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
00691       else
00692         *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
00693       return *this;
00694     }
00695 
00696     // Flips the bit
00697     bool
00698     operator~() const
00699     { return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; }
00700 
00701     // For __x = b[i];
00702     operator bool() const
00703     { return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; }
00704 
00705     // For b[i].flip();
00706     reference&
00707     flip()
00708     {
00709       *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos);
00710       return *this;
00711     }
00712       };
00713 
00714       friend class reference;
00715 
00716       typedef bool const_reference;
00717 
00718       // 23.3.5.1 constructors:
00719       /// All bits set to zero.
00720       explicit
00721       dynamic_bitset(const allocator_type& __alloc = allocator_type())
00722       : _Base(__alloc), _M_Nb(0)
00723       { }
00724 
00725       /// Initial bits bitwise-copied from a single word (others set to zero).
00726       explicit
00727       dynamic_bitset(size_type __nbits, unsigned long long __val = 0ULL,
00728              const allocator_type& __alloc = allocator_type())
00729       : _Base(__nbits, __val, __alloc),
00730     _M_Nb(__nbits)
00731       { }
00732 
00733       dynamic_bitset(initializer_list<block_type> __il,
00734              const allocator_type& __alloc = allocator_type())
00735       : _Base(__alloc), _M_Nb(0)
00736       { this->append(__il); }
00737 
00738       /**
00739        *  @brief  Use a subset of a string.
00740        *  @param  __str  A string of '0' and '1' characters.
00741        *  @param  __pos  Index of the first character in @p __str to use.
00742        *  @param  __n    The number of characters to copy.
00743        *  @throw  std::out_of_range  If @p __pos is bigger the size of @p __str.
00744        *  @throw  std::invalid_argument  If a character appears in the string
00745        *                                 which is neither '0' nor '1'.
00746        */
00747       template<typename _CharT, typename _Traits, typename _Alloc1>
00748     explicit
00749     dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc1>& __str,
00750                typename basic_string<_CharT,_Traits,_Alloc1>::size_type
00751                __pos = 0,
00752                typename basic_string<_CharT,_Traits,_Alloc1>::size_type
00753                __n = std::basic_string<_CharT, _Traits, _Alloc1>::npos,
00754                _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'),
00755                const allocator_type& __alloc = allocator_type())
00756     : _Base(__alloc),
00757       _M_Nb(0) // Watch for npos.
00758     {
00759       if (__pos > __str.size())
00760         __throw_out_of_range(__N("dynamic_bitset::bitset initial position "
00761                      "not valid"));
00762 
00763       // Watch for npos.
00764       this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n);
00765       this->resize(this->_M_Nb);
00766       this->_M_copy_from_string(__str, __pos, __n,
00767                     _CharT('0'), _CharT('1'));
00768     }
00769 
00770       /**
00771        *  @brief  Construct from a string.
00772        *  @param  __str  A string of '0' and '1' characters.
00773        *  @throw  std::invalid_argument  If a character appears in the string
00774        *                                 which is neither '0' nor '1'.
00775        */
00776       explicit
00777       dynamic_bitset(const char* __str,
00778              const allocator_type& __alloc = allocator_type())
00779       : _Base(__alloc)
00780       {
00781     size_t __len = 0;
00782     if (__str)
00783       while (__str[__len] != '\0')
00784         ++__len;
00785     this->resize(__len);
00786     this->_M_copy_from_ptr<char,std::char_traits<char>>
00787            (__str, __len, 0, __len, '0', '1');
00788       }
00789 
00790       /**
00791        *  @brief  Copy constructor.
00792        */
00793       dynamic_bitset(const dynamic_bitset& __b)
00794       : _Base(__b), _M_Nb(__b.size())
00795       { }
00796 
00797       /**
00798        *  @brief  Move constructor.
00799        */
00800       dynamic_bitset(dynamic_bitset&& __b)
00801       : _Base(std::forward<_Base>(__b)), _M_Nb(__b.size())
00802       { }
00803 
00804       /**
00805        *  @brief  Swap with another bitset.
00806        */
00807       void
00808       swap(dynamic_bitset& __b)
00809       {
00810     this->_M_swap(__b);
00811     std::swap(this->_M_Nb, __b._M_Nb);
00812       }
00813 
00814       /**
00815        *  @brief  Assignment.
00816        */
00817       dynamic_bitset&
00818       operator=(const dynamic_bitset& __b)
00819       {
00820     if (&__b != this)
00821       {
00822         this->_M_assign(__b);
00823         this->_M_Nb = __b._M_Nb;
00824       }
00825       }
00826 
00827       /**
00828        *  @brief  Move assignment.
00829        */
00830       dynamic_bitset&
00831       operator=(dynamic_bitset&& __b)
00832       {
00833     this->swap(__b);
00834     return *this;
00835       }
00836 
00837       /**
00838        *  @brief  Return the allocator for the bitset.
00839        */
00840       allocator_type
00841       get_allocator() const
00842       { return this->_M_get_allocator(); }
00843 
00844       /**
00845        *  @brief  Resize the bitset.
00846        */
00847       void
00848       resize(size_type __nbits, bool __value = false)
00849       {
00850     this->_M_resize(__nbits, __value);
00851     this->_M_Nb = __nbits;
00852     this->_M_do_sanitize();
00853       }
00854 
00855       /**
00856        *  @brief  Clear the bitset.
00857        */
00858       void
00859       clear()
00860       {
00861     this->_M_clear();
00862     this->_M_Nb = 0;
00863       }
00864 
00865       /**
00866        *  @brief  Push a bit onto the high end of the bitset.
00867        */
00868       void
00869       push_back(bool __bit)
00870       {
00871     if (size_t __offset = this->size() % bits_per_block == 0)
00872       this->_M_do_append_block(block_type(0), this->_M_Nb);
00873     ++this->_M_Nb;
00874     this->_M_unchecked_set(this->_M_Nb, __bit);
00875       }
00876 
00877       /**
00878        *  @brief  Append a block.
00879        */
00880       void
00881       append(block_type __block)
00882       {
00883     this->_M_do_append_block(__block, this->_M_Nb);
00884     this->_M_Nb += bits_per_block;
00885       }
00886 
00887       /**
00888        *  @brief
00889        */
00890       void
00891       append(initializer_list<block_type> __il)
00892       { this->append(__il.begin(), __il.end()); }
00893 
00894       /**
00895        *  @brief  Append an iterator range of blocks.
00896        */
00897       template <typename _BlockInputIterator>
00898     void
00899     append(_BlockInputIterator __first, _BlockInputIterator __last)
00900     {
00901       for (; __first != __last; ++__first)
00902         this->append(*__first);
00903     }
00904 
00905       // 23.3.5.2 dynamic_bitset operations:
00906       //@{
00907       /**
00908        *  @brief  Operations on dynamic_bitsets.
00909        *  @param  __rhs  A same-sized dynamic_bitset.
00910        *
00911        *  These should be self-explanatory.
00912        */
00913       dynamic_bitset<_WordT, _Alloc>&
00914       operator&=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
00915       {
00916     this->_M_do_and(__rhs);
00917     return *this;
00918       }
00919 
00920       dynamic_bitset<_WordT, _Alloc>&
00921       operator&=(dynamic_bitset<_WordT, _Alloc>&& __rhs)
00922       {
00923     this->_M_do_and(std::move(__rhs));
00924     return *this;
00925       }
00926 
00927       dynamic_bitset<_WordT, _Alloc>&
00928       operator|=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
00929       {
00930     this->_M_do_or(__rhs);
00931     return *this;
00932       }
00933 
00934       dynamic_bitset<_WordT, _Alloc>&
00935       operator^=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
00936       {
00937     this->_M_do_xor(__rhs);
00938     return *this;
00939       }
00940 
00941       dynamic_bitset<_WordT, _Alloc>&
00942       operator-=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
00943       {
00944     this->_M_do_dif(__rhs);
00945     return *this;
00946       }
00947       //@}
00948 
00949       //@{
00950       /**
00951        *  @brief  Operations on dynamic_bitsets.
00952        *  @param  __pos The number of places to shift.
00953        *
00954        *  These should be self-explanatory.
00955        */
00956       dynamic_bitset<_WordT, _Alloc>&
00957       operator<<=(size_type __pos)
00958       {
00959     if (__builtin_expect(__pos < this->_M_Nb, 1))
00960       {
00961         this->_M_do_left_shift(__pos);
00962         this->_M_do_sanitize();
00963       }
00964     else
00965       this->_M_do_reset();
00966     return *this;
00967       }
00968 
00969       dynamic_bitset<_WordT, _Alloc>&
00970       operator>>=(size_type __pos)
00971       {
00972     if (__builtin_expect(__pos < this->_M_Nb, 1))
00973       {
00974         this->_M_do_right_shift(__pos);
00975         this->_M_do_sanitize();
00976       }
00977     else
00978       this->_M_do_reset();
00979     return *this;
00980       }
00981       //@}
00982 
00983       // Set, reset, and flip.
00984       /**
00985        *  @brief Sets every bit to true.
00986        */
00987       dynamic_bitset<_WordT, _Alloc>&
00988       set()
00989       {
00990     this->_M_do_set();
00991     this->_M_do_sanitize();
00992     return *this;
00993       }
00994 
00995       /**
00996        *  @brief Sets a given bit to a particular value.
00997        *  @param  __pos  The index of the bit.
00998        *  @param  __val  Either true or false, defaults to true.
00999        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
01000        */
01001       dynamic_bitset<_WordT, _Alloc>&
01002       set(size_type __pos, bool __val = true)
01003       {
01004     if (__pos >= _M_Nb)
01005       __throw_out_of_range(__N("dynamic_bitset::set"));
01006     return this->_M_unchecked_set(__pos, __val);
01007       }
01008 
01009       /**
01010        *  @brief Sets every bit to false.
01011        */
01012       dynamic_bitset<_WordT, _Alloc>&
01013       reset()
01014       {
01015     this->_M_do_reset();
01016     return *this;
01017       }
01018 
01019       /**
01020        *  @brief Sets a given bit to false.
01021        *  @param  __pos  The index of the bit.
01022        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
01023        *
01024        *  Same as writing @c set(__pos, false).
01025        */
01026       dynamic_bitset<_WordT, _Alloc>&
01027       reset(size_type __pos)
01028       {
01029     if (__pos >= _M_Nb)
01030       __throw_out_of_range(__N("dynamic_bitset::reset"));
01031     return this->_M_unchecked_reset(__pos);
01032       }
01033 
01034       /**
01035        *  @brief Toggles every bit to its opposite value.
01036        */
01037       dynamic_bitset<_WordT, _Alloc>&
01038       flip()
01039       {
01040     this->_M_do_flip();
01041     this->_M_do_sanitize();
01042     return *this;
01043       }
01044 
01045       /**
01046        *  @brief Toggles a given bit to its opposite value.
01047        *  @param  __pos  The index of the bit.
01048        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
01049        */
01050       dynamic_bitset<_WordT, _Alloc>&
01051       flip(size_type __pos)
01052       {
01053     if (__pos >= _M_Nb)
01054       __throw_out_of_range(__N("dynamic_bitset::flip"));
01055     return this->_M_unchecked_flip(__pos);
01056       }
01057 
01058       /// See the no-argument flip().
01059       dynamic_bitset<_WordT, _Alloc>
01060       operator~() const
01061       { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); }
01062 
01063       //@{
01064       /**
01065        *  @brief  Array-indexing support.
01066        *  @param  __pos  Index into the %dynamic_bitset.
01067        *  @return A bool for a 'const %dynamic_bitset'.  For non-const
01068        *           bitsets, an instance of the reference proxy class.
01069        *  @note These operators do no range checking and throw no
01070        *         exceptions, as required by DR 11 to the standard.
01071        */
01072       reference
01073       operator[](size_type __pos)
01074       { return reference(*this,__pos); }
01075 
01076       const_reference
01077       operator[](size_type __pos) const
01078       { return _M_unchecked_test(__pos); }
01079       //@}
01080 
01081       /**
01082        *  @brief Returns a numerical interpretation of the %dynamic_bitset.
01083        *  @return  The integral equivalent of the bits.
01084        *  @throw  std::overflow_error  If there are too many bits to be
01085        *                               represented in an @c unsigned @c long.
01086        */
01087       unsigned long
01088       to_ulong() const
01089       { return this->_M_do_to_ulong(); }
01090 
01091       /**
01092        *  @brief Returns a numerical interpretation of the %dynamic_bitset.
01093        *  @return  The integral equivalent of the bits.
01094        *  @throw  std::overflow_error  If there are too many bits to be
01095        *                               represented in an @c unsigned @c long.
01096        */
01097       unsigned long long
01098       to_ullong() const
01099       { return this->_M_do_to_ullong(); }
01100 
01101       /**
01102        *  @brief Returns a character interpretation of the %dynamic_bitset.
01103        *  @return  The string equivalent of the bits.
01104        *
01105        *  Note the ordering of the bits:  decreasing character positions
01106        *  correspond to increasing bit positions (see the main class notes for
01107        *  an example).
01108        */
01109       template<typename _CharT = char,
01110            typename _Traits = std::char_traits<_CharT>,
01111            typename _Alloc1 = std::allocator<_CharT>>
01112     std::basic_string<_CharT, _Traits, _Alloc1>
01113     to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const
01114     {
01115       std::basic_string<_CharT, _Traits, _Alloc1> __result;
01116       _M_copy_to_string(__result, __zero, __one);
01117       return __result;
01118     }
01119 
01120       // Helper functions for string operations.
01121       template<typename _CharT, typename _Traits>
01122     void
01123     _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
01124              _CharT, _CharT);
01125 
01126       template<typename _CharT, typename _Traits, typename _Alloc1>
01127     void
01128     _M_copy_from_string(const std::basic_string<_CharT,
01129                 _Traits, _Alloc1>& __str, size_t __pos, size_t __n,
01130                 _CharT __zero = _CharT('0'),
01131                 _CharT __one = _CharT('1'))
01132     { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(),
01133                         __pos, __n, __zero, __one); }
01134 
01135       template<typename _CharT, typename _Traits, typename _Alloc1>
01136     void
01137     _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
01138               _CharT __zero = _CharT('0'),
01139               _CharT __one = _CharT('1')) const;
01140 
01141       /// Returns the number of bits which are set.
01142       size_type
01143       count() const noexcept
01144       { return this->_M_do_count(); }
01145 
01146       /// Returns the total number of bits.
01147       size_type
01148       size() const noexcept
01149       { return this->_M_Nb; }
01150 
01151       /// Returns the total number of blocks.
01152       size_type
01153       num_blocks() const noexcept
01154       { return this->_M_size(); }
01155 
01156       /// Returns true if the dynamic_bitset is empty.
01157       bool
01158       empty() const noexcept
01159       { return (this->_M_Nb == 0); }
01160 
01161       /// Returns the maximum size of a dynamic_bitset object having the same
01162       /// type as *this.
01163       /// The real answer is max() * bits_per_block but is likely to overflow.
01164       constexpr size_type
01165       max_size() noexcept
01166       { return std::numeric_limits<block_type>::max(); }
01167 
01168       /**
01169        *  @brief Tests the value of a bit.
01170        *  @param  __pos  The index of a bit.
01171        *  @return  The value at @a __pos.
01172        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
01173        */
01174       bool
01175       test(size_type __pos) const
01176       {
01177     if (__pos >= _M_Nb)
01178       __throw_out_of_range(__N("dynamic_bitset::test"));
01179     return _M_unchecked_test(__pos);
01180       }
01181 
01182       /**
01183        *  @brief Tests whether all the bits are on.
01184        *  @return  True if all the bits are set.
01185        */
01186       bool
01187       all() const
01188       { return this->_M_are_all_aux() == _M_Nb; }
01189 
01190       /**
01191        *  @brief Tests whether any of the bits are on.
01192        *  @return  True if at least one bit is set.
01193        */
01194       bool
01195       any() const
01196       { return this->_M_is_any(); }
01197 
01198       /**
01199        *  @brief Tests whether any of the bits are on.
01200        *  @return  True if none of the bits are set.
01201        */
01202       bool
01203       none() const
01204       { return !this->_M_is_any(); }
01205 
01206       //@{
01207       /// Self-explanatory.
01208       dynamic_bitset<_WordT, _Alloc>
01209       operator<<(size_type __pos) const
01210       { return dynamic_bitset<_WordT, _Alloc>(*this) <<= __pos; }
01211 
01212       dynamic_bitset<_WordT, _Alloc>
01213       operator>>(size_type __pos) const
01214       { return dynamic_bitset<_WordT, _Alloc>(*this) >>= __pos; }
01215       //@}
01216 
01217       /**
01218        *  @brief  Finds the index of the first "on" bit.
01219        *  @return  The index of the first bit set, or size() if not found.
01220        *  @sa  find_next
01221        */
01222       size_type
01223       find_first() const
01224       { return this->_M_do_find_first(this->_M_Nb); }
01225 
01226       /**
01227        *  @brief  Finds the index of the next "on" bit after prev.
01228        *  @return  The index of the next bit set, or size() if not found.
01229        *  @param  __prev  Where to start searching.
01230        *  @sa  find_first
01231        */
01232       size_type
01233       find_next(size_t __prev) const
01234       { return this->_M_do_find_next(__prev, this->_M_Nb); }
01235 
01236       bool
01237       is_subset_of(const dynamic_bitset& __b) const
01238       { return this->_M_is_subset_of(__b); }
01239 
01240       bool
01241       is_proper_subset_of(const dynamic_bitset& __b) const
01242       { return this->_M_is_proper_subset_of(__b); }
01243     };
01244 
01245   // Definitions of non-inline member functions.
01246   template<typename _WordT, typename _Alloc>
01247     template<typename _CharT, typename _Traits>
01248       void
01249       dynamic_bitset<_WordT, _Alloc>::
01250       _M_copy_from_ptr(const _CharT* __str, size_t __len,
01251                size_t __pos, size_t __n, _CharT __zero, _CharT __one)
01252       {
01253     reset();
01254     const size_t __nbits = std::min(_M_Nb, std::min(__n, __len - __pos));
01255     for (size_t __i = __nbits; __i > 0; --__i)
01256       {
01257         const _CharT __c = __str[__pos + __nbits - __i];
01258         if (_Traits::eq(__c, __zero))
01259           ;
01260         else if (_Traits::eq(__c, __one))
01261           _M_unchecked_set(__i - 1);
01262         else
01263           __throw_invalid_argument(__N("dynamic_bitset::_M_copy_from_ptr"));
01264       }
01265       }
01266 
01267   template<typename _WordT, typename _Alloc>
01268     template<typename _CharT, typename _Traits, typename _Alloc1>
01269       void
01270       dynamic_bitset<_WordT, _Alloc>::
01271       _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
01272             _CharT __zero, _CharT __one) const
01273       {
01274     __str.assign(_M_Nb, __zero);
01275     for (size_t __i = _M_Nb; __i > 0; --__i)
01276       if (_M_unchecked_test(__i - 1))
01277         _Traits::assign(__str[_M_Nb - __i], __one);
01278       }
01279 
01280 
01281   //@{
01282   /// These comparisons for equality/inequality are, well, @e bitwise.
01283   template<typename _WordT, typename _Alloc>
01284     bool
01285     operator==(const dynamic_bitset<_WordT, _Alloc>& __lhs,
01286            const dynamic_bitset<_WordT, _Alloc>& __rhs)
01287     { return __lhs._M_is_equal(__rhs); }
01288 
01289   template<typename _WordT, typename _Alloc>
01290     bool
01291     operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
01292            const dynamic_bitset<_WordT, _Alloc>& __rhs)
01293     { return !__lhs._M_is_equal(__rhs); }
01294 
01295   template<typename _WordT, typename _Alloc>
01296     bool
01297     operator<(const dynamic_bitset<_WordT, _Alloc>& __lhs,
01298           const dynamic_bitset<_WordT, _Alloc>& __rhs)
01299     { return __lhs._M_is_less(__rhs); }
01300 
01301   template<typename _WordT, typename _Alloc>
01302     bool
01303     operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
01304            const dynamic_bitset<_WordT, _Alloc>& __rhs)
01305     { return !(__lhs > __rhs); }
01306 
01307   template<typename _WordT, typename _Alloc>
01308     bool
01309     operator>(const dynamic_bitset<_WordT, _Alloc>& __lhs,
01310           const dynamic_bitset<_WordT, _Alloc>& __rhs)
01311     { return __rhs < __lhs; }
01312 
01313   template<typename _WordT, typename _Alloc>
01314     bool
01315     operator>=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
01316            const dynamic_bitset<_WordT, _Alloc>& __rhs)
01317     { return !(__lhs < __rhs); }
01318   //@}
01319 
01320   // 23.3.5.3 bitset operations:
01321   //@{
01322   /**
01323    *  @brief  Global bitwise operations on bitsets.
01324    *  @param  __x  A bitset.
01325    *  @param  __y  A bitset of the same size as @a __x.
01326    *  @return  A new bitset.
01327    *
01328    *  These should be self-explanatory.
01329    */
01330   template<typename _WordT, typename _Alloc>
01331     inline dynamic_bitset<_WordT, _Alloc>
01332     operator&(const dynamic_bitset<_WordT, _Alloc>& __x,
01333           const dynamic_bitset<_WordT, _Alloc>& __y)
01334     {
01335       dynamic_bitset<_WordT, _Alloc> __result(__x);
01336       __result &= __y;
01337       return __result;
01338     }
01339 
01340   template<typename _WordT, typename _Alloc>
01341     inline dynamic_bitset<_WordT, _Alloc>
01342     operator|(const dynamic_bitset<_WordT, _Alloc>& __x,
01343           const dynamic_bitset<_WordT, _Alloc>& __y)
01344     {
01345       dynamic_bitset<_WordT, _Alloc> __result(__x);
01346       __result |= __y;
01347       return __result;
01348     }
01349 
01350   template <typename _WordT, typename _Alloc>
01351     inline dynamic_bitset<_WordT, _Alloc>
01352     operator^(const dynamic_bitset<_WordT, _Alloc>& __x,
01353           const dynamic_bitset<_WordT, _Alloc>& __y)
01354     {
01355       dynamic_bitset<_WordT, _Alloc> __result(__x);
01356       __result ^= __y;
01357       return __result;
01358     }
01359 
01360   template <typename _WordT, typename _Alloc>
01361     inline dynamic_bitset<_WordT, _Alloc>
01362     operator-(const dynamic_bitset<_WordT, _Alloc>& __x,
01363           const dynamic_bitset<_WordT, _Alloc>& __y)
01364     {
01365       dynamic_bitset<_WordT, _Alloc> __result(__x);
01366       __result -= __y;
01367       return __result;
01368     }
01369   //@}
01370 
01371   //@{
01372   /**
01373    *  @brief Global I/O operators for bitsets.
01374    *
01375    *  Direct I/O between streams and bitsets is supported.  Output is
01376    *  straightforward.  Input will skip whitespace and only accept '0'
01377    *  and '1' characters.  The %dynamic_bitset will grow as necessary
01378    *  to hold the string of bits.
01379    */
01380   template<typename _CharT, typename _Traits,
01381        typename _WordT, typename _Alloc>
01382     std::basic_istream<_CharT, _Traits>&
01383     operator>>(std::basic_istream<_CharT, _Traits>& __is,
01384            dynamic_bitset<_WordT, _Alloc>& __x)
01385     {
01386       typedef typename _Traits::char_type          char_type;
01387       typedef std::basic_istream<_CharT, _Traits>  __istream_type;
01388       typedef typename __istream_type::ios_base    __ios_base;
01389 
01390       std::basic_string<_CharT, _Traits> __tmp;
01391       __tmp.reserve(__x.size());
01392 
01393       const char_type __zero = __is.widen('0');
01394       const char_type __one = __is.widen('1');
01395 
01396       typename __ios_base::iostate __state = __ios_base::goodbit;
01397       typename __istream_type::sentry __sentry(__is);
01398       if (__sentry)
01399     {
01400       __try
01401         {
01402           while (1)
01403         {
01404           static typename _Traits::int_type __eof = _Traits::eof();
01405 
01406           typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc();
01407           if (_Traits::eq_int_type(__c1, __eof))
01408             {
01409               __state |= __ios_base::eofbit;
01410               break;
01411             }
01412           else
01413             {
01414               const char_type __c2 = _Traits::to_char_type(__c1);
01415               if (_Traits::eq(__c2, __zero))
01416             __tmp.push_back(__zero);
01417               else if (_Traits::eq(__c2, __one))
01418             __tmp.push_back(__one);
01419               else if (_Traits::
01420                    eq_int_type(__is.rdbuf()->sputbackc(__c2),
01421                        __eof))
01422             {
01423               __state |= __ios_base::failbit;
01424               break;
01425             }
01426               else
01427             break;
01428             }
01429         }
01430         }
01431       __catch(__cxxabiv1::__forced_unwind&)
01432         {
01433           __is._M_setstate(__ios_base::badbit);
01434           __throw_exception_again;
01435         }
01436       __catch(...)
01437         { __is._M_setstate(__ios_base::badbit); }
01438     }
01439 
01440       __x.resize(__tmp.size());
01441 
01442       if (__tmp.empty() && __x.size())
01443     __state |= __ios_base::failbit;
01444       else
01445     __x._M_copy_from_string(__tmp, static_cast<size_t>(0), __x.size(),
01446                 __zero, __one);
01447       if (__state)
01448     __is.setstate(__state);
01449       return __is;
01450     }
01451 
01452   template <typename _CharT, typename _Traits,
01453         typename _WordT, typename _Alloc>
01454     std::basic_ostream<_CharT, _Traits>&
01455     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
01456            const dynamic_bitset<_WordT, _Alloc>& __x)
01457     {
01458       std::basic_string<_CharT, _Traits> __tmp;
01459 
01460       const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc());
01461       __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
01462       return __os << __tmp;
01463     }
01464   //@}
01465 
01466 _GLIBCXX_END_NAMESPACE_VERSION
01467 } // tr2
01468 } // std
01469 
01470 #undef _GLIBCXX_BITSET_BITS_PER_WORD
01471 
01472 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */