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