libstdc++-v3/include/std/bitset

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