libstdc++-v3/include/std/bitset

   1 // <bitset> -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 3, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 /*
  27  * Copyright (c) 1998
  28  * Silicon Graphics Computer Systems, Inc.
  29  *
  30  * Permission to use, copy, modify, distribute and sell this software
  31  * and its documentation for any purpose is hereby granted without fee,
  32  * provided that the above copyright notice appear in all copies and
  33  * that both that copyright notice and this permission notice appear
  34  * in supporting documentation.  Silicon Graphics makes no
  35  * representations about the suitability of this software for any
  36  * purpose.  It is provided "as is" without express or implied warranty.
  37  */
  38
  39 /** @file include/bitset
  40  *  This is a Standard C++ Library header.
  41  */
  42
  43 #ifndef _GLIBCXX_BITSET
  44 #define _GLIBCXX_BITSET 1
  45
  46 #pragma GCC system_header
  47
  48 #include <cstddef>     // For size_t
  49 #include <string>
  50 #include <bits/functexcept.h>   // For invalid_argument, out_of_range,
  51                                 // overflow_error
  52 #include <iosfwd>
  53 #include <cxxabi-forced.h>
  54
  55 #define _GLIBCXX_BITSET_BITS_PER_WORD  (__CHAR_BIT__ * sizeof(unsigned long))
  56 #define _GLIBCXX_BITSET_WORDS(__n) \
  57  ((__n) < 1 ? 0 : ((__n) + _GLIBCXX_BITSET_BITS_PER_WORD - 1) \
  58                   / _GLIBCXX_BITSET_BITS_PER_WORD)
  59
  60 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
  61
  62   /**
  63    *  Base class, general case.  It is a class invariant that _Nw will be
  64    *  nonnegative.
  65    *
  66    *  See documentation for bitset.
  67   */
  68   template<size_t _Nw>
  69     struct _Base_bitset
  70     {
  71       typedef unsigned long _WordT;
  72
  73       /// 0 is the least significant word.
  74       _WordT            _M_w[_Nw];
  75
  76       _Base_bitset()
  77       { _M_do_reset(); }
  78
  79 #ifdef __GXX_EXPERIMENTAL_CXX0X__
  80       _Base_bitset(unsigned long long __val)
  81 #else
  82       _Base_bitset(unsigned long __val)
  83 #endif
  84       {
  85         _M_do_reset();
  86         _M_w[0] = __val;
  87 #ifdef __GXX_EXPERIMENTAL_CXX0X__
  88         if (sizeof(unsigned long long) > sizeof(unsigned long))
  89           _M_w[1] = __val >> _GLIBCXX_BITSET_BITS_PER_WORD;
  90 #endif
  91       }
  92
  93       static size_t
  94       _S_whichword(size_t __pos )
  95       { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
  96
  97       static size_t
  98       _S_whichbyte(size_t __pos )
  99       { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
 100
 101       static size_t
 102       _S_whichbit(size_t __pos )
 103       { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
 104
 105       static _WordT
 106       _S_maskbit(size_t __pos )
 107       { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
 108
 109       _WordT&
 110       _M_getword(size_t __pos)
 111       { return _M_w[_S_whichword(__pos)]; }
 112
 113       _WordT
 114       _M_getword(size_t __pos) const
 115       { return _M_w[_S_whichword(__pos)]; }
 116
 117 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 118       const char*
 119       _M_getdata() const
 120       { return reinterpret_cast<const char*>(_M_w); }
 121 #endif
 122
 123       _WordT&
 124       _M_hiword()
 125       { return _M_w[_Nw - 1]; }
 126
 127       _WordT
 128       _M_hiword() const
 129       { return _M_w[_Nw - 1]; }
 130
 131       void
 132       _M_do_and(const _Base_bitset<_Nw>& __x)
 133       {
 134         for (size_t __i = 0; __i < _Nw; __i++)
 135           _M_w[__i] &= __x._M_w[__i];
 136       }
 137
 138       void
 139       _M_do_or(const _Base_bitset<_Nw>& __x)
 140       {
 141         for (size_t __i = 0; __i < _Nw; __i++)
 142           _M_w[__i] |= __x._M_w[__i];
 143       }
 144
 145       void
 146       _M_do_xor(const _Base_bitset<_Nw>& __x)
 147       {
 148         for (size_t __i = 0; __i < _Nw; __i++)
 149           _M_w[__i] ^= __x._M_w[__i];
 150       }
 151
 152       void
 153       _M_do_left_shift(size_t __shift);
 154
 155       void
 156       _M_do_right_shift(size_t __shift);
 157
 158       void
 159       _M_do_flip()
 160       {
 161         for (size_t __i = 0; __i < _Nw; __i++)
 162           _M_w[__i] = ~_M_w[__i];
 163       }
 164
 165       void
 166       _M_do_set()
 167       {
 168         for (size_t __i = 0; __i < _Nw; __i++)
 169           _M_w[__i] = ~static_cast<_WordT>(0);
 170       }
 171
 172       void
 173       _M_do_reset()
 174       { __builtin_memset(_M_w, 0, _Nw * sizeof(_WordT)); }
 175
 176       bool
 177       _M_is_equal(const _Base_bitset<_Nw>& __x) const
 178       {
 179         for (size_t __i = 0; __i < _Nw; ++__i)
 180           if (_M_w[__i] != __x._M_w[__i])
 181             return false;
 182         return true;
 183       }
 184
 185       size_t
 186       _M_are_all_aux() const
 187       {
 188         for (size_t __i = 0; __i < _Nw - 1; __i++)
 189           if (_M_w[__i] != ~static_cast<_WordT>(0))
 190             return 0;
 191         return ((_Nw - 1) * _GLIBCXX_BITSET_BITS_PER_WORD
 192                 + __builtin_popcountl(_M_hiword()));
 193       }
 194
 195       bool
 196       _M_is_any() const
 197       {
 198         for (size_t __i = 0; __i < _Nw; __i++)
 199           if (_M_w[__i] != static_cast<_WordT>(0))
 200             return true;
 201         return false;
 202       }
 203
 204       size_t
 205       _M_do_count() const
 206       {
 207         size_t __result = 0;
 208         for (size_t __i = 0; __i < _Nw; __i++)
 209           __result += __builtin_popcountl(_M_w[__i]);
 210         return __result;
 211       }
 212
 213       unsigned long
 214       _M_do_to_ulong() const;
 215
 216 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 217       unsigned long long
 218       _M_do_to_ullong() const;
 219 #endif
 220
 221       // find first "on" bit
 222       size_t
 223       _M_do_find_first(size_t __not_found) const;
 224
 225       // find the next "on" bit that follows "prev"
 226       size_t
 227       _M_do_find_next(size_t __prev, size_t __not_found) const;
 228     };
 229
 230   // Definitions of non-inline functions from _Base_bitset.
 231   template<size_t _Nw>
 232     void
 233     _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift)
 234     {
 235       if (__builtin_expect(__shift != 0, 1))
 236         {
 237           const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
 238           const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
 239
 240           if (__offset == 0)
 241             for (size_t __n = _Nw - 1; __n >= __wshift; --__n)
 242               _M_w[__n] = _M_w[__n - __wshift];
 243           else
 244             {
 245               const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
 246                                            - __offset);
 247               for (size_t __n = _Nw - 1; __n > __wshift; --__n)
 248                 _M_w[__n] = ((_M_w[__n - __wshift] << __offset)
 249                              | (_M_w[__n - __wshift - 1] >> __sub_offset));
 250               _M_w[__wshift] = _M_w[0] << __offset;
 251             }
 252
 253           std::fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0));
 254         }
 255     }
 256
 257   template<size_t _Nw>
 258     void
 259     _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift)
 260     {
 261       if (__builtin_expect(__shift != 0, 1))
 262         {
 263           const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD;
 264           const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD;
 265           const size_t __limit = _Nw - __wshift - 1;
 266
 267           if (__offset == 0)
 268             for (size_t __n = 0; __n <= __limit; ++__n)
 269               _M_w[__n] = _M_w[__n + __wshift];
 270           else
 271             {
 272               const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD
 273                                            - __offset);
 274               for (size_t __n = 0; __n < __limit; ++__n)
 275                 _M_w[__n] = ((_M_w[__n + __wshift] >> __offset)
 276                              | (_M_w[__n + __wshift + 1] << __sub_offset));
 277               _M_w[__limit] = _M_w[_Nw-1] >> __offset;
 278             }
 279
 280           std::fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0));
 281         }
 282     }
 283
 284   template<size_t _Nw>
 285     unsigned long
 286     _Base_bitset<_Nw>::_M_do_to_ulong() const
 287     {
 288       for (size_t __i = 1; __i < _Nw; ++__i)
 289         if (_M_w[__i])
 290           __throw_overflow_error(__N("_Base_bitset::_M_do_to_ulong"));
 291       return _M_w[0];
 292     }
 293
 294 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 295   template<size_t _Nw>
 296     unsigned long long
 297     _Base_bitset<_Nw>::_M_do_to_ullong() const
 298     {
 299       const bool __dw = sizeof(unsigned long long) > sizeof(unsigned long);
 300       for (size_t __i = 1 + __dw; __i < _Nw; ++__i)
 301         if (_M_w[__i])
 302           __throw_overflow_error(__N("_Base_bitset::_M_do_to_ullong"));
 303
 304       if (__dw)
 305         return _M_w[0] + (static_cast<unsigned long long>(_M_w[1])
 306                           << _GLIBCXX_BITSET_BITS_PER_WORD);
 307       return _M_w[0];
 308     }
 309 #endif
 310
 311   template<size_t _Nw>
 312     size_t
 313     _Base_bitset<_Nw>::_M_do_find_first(size_t __not_found) const
 314     {
 315       for (size_t __i = 0; __i < _Nw; __i++)
 316         {
 317           _WordT __thisword = _M_w[__i];
 318           if (__thisword != static_cast<_WordT>(0))
 319             return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
 320                     + __builtin_ctzl(__thisword));
 321         }
 322       // not found, so return an indication of failure.
 323       return __not_found;
 324     }
 325
 326   template<size_t _Nw>
 327     size_t
 328     _Base_bitset<_Nw>::_M_do_find_next(size_t __prev, size_t __not_found) const
 329     {
 330       // make bound inclusive
 331       ++__prev;
 332
 333       // check out of bounds
 334       if (__prev >= _Nw * _GLIBCXX_BITSET_BITS_PER_WORD)
 335         return __not_found;
 336
 337       // search first word
 338       size_t __i = _S_whichword(__prev);
 339       _WordT __thisword = _M_w[__i];
 340
 341       // mask off bits below bound
 342       __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
 343
 344       if (__thisword != static_cast<_WordT>(0))
 345         return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
 346                 + __builtin_ctzl(__thisword));
 347
 348       // check subsequent words
 349       __i++;
 350       for (; __i < _Nw; __i++)
 351         {
 352           __thisword = _M_w[__i];
 353           if (__thisword != static_cast<_WordT>(0))
 354             return (__i * _GLIBCXX_BITSET_BITS_PER_WORD
 355                     + __builtin_ctzl(__thisword));
 356         }
 357       // not found, so return an indication of failure.
 358       return __not_found;
 359     } // end _M_do_find_next
 360
 361   /**
 362    *  Base class, specialization for a single word.
 363    *
 364    *  See documentation for bitset.
 365   */
 366   template<>
 367     struct _Base_bitset<1>
 368     {
 369       typedef unsigned long _WordT;
 370       _WordT _M_w;
 371
 372       _Base_bitset(void)
 373       : _M_w(0)
 374       { }
 375
 376 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 377       _Base_bitset(unsigned long long __val)
 378 #else
 379       _Base_bitset(unsigned long __val)
 380 #endif
 381       : _M_w(__val)
 382       { }
 383
 384       static size_t
 385       _S_whichword(size_t __pos )
 386       { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
 387
 388       static size_t
 389       _S_whichbyte(size_t __pos )
 390       { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
 391
 392       static size_t
 393       _S_whichbit(size_t __pos )
 394       {  return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
 395
 396       static _WordT
 397       _S_maskbit(size_t __pos )
 398       { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
 399
 400       _WordT&
 401       _M_getword(size_t)
 402       { return _M_w; }
 403
 404       _WordT
 405       _M_getword(size_t) const
 406       { return _M_w; }
 407
 408 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 409       const char*
 410       _M_getdata() const
 411       { return reinterpret_cast<const char*>(&_M_w); }
 412 #endif
 413
 414       _WordT&
 415       _M_hiword()
 416       { return _M_w; }
 417
 418       _WordT
 419       _M_hiword() const
 420       { return _M_w; }
 421
 422       void
 423       _M_do_and(const _Base_bitset<1>& __x)
 424       { _M_w &= __x._M_w; }
 425
 426       void
 427       _M_do_or(const _Base_bitset<1>& __x)
 428       { _M_w |= __x._M_w; }
 429
 430       void
 431       _M_do_xor(const _Base_bitset<1>& __x)
 432       { _M_w ^= __x._M_w; }
 433
 434       void
 435       _M_do_left_shift(size_t __shift)
 436       { _M_w <<= __shift; }
 437
 438       void
 439       _M_do_right_shift(size_t __shift)
 440       { _M_w >>= __shift; }
 441
 442       void
 443       _M_do_flip()
 444       { _M_w = ~_M_w; }
 445
 446       void
 447       _M_do_set()
 448       { _M_w = ~static_cast<_WordT>(0); }
 449
 450       void
 451       _M_do_reset()
 452       { _M_w = 0; }
 453
 454       bool
 455       _M_is_equal(const _Base_bitset<1>& __x) const
 456       { return _M_w == __x._M_w; }
 457
 458       size_t
 459       _M_are_all_aux() const
 460       { return __builtin_popcountl(_M_w); }
 461
 462       bool
 463       _M_is_any() const
 464       { return _M_w != 0; }
 465
 466       size_t
 467       _M_do_count() const
 468       { return __builtin_popcountl(_M_w); }
 469
 470       unsigned long
 471       _M_do_to_ulong() const
 472       { return _M_w; }
 473
 474 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 475       unsigned long long
 476       _M_do_to_ullong() const
 477       { return _M_w; }
 478 #endif
 479
 480       size_t
 481       _M_do_find_first(size_t __not_found) const
 482       {
 483         if (_M_w != 0)
 484           return __builtin_ctzl(_M_w);
 485         else
 486           return __not_found;
 487       }
 488
 489       // find the next "on" bit that follows "prev"
 490       size_t
 491       _M_do_find_next(size_t __prev, size_t __not_found) const
 492       {
 493         ++__prev;
 494         if (__prev >= ((size_t) _GLIBCXX_BITSET_BITS_PER_WORD))
 495           return __not_found;
 496
 497         _WordT __x = _M_w >> __prev;
 498         if (__x != 0)
 499           return __builtin_ctzl(__x) + __prev;
 500         else
 501           return __not_found;
 502       }
 503     };
 504
 505   /**
 506    *  Base class, specialization for no storage (zero-length %bitset).
 507    *
 508    *  See documentation for bitset.
 509   */
 510   template<>
 511     struct _Base_bitset<0>
 512     {
 513       typedef unsigned long _WordT;
 514
 515       _Base_bitset()
 516       { }
 517
 518 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 519       _Base_bitset(unsigned long long)
 520 #else
 521       _Base_bitset(unsigned long)
 522 #endif
 523       { }
 524
 525       static size_t
 526       _S_whichword(size_t __pos )
 527       { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }
 528
 529       static size_t
 530       _S_whichbyte(size_t __pos )
 531       { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }
 532
 533       static size_t
 534       _S_whichbit(size_t __pos )
 535       {  return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }
 536
 537       static _WordT
 538       _S_maskbit(size_t __pos )
 539       { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }
 540
 541       // This would normally give access to the data.  The bounds-checking
 542       // in the bitset class will prevent the user from getting this far,
 543       // but (1) it must still return an lvalue to compile, and (2) the
 544       // user might call _Unchecked_set directly, in which case this /needs/
 545       // to fail.  Let's not penalize zero-length users unless they actually
 546       // make an unchecked call; all the memory ugliness is therefore
 547       // localized to this single should-never-get-this-far function.
 548       _WordT&
 549       _M_getword(size_t) const
 550       {
 551         __throw_out_of_range(__N("_Base_bitset::_M_getword"));
 552         return *new _WordT;
 553       }
 554
 555       _WordT
 556       _M_hiword() const
 557       { return 0; }
 558
 559       void
 560       _M_do_and(const _Base_bitset<0>&)
 561       { }
 562
 563       void
 564       _M_do_or(const _Base_bitset<0>&)
 565       { }
 566
 567       void
 568       _M_do_xor(const _Base_bitset<0>&)
 569       { }
 570
 571       void
 572       _M_do_left_shift(size_t)
 573       { }
 574
 575       void
 576       _M_do_right_shift(size_t)
 577       { }
 578
 579       void
 580       _M_do_flip()
 581       { }
 582
 583       void
 584       _M_do_set()
 585       { }
 586
 587       void
 588       _M_do_reset()
 589       { }
 590
 591       // Are all empty bitsets equal to each other?  Are they equal to
 592       // themselves?  How to compare a thing which has no state?  What is
 593       // the sound of one zero-length bitset clapping?
 594       bool
 595       _M_is_equal(const _Base_bitset<0>&) const
 596       { return true; }
 597
 598       size_t
 599       _M_are_all_aux() const
 600       { return 0; }
 601
 602       bool
 603       _M_is_any() const
 604       { return false; }
 605
 606       size_t
 607       _M_do_count() const
 608       { return 0; }
 609
 610       unsigned long
 611       _M_do_to_ulong() const
 612       { return 0; }
 613
 614 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 615       unsigned long long
 616       _M_do_to_ullong() const
 617       { return 0; }
 618 #endif
 619
 620       // Normally "not found" is the size, but that could also be
 621       // misinterpreted as an index in this corner case.  Oh well.
 622       size_t
 623       _M_do_find_first(size_t) const
 624       { return 0; }
 625
 626       size_t
 627       _M_do_find_next(size_t, size_t) const
 628       { return 0; }
 629     };
 630
 631
 632   // Helper class to zero out the unused high-order bits in the highest word.
 633   template<size_t _Extrabits>
 634     struct _Sanitize
 635     {
 636       static void _S_do_sanitize(unsigned long& __val)
 637       { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); }
 638     };
 639
 640   template<>
 641     struct _Sanitize<0>
 642     { static void _S_do_sanitize(unsigned long) {} };
 643
 644   /**
 645    *  @brief  The %bitset class represents a @e fixed-size sequence of bits.
 646    *
 647    *  @ingroup containers
 648    *
 649    *  (Note that %bitset does @e not meet the formal requirements of a
 650    *  <a href="tables.html#65">container</a>.  Mainly, it lacks iterators.)
 651    *
 652    *  The template argument, @a Nb, may be any non-negative number,
 653    *  specifying the number of bits (e.g., "0", "12", "1024*1024").
 654    *
 655    *  In the general unoptimized case, storage is allocated in word-sized
 656    *  blocks.  Let B be the number of bits in a word, then (Nb+(B-1))/B
 657    *  words will be used for storage.  B - Nb%B bits are unused.  (They are
 658    *  the high-order bits in the highest word.)  It is a class invariant
 659    *  that those unused bits are always zero.
 660    *
 661    *  If you think of %bitset as <em>a simple array of bits</em>, be
 662    *  aware that your mental picture is reversed: a %bitset behaves
 663    *  the same way as bits in integers do, with the bit at index 0 in
 664    *  the <em>least significant / right-hand</em> position, and the bit at
 665    *  index Nb-1 in the <em>most significant / left-hand</em> position.
 666    *  Thus, unlike other containers, a %bitset's index <em>counts from
 667    *  right to left</em>, to put it very loosely.
 668    *
 669    *  This behavior is preserved when translating to and from strings.  For
 670    *  example, the first line of the following program probably prints
 671    *  <em>b(&apos;a&apos;) is 0001100001</em> on a modern ASCII system.
 672    *
 673    *  @code
 674    *     #include <bitset>
 675    *     #include <iostream>
 676    *     #include <sstream>
 677    *
 678    *     using namespace std;
 679    *
 680    *     int main()
 681    *     {
 682    *         long         a = 'a';
 683    *         bitset<10>   b(a);
 684    *
 685    *         cout << "b('a') is " << b << endl;
 686    *
 687    *         ostringstream s;
 688    *         s << b;
 689    *         string  str = s.str();
 690    *         cout << "index 3 in the string is " << str[3] << " but\n"
 691    *              << "index 3 in the bitset is " << b[3] << endl;
 692    *     }
 693    *  @endcode
 694    *
 695    *  Also see:
 696    *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch33s02.html
 697    *  for a description of extensions.
 698    *
 699    *  Most of the actual code isn't contained in %bitset<> itself, but in the
 700    *  base class _Base_bitset.  The base class works with whole words, not with
 701    *  individual bits.  This allows us to specialize _Base_bitset for the
 702    *  important special case where the %bitset is only a single word.
 703    *
 704    *  Extra confusion can result due to the fact that the storage for
 705    *  _Base_bitset @e is a regular array, and is indexed as such.  This is
 706    *  carefully encapsulated.
 707   */
 708   template<size_t _Nb>
 709     class bitset
 710     : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)>
 711     {
 712     private:
 713       typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base;
 714       typedef unsigned long _WordT;
 715
 716       void
 717         _M_do_sanitize()
 718         {
 719           _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD>::
 720             _S_do_sanitize(this->_M_hiword());
 721         }
 722
 723 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 724       template<typename> friend class hash;
 725 #endif
 726
 727     public:
 728       /**
 729        *  This encapsulates the concept of a single bit.  An instance of this
 730        *  class is a proxy for an actual bit; this way the individual bit
 731        *  operations are done as faster word-size bitwise instructions.
 732        *
 733        *  Most users will never need to use this class directly; conversions
 734        *  to and from bool are automatic and should be transparent.  Overloaded
 735        *  operators help to preserve the illusion.
 736        *
 737        *  (On a typical system, this <em>bit %reference</em> is 64
 738        *  times the size of an actual bit.  Ha.)
 739        */
 740       class reference
 741       {
 742         friend class bitset;
 743
 744         _WordT *_M_wp;
 745         size_t _M_bpos;
 746
 747         // left undefined
 748         reference();
 749
 750       public:
 751         reference(bitset& __b, size_t __pos)
 752         {
 753           _M_wp = &__b._M_getword(__pos);
 754           _M_bpos = _Base::_S_whichbit(__pos);
 755         }
 756
 757         ~reference()
 758         { }
 759
 760         // For b[i] = __x;
 761         reference&
 762         operator=(bool __x)
 763         {
 764           if (__x)
 765             *_M_wp |= _Base::_S_maskbit(_M_bpos);
 766           else
 767             *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
 768           return *this;
 769         }
 770
 771         // For b[i] = b[__j];
 772         reference&
 773         operator=(const reference& __j)
 774         {
 775           if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
 776             *_M_wp |= _Base::_S_maskbit(_M_bpos);
 777           else
 778             *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
 779           return *this;
 780         }
 781
 782         // Flips the bit
 783         bool
 784         operator~() const
 785         { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; }
 786
 787         // For __x = b[i];
 788         operator bool() const
 789         { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }
 790
 791         // For b[i].flip();
 792         reference&
 793         flip()
 794         {
 795           *_M_wp ^= _Base::_S_maskbit(_M_bpos);
 796           return *this;
 797         }
 798       };
 799       friend class reference;
 800
 801       // 23.3.5.1 constructors:
 802       /// All bits set to zero.
 803       bitset()
 804       { }
 805
 806       /// Initial bits bitwise-copied from a single word (others set to zero).
 807 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 808       bitset(unsigned long long __val)
 809 #else
 810       bitset(unsigned long __val)
 811 #endif
 812       : _Base(__val)
 813       { _M_do_sanitize(); }
 814
 815       /**
 816        *  @brief  Use a subset of a string.
 817        *  @param  s  A string of @a 0 and @a 1 characters.
 818        *  @param  position  Index of the first character in @a s to use;
 819        *                    defaults to zero.
 820        *  @throw  std::out_of_range  If @a pos is bigger the size of @a s.
 821        *  @throw  std::invalid_argument  If a character appears in the string
 822        *                                 which is neither @a 0 nor @a 1.
 823        */
 824       template<class _CharT, class _Traits, class _Alloc>
 825         explicit
 826         bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
 827                size_t __position = 0)
 828         : _Base()
 829         {
 830           if (__position > __s.size())
 831             __throw_out_of_range(__N("bitset::bitset initial position "
 832                                      "not valid"));
 833           _M_copy_from_string(__s, __position,
 834                               std::basic_string<_CharT, _Traits, _Alloc>::npos,
 835                               _CharT('0'), _CharT('1'));
 836         }
 837
 838       /**
 839        *  @brief  Use a subset of a string.
 840        *  @param  s  A string of @a 0 and @a 1 characters.
 841        *  @param  position  Index of the first character in @a s to use.
 842        *  @param  n    The number of characters to copy.
 843        *  @throw  std::out_of_range  If @a pos is bigger the size of @a s.
 844        *  @throw  std::invalid_argument  If a character appears in the string
 845        *                                 which is neither @a 0 nor @a 1.
 846        */
 847       template<class _CharT, class _Traits, class _Alloc>
 848         bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
 849                size_t __position, size_t __n)
 850         : _Base()
 851         {
 852           if (__position > __s.size())
 853             __throw_out_of_range(__N("bitset::bitset initial position "
 854                                      "not valid"));
 855           _M_copy_from_string(__s, __position, __n, _CharT('0'), _CharT('1'));
 856         }
 857
 858       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 859       // 396. what are characters zero and one.
 860       template<class _CharT, class _Traits, class _Alloc>
 861         bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
 862                size_t __position, size_t __n,
 863                _CharT __zero, _CharT __one = _CharT('1'))
 864         : _Base()
 865         {
 866           if (__position > __s.size())
 867             __throw_out_of_range(__N("bitset::bitset initial position "
 868                                      "not valid"));
 869           _M_copy_from_string(__s, __position, __n, __zero, __one);
 870         }
 871
 872 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 873       /**
 874        *  @brief  Construct from a string.
 875        *  @param  str  A string of @a 0 and @a 1 characters.
 876        *  @throw  std::invalid_argument  If a character appears in the string
 877        *                                 which is neither @a 0 nor @a 1.
 878        */
 879       explicit
 880       bitset(const char* __str)
 881       : _Base()
 882       {
 883         if (!__str)
 884           __throw_logic_error(__N("bitset::bitset(const char*)"));
 885
 886         const size_t __len = __builtin_strlen(__str);
 887         _M_copy_from_ptr<char, std::char_traits<char>>(__str, __len, 0,
 888                                                        __len, '0', '1');
 889       }
 890 #endif
 891
 892       // 23.3.5.2 bitset operations:
 893       //@{
 894       /**
 895        *  @brief  Operations on bitsets.
 896        *  @param  rhs  A same-sized bitset.
 897        *
 898        *  These should be self-explanatory.
 899        */
 900       bitset<_Nb>&
 901       operator&=(const bitset<_Nb>& __rhs)
 902       {
 903         this->_M_do_and(__rhs);
 904         return *this;
 905       }
 906
 907       bitset<_Nb>&
 908       operator|=(const bitset<_Nb>& __rhs)
 909       {
 910         this->_M_do_or(__rhs);
 911         return *this;
 912       }
 913
 914       bitset<_Nb>&
 915       operator^=(const bitset<_Nb>& __rhs)
 916       {
 917         this->_M_do_xor(__rhs);
 918         return *this;
 919       }
 920       //@}
 921
 922       //@{
 923       /**
 924        *  @brief  Operations on bitsets.
 925        *  @param  position  The number of places to shift.
 926        *
 927        *  These should be self-explanatory.
 928        */
 929       bitset<_Nb>&
 930       operator<<=(size_t __position)
 931       {
 932         if (__builtin_expect(__position < _Nb, 1))
 933           {
 934             this->_M_do_left_shift(__position);
 935             this->_M_do_sanitize();
 936           }
 937         else
 938           this->_M_do_reset();
 939         return *this;
 940       }
 941
 942       bitset<_Nb>&
 943       operator>>=(size_t __position)
 944       {
 945         if (__builtin_expect(__position < _Nb, 1))
 946           {
 947             this->_M_do_right_shift(__position);
 948             this->_M_do_sanitize();
 949           }
 950         else
 951           this->_M_do_reset();
 952         return *this;
 953       }
 954       //@}
 955
 956       //@{
 957       /**
 958        *  These versions of single-bit set, reset, flip, and test are
 959        *  extensions from the SGI version.  They do no range checking.
 960        *  @ingroup SGIextensions
 961        */
 962       bitset<_Nb>&
 963       _Unchecked_set(size_t __pos)
 964       {
 965         this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
 966         return *this;
 967       }
 968
 969       bitset<_Nb>&
 970       _Unchecked_set(size_t __pos, int __val)
 971       {
 972         if (__val)
 973           this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
 974         else
 975           this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
 976         return *this;
 977       }
 978
 979       bitset<_Nb>&
 980       _Unchecked_reset(size_t __pos)
 981       {
 982         this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
 983         return *this;
 984       }
 985
 986       bitset<_Nb>&
 987       _Unchecked_flip(size_t __pos)
 988       {
 989         this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
 990         return *this;
 991       }
 992
 993       bool
 994       _Unchecked_test(size_t __pos) const
 995       { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
 996                 != static_cast<_WordT>(0)); }
 997       //@}
 998
 999       // Set, reset, and flip.
1000       /**
1001        *  @brief Sets every bit to true.
1002        */
1003       bitset<_Nb>&
1004       set()
1005       {
1006         this->_M_do_set();
1007         this->_M_do_sanitize();
1008         return *this;
1009       }
1010
1011       /**
1012        *  @brief Sets a given bit to a particular value.
1013        *  @param  position  The index of the bit.
1014        *  @param  val  Either true or false, defaults to true.
1015        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
1016        */
1017       bitset<_Nb>&
1018       set(size_t __position, bool __val = true)
1019       {
1020         if (__position >= _Nb)
1021           __throw_out_of_range(__N("bitset::set"));
1022         return _Unchecked_set(__position, __val);
1023       }
1024
1025       /**
1026        *  @brief Sets every bit to false.
1027        */
1028       bitset<_Nb>&
1029       reset()
1030       {
1031         this->_M_do_reset();
1032         return *this;
1033       }
1034
1035       /**
1036        *  @brief Sets a given bit to false.
1037        *  @param  position  The index of the bit.
1038        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
1039        *
1040        *  Same as writing @c set(pos,false).
1041        */
1042       bitset<_Nb>&
1043       reset(size_t __position)
1044       {
1045         if (__position >= _Nb)
1046           __throw_out_of_range(__N("bitset::reset"));
1047         return _Unchecked_reset(__position);
1048       }
1049
1050       /**
1051        *  @brief Toggles every bit to its opposite value.
1052        */
1053       bitset<_Nb>&
1054       flip()
1055       {
1056         this->_M_do_flip();
1057         this->_M_do_sanitize();
1058         return *this;
1059       }
1060
1061       /**
1062        *  @brief Toggles a given bit to its opposite value.
1063        *  @param  position  The index of the bit.
1064        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
1065        */
1066       bitset<_Nb>&
1067       flip(size_t __position)
1068       {
1069         if (__position >= _Nb)
1070           __throw_out_of_range(__N("bitset::flip"));
1071         return _Unchecked_flip(__position);
1072       }
1073
1074       /// See the no-argument flip().
1075       bitset<_Nb>
1076       operator~() const
1077       { return bitset<_Nb>(*this).flip(); }
1078
1079       //@{
1080       /**
1081        *  @brief  Array-indexing support.
1082        *  @param  position  Index into the %bitset.
1083        *  @return  A bool for a <em>const %bitset</em>.  For non-const bitsets, an
1084        *           instance of the reference proxy class.
1085        *  @note  These operators do no range checking and throw no exceptions,
1086        *         as required by DR 11 to the standard.
1087        *
1088        *  _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already
1089        *  resolves DR 11 (items 1 and 2), but does not do the range-checking
1090        *  required by that DR's resolution.  -pme
1091        *  The DR has since been changed:  range-checking is a precondition
1092        *  (users' responsibility), and these functions must not throw.  -pme
1093        */
1094       reference
1095       operator[](size_t __position)
1096       { return reference(*this,__position); }
1097
1098       bool
1099       operator[](size_t __position) const
1100       { return _Unchecked_test(__position); }
1101       //@}
1102
1103       /**
1104        *  @brief Returns a numerical interpretation of the %bitset.
1105        *  @return  The integral equivalent of the bits.
1106        *  @throw  std::overflow_error  If there are too many bits to be
1107        *                               represented in an @c unsigned @c long.
1108        */
1109       unsigned long
1110       to_ulong() const
1111       { return this->_M_do_to_ulong(); }
1112
1113 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1114       unsigned long long
1115       to_ullong() const
1116       { return this->_M_do_to_ullong(); }
1117 #endif
1118
1119       /**
1120        *  @brief Returns a character interpretation of the %bitset.
1121        *  @return  The string equivalent of the bits.
1122        *
1123        *  Note the ordering of the bits:  decreasing character positions
1124        *  correspond to increasing bit positions (see the main class notes for
1125        *  an example).
1126        */
1127       template<class _CharT, class _Traits, class _Alloc>
1128         std::basic_string<_CharT, _Traits, _Alloc>
1129         to_string() const
1130         {
1131           std::basic_string<_CharT, _Traits, _Alloc> __result;
1132           _M_copy_to_string(__result, _CharT('0'), _CharT('1'));
1133           return __result;
1134         }
1135
1136       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1137       // 396. what are characters zero and one.
1138       template<class _CharT, class _Traits, class _Alloc>
1139         std::basic_string<_CharT, _Traits, _Alloc>
1140         to_string(_CharT __zero, _CharT __one = _CharT('1')) const
1141         {
1142           std::basic_string<_CharT, _Traits, _Alloc> __result;
1143           _M_copy_to_string(__result, __zero, __one);
1144           return __result;
1145         }
1146
1147       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1148       // 434. bitset::to_string() hard to use.
1149       template<class _CharT, class _Traits>
1150         std::basic_string<_CharT, _Traits, std::allocator<_CharT> >
1151         to_string() const
1152         { return to_string<_CharT, _Traits, std::allocator<_CharT> >(); }
1153
1154       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1155       // 853. to_string needs updating with zero and one.
1156       template<class _CharT, class _Traits>
1157         std::basic_string<_CharT, _Traits, std::allocator<_CharT> >
1158         to_string(_CharT __zero, _CharT __one = _CharT('1')) const
1159         { return to_string<_CharT, _Traits,
1160                            std::allocator<_CharT> >(__zero, __one); }
1161
1162       template<class _CharT>
1163         std::basic_string<_CharT, std::char_traits<_CharT>,
1164                           std::allocator<_CharT> >
1165         to_string() const
1166         {
1167           return to_string<_CharT, std::char_traits<_CharT>,
1168                            std::allocator<_CharT> >();
1169         }
1170
1171       template<class _CharT>
1172         std::basic_string<_CharT, std::char_traits<_CharT>,
1173                           std::allocator<_CharT> >
1174         to_string(_CharT __zero, _CharT __one = _CharT('1')) const
1175         {
1176           return to_string<_CharT, std::char_traits<_CharT>,
1177                            std::allocator<_CharT> >(__zero, __one);
1178         }
1179
1180       std::basic_string<char, std::char_traits<char>, std::allocator<char> >
1181       to_string() const
1182       {
1183         return to_string<char, std::char_traits<char>,
1184                          std::allocator<char> >();
1185       }
1186
1187       std::basic_string<char, std::char_traits<char>, std::allocator<char> >
1188       to_string(char __zero, char __one = '1') const
1189       {
1190         return to_string<char, std::char_traits<char>,
1191                          std::allocator<char> >(__zero, __one);
1192       }
1193
1194       // Helper functions for string operations.
1195       template<class _CharT, class _Traits>
1196         void
1197         _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
1198                          _CharT, _CharT);
1199
1200       template<class _CharT, class _Traits, class _Alloc>
1201         void
1202         _M_copy_from_string(const std::basic_string<_CharT,
1203                             _Traits, _Alloc>& __s, size_t __pos, size_t __n,
1204                             _CharT __zero, _CharT __one)
1205         { _M_copy_from_ptr<_CharT, _Traits>(__s.data(), __s.size(), __pos, __n,
1206                                             __zero, __one); }
1207
1208       template<class _CharT, class _Traits, class _Alloc>
1209         void
1210         _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>&,
1211                           _CharT, _CharT) const;
1212
1213       // NB: Backward compat.
1214       template<class _CharT, class _Traits, class _Alloc>
1215         void
1216         _M_copy_from_string(const std::basic_string<_CharT,
1217                             _Traits, _Alloc>& __s, size_t __pos, size_t __n)
1218         { _M_copy_from_string(__s, __pos, __n, _CharT('0'), _CharT('1')); }
1219
1220       template<class _CharT, class _Traits, class _Alloc>
1221         void
1222         _M_copy_to_string(std::basic_string<_CharT, _Traits,_Alloc>& __s) const
1223         { _M_copy_to_string(__s, _CharT('0'), _CharT('1')); }
1224
1225       /// Returns the number of bits which are set.
1226       size_t
1227       count() const
1228       { return this->_M_do_count(); }
1229
1230       /// Returns the total number of bits.
1231       size_t
1232       size() const
1233       { return _Nb; }
1234
1235       //@{
1236       /// These comparisons for equality/inequality are, well, @e bitwise.
1237       bool
1238       operator==(const bitset<_Nb>& __rhs) const
1239       { return this->_M_is_equal(__rhs); }
1240
1241       bool
1242       operator!=(const bitset<_Nb>& __rhs) const
1243       { return !this->_M_is_equal(__rhs); }
1244       //@}
1245
1246       /**
1247        *  @brief Tests the value of a bit.
1248        *  @param  position  The index of a bit.
1249        *  @return  The value at @a pos.
1250        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
1251        */
1252       bool
1253       test(size_t __position) const
1254       {
1255         if (__position >= _Nb)
1256           __throw_out_of_range(__N("bitset::test"));
1257         return _Unchecked_test(__position);
1258       }
1259
1260       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1261       // DR 693. std::bitset::all() missing.
1262       /**
1263        *  @brief Tests whether all the bits are on.
1264        *  @return  True if all the bits are set.
1265        */
1266       bool
1267       all() const
1268       { return this->_M_are_all_aux() == _Nb; }
1269
1270       /**
1271        *  @brief Tests whether any of the bits are on.
1272        *  @return  True if at least one bit is set.
1273        */
1274       bool
1275       any() const
1276       { return this->_M_is_any(); }
1277
1278       /**
1279        *  @brief Tests whether any of the bits are on.
1280        *  @return  True if none of the bits are set.
1281        */
1282       bool
1283       none() const
1284       { return !this->_M_is_any(); }
1285
1286       //@{
1287       /// Self-explanatory.
1288       bitset<_Nb>
1289       operator<<(size_t __position) const
1290       { return bitset<_Nb>(*this) <<= __position; }
1291
1292       bitset<_Nb>
1293       operator>>(size_t __position) const
1294       { return bitset<_Nb>(*this) >>= __position; }
1295       //@}
1296
1297       /**
1298        *  @brief  Finds the index of the first "on" bit.
1299        *  @return  The index of the first bit set, or size() if not found.
1300        *  @ingroup SGIextensions
1301        *  @sa  _Find_next
1302        */
1303       size_t
1304       _Find_first() const
1305       { return this->_M_do_find_first(_Nb); }
1306
1307       /**
1308        *  @brief  Finds the index of the next "on" bit after prev.
1309        *  @return  The index of the next bit set, or size() if not found.
1310        *  @param  prev  Where to start searching.
1311        *  @ingroup SGIextensions
1312        *  @sa  _Find_first
1313        */
1314       size_t
1315       _Find_next(size_t __prev ) const
1316       { return this->_M_do_find_next(__prev, _Nb); }
1317     };
1318
1319   // Definitions of non-inline member functions.
1320   template<size_t _Nb>
1321     template<class _CharT, class _Traits>
1322       void
1323       bitset<_Nb>::
1324       _M_copy_from_ptr(const _CharT* __s, size_t __len,
1325                        size_t __pos, size_t __n, _CharT __zero, _CharT __one)
1326       {
1327         reset();
1328         const size_t __nbits = std::min(_Nb, std::min(__n, __len - __pos));
1329         for (size_t __i = __nbits; __i > 0; --__i)
1330           {
1331             const _CharT __c = __s[__pos + __nbits - __i];
1332             if (_Traits::eq(__c, __zero))
1333               ;
1334             else if (_Traits::eq(__c, __one))
1335               _Unchecked_set(__i - 1);
1336             else
1337               __throw_invalid_argument(__N("bitset::_M_copy_from_ptr"));
1338           }
1339       }
1340
1341   template<size_t _Nb>
1342     template<class _CharT, class _Traits, class _Alloc>
1343       void
1344       bitset<_Nb>::
1345       _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>& __s,
1346                         _CharT __zero, _CharT __one) const
1347       {
1348         __s.assign(_Nb, __zero);
1349         for (size_t __i = _Nb; __i > 0; --__i)
1350           if (_Unchecked_test(__i - 1))
1351             _Traits::assign(__s[_Nb - __i], __one);
1352       }
1353
1354   // 23.3.5.3 bitset operations:
1355   //@{
1356   /**
1357    *  @brief  Global bitwise operations on bitsets.
1358    *  @param  x  A bitset.
1359    *  @param  y  A bitset of the same size as @a x.
1360    *  @return  A new bitset.
1361    *
1362    *  These should be self-explanatory.
1363   */
1364   template<size_t _Nb>
1365     inline bitset<_Nb>
1366     operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
1367     {
1368       bitset<_Nb> __result(__x);
1369       __result &= __y;
1370       return __result;
1371     }
1372
1373   template<size_t _Nb>
1374     inline bitset<_Nb>
1375     operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
1376     {
1377       bitset<_Nb> __result(__x);
1378       __result |= __y;
1379       return __result;
1380     }
1381
1382   template <size_t _Nb>
1383     inline bitset<_Nb>
1384     operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y)
1385     {
1386       bitset<_Nb> __result(__x);
1387       __result ^= __y;
1388       return __result;
1389     }
1390   //@}
1391
1392   //@{
1393   /**
1394    *  @brief Global I/O operators for bitsets.
1395    *
1396    *  Direct I/O between streams and bitsets is supported.  Output is
1397    *  straightforward.  Input will skip whitespace, only accept @a 0 and @a 1
1398    *  characters, and will only extract as many digits as the %bitset will
1399    *  hold.
1400   */
1401   template<class _CharT, class _Traits, size_t _Nb>
1402     std::basic_istream<_CharT, _Traits>&
1403     operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x)
1404     {
1405       typedef typename _Traits::char_type          char_type;
1406       typedef std::basic_istream<_CharT, _Traits>  __istream_type;
1407       typedef typename __istream_type::ios_base    __ios_base;
1408
1409       std::basic_string<_CharT, _Traits> __tmp;
1410       __tmp.reserve(_Nb);
1411
1412       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1413       // 303. Bitset input operator underspecified
1414       const char_type __zero = __is.widen('0');
1415       const char_type __one = __is.widen('1');
1416
1417       typename __ios_base::iostate __state = __ios_base::goodbit;
1418       typename __istream_type::sentry __sentry(__is);
1419       if (__sentry)
1420         {
1421           __try
1422             {
1423               for (size_t __i = _Nb; __i > 0; --__i)
1424                 {
1425                   static typename _Traits::int_type __eof = _Traits::eof();
1426
1427                   typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc();
1428                   if (_Traits::eq_int_type(__c1, __eof))
1429                     {
1430                       __state |= __ios_base::eofbit;
1431                       break;
1432                     }
1433                   else
1434                     {
1435                       const char_type __c2 = _Traits::to_char_type(__c1);
1436                       if (_Traits::eq(__c2, __zero))
1437                         __tmp.push_back(__zero);
1438                       else if (_Traits::eq(__c2, __one))
1439                         __tmp.push_back(__one);
1440                       else if (_Traits::
1441                                eq_int_type(__is.rdbuf()->sputbackc(__c2),
1442                                            __eof))
1443                         {
1444                           __state |= __ios_base::failbit;
1445                           break;
1446                         }
1447                     }
1448                 }
1449             }
1450           __catch(__cxxabiv1::__forced_unwind&)
1451             {
1452               __is._M_setstate(__ios_base::badbit);
1453               __throw_exception_again;
1454             }
1455           __catch(...)
1456             { __is._M_setstate(__ios_base::badbit); }
1457         }
1458
1459       if (__tmp.empty() && _Nb)
1460         __state |= __ios_base::failbit;
1461       else
1462         __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb,
1463                                 __zero, __one);
1464       if (__state)
1465         __is.setstate(__state);
1466       return __is;
1467     }
1468
1469   template <class _CharT, class _Traits, size_t _Nb>
1470     std::basic_ostream<_CharT, _Traits>&
1471     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1472                const bitset<_Nb>& __x)
1473     {
1474       std::basic_string<_CharT, _Traits> __tmp;
1475
1476       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1477       // 396. what are characters zero and one.
1478       const ctype<_CharT>& __ct = use_facet<ctype<_CharT> >(__os.getloc());
1479       __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
1480       return __os << __tmp;
1481     }
1482   //@}
1483
1484 _GLIBCXX_END_NESTED_NAMESPACE
1485
1486 #undef _GLIBCXX_BITSET_WORDS
1487 #undef _GLIBCXX_BITSET_BITS_PER_WORD
1488
1489 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1490
1491 #include <bits/functional_hash.h>
1492
1493 _GLIBCXX_BEGIN_NAMESPACE(std)
1494
1495   // DR 1182.
1496   /// std::hash specialization for bitset.
1497   template<size_t _Nb>
1498     struct hash<_GLIBCXX_STD_D::bitset<_Nb>>
1499     : public std::unary_function<_GLIBCXX_STD_D::bitset<_Nb>, size_t>
1500     {
1501       size_t
1502       operator()(const _GLIBCXX_STD_D::bitset<_Nb>& __b) const
1503       {
1504         const size_t __size = (_Nb + __CHAR_BIT__ - 1) / __CHAR_BIT__;
1505         return std::_Fnv_hash::hash(__b._M_getdata(), __size);
1506       }
1507     };
1508
1509   template<>
1510     struct hash<_GLIBCXX_STD_D::bitset<0>>
1511     : public std::unary_function<_GLIBCXX_STD_D::bitset<0>, size_t>
1512     {
1513       size_t
1514       operator()(const _GLIBCXX_STD_D::bitset<0>&) const
1515       { return 0; }
1516     };
1517
1518 _GLIBCXX_END_NAMESPACE
1519
1520 #endif // __GXX_EXPERIMENTAL_CXX0X__
1521
1522 #ifdef _GLIBCXX_DEBUG
1523 # include <debug/bitset>
1524 #endif
1525
1526 #ifdef _GLIBCXX_PROFILE
1527 # include <profile/bitset>
1528 #endif
1529
1530 #endif /* _GLIBCXX_BITSET */