libstdc++
dynamic_bitset
Go to the documentation of this file.
00001 // TR2 <dynamic_bitset> -*- C++ -*-
00002 
00003 // Copyright (C) 2009, 2010, 2011 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 <cstddef> // For size_t
00037 #include <string>
00038 #include <memory> // For std::allocator
00039 #include <bits/functexcept.h>   // For invalid_argument, out_of_range,
00040                 // overflow_error
00041 #include <iosfwd>
00042 #include <cxxabi_forced.h>
00043 
00044 namespace std _GLIBCXX_VISIBILITY(default)
00045 {
00046 namespace tr2
00047 {
00048 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00049 
00050   /**
00051    *  Dynamic Bitset.
00052    *
00053    *  See N2050,
00054    *  Proposal to Add a Dynamically Sizeable Bitset to the Standard Library.
00055    */
00056 namespace __detail
00057 {
00058 
00059 template<typename T>
00060 class _Bool2UChar
00061 {
00062   typedef T type;
00063 };
00064 
00065 template<>
00066 class _Bool2UChar<bool>
00067 {
00068 public:
00069   typedef unsigned char type;
00070 };
00071 
00072 }
00073 
00074   /**
00075    *  Base class, general case.
00076    *
00077    *  See documentation for dynamic_bitset.
00078    */
00079   template<typename _WordT = unsigned long long,
00080        typename _Alloc = std::allocator<_WordT>>
00081     struct __dynamic_bitset_base
00082     {
00083       static_assert(std::is_unsigned<_WordT>::value, "template argument "
00084             "_WordT not an unsigned integral type");
00085 
00086       typedef _WordT block_type;
00087       typedef _Alloc allocator_type;
00088       typedef size_t size_type;
00089 
00090       static const size_type _S_bits_per_block = __CHAR_BIT__ * sizeof(block_type);
00091       static const size_type npos = static_cast<size_type>(-1);
00092 
00093       /// 0 is the least significant word.
00094       std::vector<block_type, allocator_type> _M_w;
00095 
00096       explicit
00097       __dynamic_bitset_base(const allocator_type& __alloc = allocator_type())
00098       : _M_w(__alloc)
00099       { }
00100 
00101       explicit
00102       __dynamic_bitset_base(__dynamic_bitset_base&& __b)
00103       { this->_M_w.swap(__b._M_w); }
00104 
00105       explicit
00106       __dynamic_bitset_base(size_type __nbits, unsigned long long __val = 0ULL,
00107                const allocator_type& __alloc = allocator_type())
00108       : _M_w(__nbits / _S_bits_per_block
00109          + (__nbits % _S_bits_per_block > 0),
00110          __val, __alloc)
00111       {
00112     unsigned long long __mask = ~static_cast<block_type>(0);
00113     size_t __n = std::min(this->_M_w.size(),
00114                   sizeof(unsigned long long) / sizeof(block_type));
00115     for (size_t __i = 0; __i < __n; ++__i)
00116       {
00117         this->_M_w[__i] = (__val & __mask) >> (__i * _S_bits_per_block);
00118         __mask <<= _S_bits_per_block;
00119       }
00120       }
00121 
00122       void
00123       _M_assign(const __dynamic_bitset_base& __b)
00124       { this->_M_w = __b._M_w; }
00125 
00126       void
00127       _M_swap(__dynamic_bitset_base& __b)
00128       { this->_M_w.swap(__b._M_w); }
00129 
00130       void
00131       _M_clear()
00132       { this->_M_w.clear(); }
00133 
00134       void
00135       _M_resize(size_t __nbits, bool __value)
00136       {
00137     size_t __sz = __nbits / _S_bits_per_block;
00138     if (__nbits % _S_bits_per_block > 0)
00139       ++__sz;
00140     if (__sz != this->_M_w.size())
00141       this->_M_w.resize(__sz);
00142       }
00143 
00144       allocator_type
00145       _M_get_allocator() const
00146       { return this->_M_w.get_allocator(); }
00147 
00148       static size_type
00149       _S_whichword(size_type __pos)
00150       { return __pos / _S_bits_per_block; }
00151 
00152       static size_type
00153       _S_whichbyte(size_type __pos)
00154       { return (__pos % _S_bits_per_block) / __CHAR_BIT__; }
00155 
00156       static size_type
00157       _S_whichbit(size_type __pos)
00158       { return __pos % _S_bits_per_block; }
00159 
00160       static block_type
00161       _S_maskbit(size_type __pos)
00162       { return (static_cast<block_type>(1)) << _S_whichbit(__pos); }
00163 
00164       block_type&
00165       _M_getword(size_type __pos)
00166       { return this->_M_w[_S_whichword(__pos)]; }
00167 
00168       block_type
00169       _M_getword(size_type __pos) const
00170       { return this->_M_w[_S_whichword(__pos)]; }
00171 
00172       block_type&
00173       _M_hiword()
00174       { return this->_M_w[_M_w.size() - 1]; }
00175 
00176       block_type
00177       _M_hiword() const
00178       { return this->_M_w[_M_w.size() - 1]; }
00179 
00180       void
00181       _M_do_and(const __dynamic_bitset_base& __x)
00182       {
00183     if (__x._M_w.size() == this->_M_w.size())
00184       for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00185         this->_M_w[__i] &= __x._M_w[__i];
00186     else
00187       return;
00188       }
00189 
00190       void
00191       _M_do_or(const __dynamic_bitset_base& __x)
00192       {
00193     if (__x._M_w.size() == this->_M_w.size())
00194       for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00195         this->_M_w[__i] |= __x._M_w[__i];
00196     else
00197       return;
00198       }
00199 
00200       void
00201       _M_do_xor(const __dynamic_bitset_base& __x)
00202       {
00203     if (__x._M_w.size() == this->_M_w.size())
00204       for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00205         this->_M_w[__i] ^= __x._M_w[__i];
00206     else
00207       return;
00208       }
00209 
00210       void
00211       _M_do_dif(const __dynamic_bitset_base& __x)
00212       {
00213     if (__x._M_w.size() == this->_M_w.size())
00214       for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00215         this->_M_w[__i] &= ~__x._M_w[__i];
00216     else
00217       return;
00218       }
00219 
00220       void
00221       _M_do_left_shift(size_t __shift);
00222 
00223       void
00224       _M_do_right_shift(size_t __shift);
00225 
00226       void
00227       _M_do_flip()
00228       {
00229     for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00230       this->_M_w[__i] = ~this->_M_w[__i];
00231       }
00232 
00233       void
00234       _M_do_set()
00235       {
00236     for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00237       this->_M_w[__i] = ~static_cast<block_type>(0);
00238       }
00239 
00240       void
00241       _M_do_reset()
00242       {
00243     for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00244       this->_M_w[__i] = static_cast<block_type>(0);
00245       }
00246 
00247       bool
00248       _M_is_equal(const __dynamic_bitset_base& __x) const
00249       {
00250     if (__x.size() == this->size())
00251       {
00252         for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00253           if (this->_M_w[__i] != __x._M_w[__i])
00254         return false;
00255         return true;
00256       }
00257     else
00258       return false;
00259       }
00260 
00261       bool
00262       _M_is_less(const __dynamic_bitset_base& __x) const
00263       {
00264     if (__x.size() == this->size())
00265       {
00266         for (size_t __i = this->_M_w.size(); __i > 0; --__i)
00267           {
00268         if (this->_M_w[__i-1] < __x._M_w[__i-1])
00269           return true;
00270         else if (this->_M_w[__i-1] > __x._M_w[__i-1])
00271           return false;
00272           }
00273         return false;
00274       }
00275     else
00276       return false;
00277       }
00278 
00279       size_t
00280       _M_are_all_aux() const
00281       {
00282     for (size_t __i = 0; __i < this->_M_w.size() - 1; ++__i)
00283       if (_M_w[__i] != ~static_cast<block_type>(0))
00284         return 0;
00285     return ((this->_M_w.size() - 1) * _S_bits_per_block
00286         + __builtin_popcountl(this->_M_hiword()));
00287       }
00288 
00289       bool
00290       _M_is_any() const
00291       {
00292     for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00293       if (this->_M_w[__i] != static_cast<block_type>(0))
00294         return true;
00295     return false;
00296       }
00297 
00298       bool
00299       _M_is_subset_of(const __dynamic_bitset_base& __b)
00300       {
00301     if (__b.size() == this->size())
00302       {
00303         for (size_t __i = 0; __i < _M_w.size(); ++__i)
00304           if (this->_M_w[__i] != (this->_M_w[__i] | __b._M_w[__i]))
00305         return false;
00306         return true;
00307       }
00308     else
00309       return false;
00310       }
00311 
00312       bool
00313       _M_is_proper_subset_of(const __dynamic_bitset_base& __b) const
00314       {
00315     if (this->is_subset_of(__b))
00316       {
00317         if (*this == __b)
00318           return false;
00319         else
00320           return true;
00321       }
00322     else
00323       return false;
00324       }
00325 
00326       size_t
00327       _M_do_count() const
00328       {
00329     size_t __result = 0;
00330     for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00331       __result += __builtin_popcountl(this->_M_w[__i]);
00332     return __result;
00333       }
00334 
00335       size_type
00336       _M_size() const
00337       { return this->_M_w.size(); }
00338 
00339       unsigned long
00340       _M_do_to_ulong() const;
00341 
00342       unsigned long long
00343       _M_do_to_ullong() const;
00344 
00345       // find first "on" bit
00346       size_type
00347       _M_do_find_first(size_t __not_found) const;
00348 
00349       // find the next "on" bit that follows "prev"
00350       size_type
00351       _M_do_find_next(size_t __prev, size_t __not_found) const;
00352 
00353       // do append of block
00354       void
00355       _M_do_append_block(block_type __block, size_type __pos)
00356       {
00357     size_t __offset = __pos % _S_bits_per_block;
00358     if (__offset == 0)
00359       this->_M_w.push_back(__block);
00360     else
00361       {
00362         this->_M_hiword() |= (__block << __offset);
00363         this->_M_w.push_back(__block >> (_S_bits_per_block - __offset));
00364       }
00365       }
00366     };
00367 
00368   // Definitions of non-inline functions from __dynamic_bitset_base.
00369   template<typename _WordT, typename _Alloc>
00370     void
00371     __dynamic_bitset_base<_WordT, _Alloc>::_M_do_left_shift(size_t __shift)
00372     {
00373       if (__builtin_expect(__shift != 0, 1))
00374     {
00375       const size_t __wshift = __shift / _S_bits_per_block;
00376       const size_t __offset = __shift % _S_bits_per_block;
00377 
00378       if (__offset == 0)
00379         for (size_t __n = this->_M_w.size() - 1; __n >= __wshift; --__n)
00380           this->_M_w[__n] = this->_M_w[__n - __wshift];
00381       else
00382         {
00383           const size_t __sub_offset = _S_bits_per_block - __offset;
00384           for (size_t __n = _M_w.size() - 1; __n > __wshift; --__n)
00385         this->_M_w[__n] = ((this->_M_w[__n - __wshift] << __offset)
00386                  | (this->_M_w[__n - __wshift - 1] >> __sub_offset));
00387           this->_M_w[__wshift] = this->_M_w[0] << __offset;
00388         }
00389 
00390       //// std::fill(this->_M_w.begin(), this->_M_w.begin() + __wshift,
00391       ////          static_cast<_WordT>(0));
00392     }
00393     }
00394 
00395   template<typename _WordT, typename _Alloc>
00396     void
00397     __dynamic_bitset_base<_WordT, _Alloc>::_M_do_right_shift(size_t __shift)
00398     {
00399       if (__builtin_expect(__shift != 0, 1))
00400     {
00401       const size_t __wshift = __shift / _S_bits_per_block;
00402       const size_t __offset = __shift % _S_bits_per_block;
00403       const size_t __limit = this->_M_w.size() - __wshift - 1;
00404 
00405       if (__offset == 0)
00406         for (size_t __n = 0; __n <= __limit; ++__n)
00407           this->_M_w[__n] = this->_M_w[__n + __wshift];
00408       else
00409         {
00410           const size_t __sub_offset = (_S_bits_per_block
00411                        - __offset);
00412           for (size_t __n = 0; __n < __limit; ++__n)
00413         this->_M_w[__n] = ((this->_M_w[__n + __wshift] >> __offset)
00414                  | (this->_M_w[__n + __wshift + 1] << __sub_offset));
00415           this->_M_w[__limit] = this->_M_w[_M_w.size()-1] >> __offset;
00416         }
00417 
00418       ////std::fill(this->_M_w.begin() + __limit + 1, this->_M_w.end(),
00419       ////          static_cast<_WordT>(0));
00420     }
00421     }
00422 
00423   template<typename _WordT, typename _Alloc>
00424     unsigned long
00425     __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ulong() const
00426     {
00427       size_t __n = sizeof(unsigned long) / sizeof(block_type);
00428       for (size_t __i = __n; __i < this->_M_w.size(); ++__i)
00429     if (this->_M_w[__i])
00430       __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ulong"));
00431       unsigned long __res = 0UL;
00432       for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
00433     __res += this->_M_w[__i] << (__i * _S_bits_per_block);
00434       return __res;
00435     }
00436 
00437   template<typename _WordT, typename _Alloc>
00438     unsigned long long
00439     __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ullong() const
00440     {
00441       size_t __n = sizeof(unsigned long long) / sizeof(block_type);
00442       for (size_t __i = __n; __i < this->_M_w.size(); ++__i)
00443     if (this->_M_w[__i])
00444       __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ullong"));
00445       unsigned long long __res = 0ULL;
00446       for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
00447     __res += this->_M_w[__i] << (__i * _S_bits_per_block);
00448       return __res;
00449     }
00450 
00451   template<typename _WordT, typename _Alloc>
00452     size_t
00453     __dynamic_bitset_base<_WordT, _Alloc>
00454     ::_M_do_find_first(size_t __not_found) const
00455     {
00456       for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
00457     {
00458       _WordT __thisword = this->_M_w[__i];
00459       if (__thisword != static_cast<_WordT>(0))
00460         return (__i * _S_bits_per_block
00461             + __builtin_ctzl(__thisword));
00462     }
00463       // not found, so return an indication of failure.
00464       return __not_found;
00465     }
00466 
00467   template<typename _WordT, typename _Alloc>
00468     size_t
00469     __dynamic_bitset_base<_WordT, _Alloc>
00470     ::_M_do_find_next(size_t __prev, size_t __not_found) const
00471     {
00472       // make bound inclusive
00473       ++__prev;
00474 
00475       // check out of bounds
00476       if (__prev >= this->_M_w.size() * _S_bits_per_block)
00477     return __not_found;
00478 
00479       // search first word
00480       size_t __i = _S_whichword(__prev);
00481       _WordT __thisword = this->_M_w[__i];
00482 
00483       // mask off bits below bound
00484       __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
00485 
00486       if (__thisword != static_cast<_WordT>(0))
00487     return (__i * _S_bits_per_block
00488         + __builtin_ctzl(__thisword));
00489 
00490       // check subsequent words
00491       for (++__i; __i < this->_M_w.size(); ++__i)
00492     {
00493       __thisword = this->_M_w[__i];
00494       if (__thisword != static_cast<_WordT>(0))
00495         return (__i * _S_bits_per_block
00496             + __builtin_ctzl(__thisword));
00497     }
00498       // not found, so return an indication of failure.
00499       return __not_found;
00500     } // end _M_do_find_next
00501 
00502   /**
00503    *  @brief  The %dynamic_bitset class represents a sequence of bits.
00504    *
00505    *  @ingroup containers
00506    *
00507    *  (Note that %dynamic_bitset does @e not meet the formal
00508    *  requirements of a <a href="tables.html#65">container</a>.
00509    *  Mainly, it lacks iterators.)
00510    *
00511    *  The template argument, @a Nb, may be any non-negative number,
00512    *  specifying the number of bits (e.g., "0", "12", "1024*1024").
00513    *
00514    *  In the general unoptimized case, storage is allocated in
00515    *  word-sized blocks.  Let B be the number of bits in a word, then
00516    *  (Nb+(B-1))/B words will be used for storage.  B - Nb%B bits are
00517    *  unused.  (They are the high-order bits in the highest word.)  It
00518    *  is a class invariant that those unused bits are always zero.
00519    *
00520    *  If you think of %dynamic_bitset as "a simple array of bits," be
00521    *  aware that your mental picture is reversed: a %dynamic_bitset
00522    *  behaves the same way as bits in integers do, with the bit at
00523    *  index 0 in the "least significant / right-hand" position, and
00524    *  the bit at index Nb-1 in the "most significant / left-hand"
00525    *  position.  Thus, unlike other containers, a %dynamic_bitset's
00526    *  index "counts from right to left," to put it very loosely.
00527    *
00528    *  This behavior is preserved when translating to and from strings.
00529    *  For example, the first line of the following program probably
00530    *  prints "b('a') is 0001100001" on a modern ASCII system.
00531    *
00532    *  @code
00533    *     #include <dynamic_bitset>
00534    *     #include <iostream>
00535    *     #include <sstream>
00536    *
00537    *     using namespace std;
00538    *
00539    *     int main()
00540    *     {
00541    *         long         a = 'a';
00542    *         dynamic_bitset   b(a);
00543    *
00544    *         cout << "b('a') is " << b << endl;
00545    *
00546    *         ostringstream s;
00547    *         s << b;
00548    *         string  str = s.str();
00549    *         cout << "index 3 in the string is " << str[3] << " but\n"
00550    *              << "index 3 in the bitset is " << b[3] << endl;
00551    *     }
00552    *  @endcode
00553    *
00554    *  Also see:
00555    *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch33s02.html
00556    *  for a description of extensions.
00557    *
00558    *  Most of the actual code isn't contained in %dynamic_bitset<>
00559    *  itself, but in the base class __dynamic_bitset_base.  The base
00560    *  class works with whole words, not with individual bits.  This
00561    *  allows us to specialize __dynamic_bitset_base for the important
00562    *  special case where the %dynamic_bitset is only a single word.
00563    *
00564    *  Extra confusion can result due to the fact that the storage for
00565    *  __dynamic_bitset_base @e is a vector, and is indexed as such.  This is
00566    *  carefully encapsulated.
00567    */
00568   template<typename _WordT = unsigned long long,
00569        typename _Alloc = std::allocator<_WordT>>
00570     class dynamic_bitset
00571     : private __dynamic_bitset_base<_WordT, _Alloc>
00572     {
00573       static_assert(std::is_unsigned<_WordT>::value, "template argument "
00574             "_WordT not an unsigned integral type");
00575 
00576     public:
00577 
00578       typedef __dynamic_bitset_base<_WordT, _Alloc> _Base;
00579       typedef _WordT block_type;
00580       typedef _Alloc allocator_type;
00581       typedef size_t size_type;
00582 
00583       static const size_type bits_per_block = __CHAR_BIT__ * sizeof(block_type);
00584       // Use this: constexpr size_type std::numeric_limits<size_type>::max().
00585       static const size_type npos = static_cast<size_type>(-1);
00586 
00587     private:
00588 
00589       //  Clear the unused bits in the uppermost word.
00590       void
00591       _M_do_sanitize()
00592       {
00593     size_type __shift = this->_M_Nb % bits_per_block;
00594     if (__shift > 0)
00595       this->_M_hiword() &= ~((~static_cast<block_type>(0)) << __shift);
00596       }
00597 
00598       /**
00599        *  These versions of single-bit set, reset, flip, and test
00600        *  do no range checking.
00601        */
00602       dynamic_bitset<_WordT, _Alloc>&
00603       _M_unchecked_set(size_type __pos)
00604       {
00605     this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
00606     return *this;
00607       }
00608 
00609       dynamic_bitset<_WordT, _Alloc>&
00610       _M_unchecked_set(size_type __pos, int __val)
00611       {
00612     if (__val)
00613       this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
00614     else
00615       this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
00616     return *this;
00617       }
00618 
00619       dynamic_bitset<_WordT, _Alloc>&
00620       _M_unchecked_reset(size_type __pos)
00621       {
00622     this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
00623     return *this;
00624       }
00625 
00626       dynamic_bitset<_WordT, _Alloc>&
00627       _M_unchecked_flip(size_type __pos)
00628       {
00629     this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
00630     return *this;
00631       }
00632 
00633       bool
00634       _M_unchecked_test(size_type __pos) const
00635       { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
00636         != static_cast<_WordT>(0)); }
00637 
00638       size_type _M_Nb;
00639 
00640     public:
00641       /**
00642        *  This encapsulates the concept of a single bit.  An instance
00643        *  of this class is a proxy for an actual bit; this way the
00644        *  individual bit operations are done as faster word-size
00645        *  bitwise instructions.
00646        *
00647        *  Most users will never need to use this class directly;
00648        *  conversions to and from bool are automatic and should be
00649        *  transparent.  Overloaded operators help to preserve the
00650        *  illusion.
00651        *
00652        *  (On a typical system, this "bit %reference" is 64 times the
00653        *  size of an actual bit.  Ha.)
00654        */
00655       class reference
00656       {
00657     friend class dynamic_bitset;
00658 
00659     block_type *_M_wp;
00660     size_type _M_bpos;
00661 
00662     // left undefined
00663     reference();
00664 
00665       public:
00666     reference(dynamic_bitset& __b, size_type __pos)
00667     {
00668       this->_M_wp = &__b._M_getword(__pos);
00669       this->_M_bpos = _Base::_S_whichbit(__pos);
00670     }
00671 
00672     ~reference()
00673     { }
00674 
00675     // For b[i] = __x;
00676     reference&
00677     operator=(bool __x)
00678     {
00679       if (__x)
00680         *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
00681       else
00682         *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
00683       return *this;
00684     }
00685 
00686     // For b[i] = b[__j];
00687     reference&
00688     operator=(const reference& __j)
00689     {
00690       if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
00691         *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
00692       else
00693         *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
00694       return *this;
00695     }
00696 
00697     // Flips the bit
00698     bool
00699     operator~() const
00700     { return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; }
00701 
00702     // For __x = b[i];
00703     operator bool() const
00704     { return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; }
00705 
00706     // For b[i].flip();
00707     reference&
00708     flip()
00709     {
00710       *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos);
00711       return *this;
00712     }
00713       };
00714 
00715       friend class reference;
00716 
00717       typedef bool const_reference;
00718 
00719       // 23.3.5.1 constructors:
00720       /// All bits set to zero.
00721       explicit
00722       dynamic_bitset(const allocator_type& __alloc = allocator_type())
00723       : _Base(__alloc), _M_Nb(0)
00724       { }
00725 
00726       /// Initial bits bitwise-copied from a single word (others set to zero).
00727       explicit
00728       dynamic_bitset(size_type __nbits, unsigned long long __val = 0ULL,
00729              const allocator_type& __alloc = allocator_type())
00730       : _Base(__nbits, __val, __alloc),
00731     _M_Nb(__nbits)
00732       { }
00733 
00734       dynamic_bitset(initializer_list<block_type> __il,
00735              const allocator_type& __alloc = allocator_type())
00736       : _Base(__alloc), _M_Nb(0)
00737       { this->append(__il); }
00738 
00739       /**
00740        *  @brief  Use a subset of a string.
00741        *  @param  __str  A string of '0' and '1' characters.
00742        *  @param  __pos  Index of the first character in @p __str to use.
00743        *  @param  __n    The number of characters to copy.
00744        *  @throw  std::out_of_range  If @p __pos is bigger the size of @p __str.
00745        *  @throw  std::invalid_argument  If a character appears in the string
00746        *                                 which is neither '0' nor '1'.
00747        */
00748       template<typename _CharT, typename _Traits, typename _Alloc1>
00749     explicit
00750     dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc1>& __str,
00751                typename basic_string<_CharT,_Traits,_Alloc1>::size_type
00752                __pos = 0,
00753                typename basic_string<_CharT,_Traits,_Alloc1>::size_type
00754                __n = std::basic_string<_CharT, _Traits, _Alloc1>::npos,
00755                _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'),
00756                const allocator_type& __alloc = allocator_type())
00757     : _Base(__alloc),
00758       _M_Nb(0) // Watch for npos.
00759     {
00760       if (__pos > __str.size())
00761         __throw_out_of_range(__N("dynamic_bitset::bitset initial position "
00762                      "not valid"));
00763 
00764       // Watch for npos.
00765       this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n);
00766       this->resize(this->_M_Nb);
00767       this->_M_copy_from_string(__str, __pos, __n,
00768                     _CharT('0'), _CharT('1'));
00769     }
00770 
00771       /**
00772        *  @brief  Construct from a string.
00773        *  @param  __str  A string of '0' and '1' characters.
00774        *  @throw  std::invalid_argument  If a character appears in the string
00775        *                                 which is neither '0' nor '1'.
00776        */
00777       explicit
00778       dynamic_bitset(const char* __str,
00779              const allocator_type& __alloc = allocator_type())
00780       : _Base(__alloc)
00781       {
00782     size_t __len = 0;
00783     if (__str)
00784       while (__str[__len] != '\0')
00785         ++__len;
00786     this->resize(__len);
00787     this->_M_copy_from_ptr<char,std::char_traits<char>>
00788            (__str, __len, 0, __len, '0', '1');
00789       }
00790 
00791       /**
00792        *  @brief  Copy constructor.
00793        */
00794       dynamic_bitset(const dynamic_bitset& __b)
00795       : _Base(__b), _M_Nb(__b.size())
00796       { }
00797 
00798       /**
00799        *  @brief  Move constructor.
00800        */
00801       dynamic_bitset(dynamic_bitset&& __b)
00802       : _Base(std::forward<_Base>(__b)), _M_Nb(__b.size())
00803       { }
00804 
00805       /**
00806        *  @brief  Swap with another bitset.
00807        */
00808       void
00809       swap(dynamic_bitset& __b)
00810       {
00811     this->_M_swap(__b);
00812     std::swap(this->_M_Nb, __b._M_Nb);
00813       }
00814 
00815       /**
00816        *  @brief  Assignment.
00817        */
00818       dynamic_bitset&
00819       operator=(const dynamic_bitset& __b)
00820       {
00821     if (&__b != this)
00822       {
00823         this->_M_assign(__b);
00824         this->_M_Nb = __b._M_Nb;
00825       }
00826       }
00827 
00828       /**
00829        *  @brief  Move assignment.
00830        */
00831       dynamic_bitset&
00832       operator=(dynamic_bitset&& __b)
00833       {
00834     this->swap(__b);
00835     return *this;
00836       }
00837 
00838       /**
00839        *  @brief  Return the allocator for the bitset.
00840        */
00841       allocator_type
00842       get_allocator() const
00843       { return this->_M_get_allocator(); }
00844 
00845       /**
00846        *  @brief  Resize the bitset.
00847        */
00848       void
00849       resize(size_type __nbits, bool __value = false)
00850       {
00851     this->_M_resize(__nbits, __value);
00852     this->_M_Nb = __nbits;
00853     this->_M_do_sanitize();
00854       }
00855 
00856       /**
00857        *  @brief  Clear the bitset.
00858        */
00859       void
00860       clear()
00861       {
00862     this->_M_clear();
00863     this->_M_Nb = 0;
00864       }
00865 
00866       /**
00867        *  @brief  Push a bit onto the high end of the bitset.
00868        */
00869       void
00870       push_back(bool __bit)
00871       {
00872     if (size_t __offset = this->size() % bits_per_block == 0)
00873       this->_M_do_append_block(block_type(0), this->_M_Nb);
00874     ++this->_M_Nb;
00875     this->_M_unchecked_set(this->_M_Nb, __bit);
00876       }
00877 
00878       /**
00879        *  @brief  Append a block.
00880        */
00881       void
00882       append(block_type __block)
00883       {
00884     this->_M_do_append_block(__block, this->_M_Nb);
00885     this->_M_Nb += bits_per_block;
00886       }
00887 
00888       /**
00889        *  @brief
00890        */
00891       void
00892       append(initializer_list<block_type> __il)
00893       { this->append(__il.begin(), __il.end()); }
00894 
00895       /**
00896        *  @brief  Append an iterator range of blocks.
00897        */
00898       template <typename _BlockInputIterator>
00899     void
00900     append(_BlockInputIterator __first, _BlockInputIterator __last)
00901     {
00902       for (; __first != __last; ++__first)
00903         this->append(*__first);
00904     }
00905 
00906       // 23.3.5.2 dynamic_bitset operations:
00907       //@{
00908       /**
00909        *  @brief  Operations on dynamic_bitsets.
00910        *  @param  __rhs  A same-sized dynamic_bitset.
00911        *
00912        *  These should be self-explanatory.
00913        */
00914       dynamic_bitset<_WordT, _Alloc>&
00915       operator&=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
00916       {
00917     this->_M_do_and(__rhs);
00918     return *this;
00919       }
00920 
00921       dynamic_bitset<_WordT, _Alloc>&
00922       operator&=(dynamic_bitset<_WordT, _Alloc>&& __rhs)
00923       {
00924     this->_M_do_and(std::move(__rhs));
00925     return *this;
00926       }
00927 
00928       dynamic_bitset<_WordT, _Alloc>&
00929       operator|=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
00930       {
00931     this->_M_do_or(__rhs);
00932     return *this;
00933       }
00934 
00935       dynamic_bitset<_WordT, _Alloc>&
00936       operator^=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
00937       {
00938     this->_M_do_xor(__rhs);
00939     return *this;
00940       }
00941 
00942       dynamic_bitset<_WordT, _Alloc>&
00943       operator-=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
00944       {
00945     this->_M_do_dif(__rhs);
00946     return *this;
00947       }
00948       //@}
00949 
00950       //@{
00951       /**
00952        *  @brief  Operations on dynamic_bitsets.
00953        *  @param  __pos The number of places to shift.
00954        *
00955        *  These should be self-explanatory.
00956        */
00957       dynamic_bitset<_WordT, _Alloc>&
00958       operator<<=(size_type __pos)
00959       {
00960     if (__builtin_expect(__pos < this->_M_Nb, 1))
00961       {
00962         this->_M_do_left_shift(__pos);
00963         this->_M_do_sanitize();
00964       }
00965     else
00966       this->_M_do_reset();
00967     return *this;
00968       }
00969 
00970       dynamic_bitset<_WordT, _Alloc>&
00971       operator>>=(size_type __pos)
00972       {
00973     if (__builtin_expect(__pos < this->_M_Nb, 1))
00974       {
00975         this->_M_do_right_shift(__pos);
00976         this->_M_do_sanitize();
00977       }
00978     else
00979       this->_M_do_reset();
00980     return *this;
00981       }
00982       //@}
00983 
00984       // Set, reset, and flip.
00985       /**
00986        *  @brief Sets every bit to true.
00987        */
00988       dynamic_bitset<_WordT, _Alloc>&
00989       set()
00990       {
00991     this->_M_do_set();
00992     this->_M_do_sanitize();
00993     return *this;
00994       }
00995 
00996       /**
00997        *  @brief Sets a given bit to a particular value.
00998        *  @param  __pos  The index of the bit.
00999        *  @param  __val  Either true or false, defaults to true.
01000        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
01001        */
01002       dynamic_bitset<_WordT, _Alloc>&
01003       set(size_type __pos, bool __val = true)
01004       {
01005     if (__pos >= _M_Nb)
01006       __throw_out_of_range(__N("dynamic_bitset::set"));
01007     return this->_M_unchecked_set(__pos, __val);
01008       }
01009 
01010       /**
01011        *  @brief Sets every bit to false.
01012        */
01013       dynamic_bitset<_WordT, _Alloc>&
01014       reset()
01015       {
01016     this->_M_do_reset();
01017     return *this;
01018       }
01019 
01020       /**
01021        *  @brief Sets a given bit to false.
01022        *  @param  __pos  The index of the bit.
01023        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
01024        *
01025        *  Same as writing @c set(__pos, false).
01026        */
01027       dynamic_bitset<_WordT, _Alloc>&
01028       reset(size_type __pos)
01029       {
01030     if (__pos >= _M_Nb)
01031       __throw_out_of_range(__N("dynamic_bitset::reset"));
01032     return this->_M_unchecked_reset(__pos);
01033       }
01034 
01035       /**
01036        *  @brief Toggles every bit to its opposite value.
01037        */
01038       dynamic_bitset<_WordT, _Alloc>&
01039       flip()
01040       {
01041     this->_M_do_flip();
01042     this->_M_do_sanitize();
01043     return *this;
01044       }
01045 
01046       /**
01047        *  @brief Toggles a given bit to its opposite value.
01048        *  @param  __pos  The index of the bit.
01049        *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
01050        */
01051       dynamic_bitset<_WordT, _Alloc>&
01052       flip(size_type __pos)
01053       {
01054     if (__pos >= _M_Nb)
01055       __throw_out_of_range(__N("dynamic_bitset::flip"));
01056     return this->_M_unchecked_flip(__pos);
01057       }
01058 
01059       /// See the no-argument flip().
01060       dynamic_bitset<_WordT, _Alloc>
01061       operator~() const
01062       { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); }
01063 
01064       //@{
01065       /**
01066        *  @brief  Array-indexing support.
01067        *  @param  __pos  Index into the %dynamic_bitset.
01068        *  @return A bool for a 'const %dynamic_bitset'.  For non-const
01069        *           bitsets, an instance of the reference proxy class.
01070        *  @note These operators do no range checking and throw no
01071        *         exceptions, as required by DR 11 to the standard.
01072        */
01073       reference
01074       operator[](size_type __pos)
01075       { return reference(*this,__pos); }
01076 
01077       const_reference
01078       operator[](size_type __pos) const
01079       { return _M_unchecked_test(__pos); }
01080       //@}
01081 
01082       /**
01083        *  @brief Returns a numerical interpretation of the %dynamic_bitset.
01084        *  @return  The integral equivalent of the bits.
01085        *  @throw  std::overflow_error  If there are too many bits to be
01086        *                               represented in an @c unsigned @c long.
01087        */
01088       unsigned long
01089       to_ulong() const
01090       { return this->_M_do_to_ulong(); }
01091 
01092       /**
01093        *  @brief Returns a numerical interpretation of the %dynamic_bitset.
01094        *  @return  The integral equivalent of the bits.
01095        *  @throw  std::overflow_error  If there are too many bits to be
01096        *                               represented in an @c unsigned @c long.
01097        */
01098       unsigned long long
01099       to_ullong() const
01100       { return this->_M_do_to_ullong(); }
01101 
01102       /**
01103        *  @brief Returns a character interpretation of the %dynamic_bitset.
01104        *  @return  The string equivalent of the bits.
01105        *
01106        *  Note the ordering of the bits:  decreasing character positions
01107        *  correspond to increasing bit positions (see the main class notes for
01108        *  an example).
01109        */
01110       template<typename _CharT = char,
01111            typename _Traits = std::char_traits<_CharT>,
01112            typename _Alloc1 = std::allocator<_CharT>>
01113     std::basic_string<_CharT, _Traits, _Alloc1>
01114     to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const
01115     {
01116       std::basic_string<_CharT, _Traits, _Alloc1> __result;
01117       _M_copy_to_string(__result, __zero, __one);
01118       return __result;
01119     }
01120 
01121       // Helper functions for string operations.
01122       template<typename _CharT, typename _Traits>
01123     void
01124     _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
01125              _CharT, _CharT);
01126 
01127       template<typename _CharT, typename _Traits, typename _Alloc1>
01128     void
01129     _M_copy_from_string(const std::basic_string<_CharT,
01130                 _Traits, _Alloc1>& __str, size_t __pos, size_t __n,
01131                 _CharT __zero = _CharT('0'),
01132                 _CharT __one = _CharT('1'))
01133     { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(),
01134                         __pos, __n, __zero, __one); }
01135 
01136       template<typename _CharT, typename _Traits, typename _Alloc1>
01137     void
01138     _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
01139               _CharT __zero = _CharT('0'),
01140               _CharT __one = _CharT('1')) const;
01141 
01142       /// Returns the number of bits which are set.
01143       size_type
01144       count() const
01145       { return this->_M_do_count(); }
01146 
01147       /// Returns the total number of bits.
01148       size_type
01149       size() const
01150       { return this->_M_Nb; }
01151 
01152       /// Returns the total number of blocks.
01153       size_type num_blocks() const
01154       { return this->_M_size(); }
01155 
01156       /// Returns true if the dynamic_bitset is empty.
01157       bool
01158       empty() const
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() const
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 */