libstdc++-v3/include/std/bitset

   1 // <bitset> -*- C++ -*-
   2
   3 // Copyright (C) 2001-2016 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    *  @brief The %bitset class represents a @e fixed-size sequence of bits.
 685    *  @ingroup utilities
 686    *
 687    *  (Note that %bitset does @e not meet the formal requirements of a
 688    *  <a href="tables.html#65">container</a>.  Mainly, it lacks iterators.)
 689    *
 690    *  The template argument, @a Nb, may be any non-negative number,
 691    *  specifying the number of bits (e.g., "0", "12", "1024*1024").
 692    *
 693    *  In the general unoptimized case, storage is allocated in word-sized
 694    *  blocks.  Let B be the number of bits in a word, then (Nb+(B-1))/B
 695    *  words will be used for storage.  B - Nb%B bits are unused.  (They are
 696    *  the high-order bits in the highest word.)  It is a class invariant
 697    *  that those unused bits are always zero.
 698    *
 699    *  If you think of %bitset as <em>a simple array of bits</em>, be
 700    *  aware that your mental picture is reversed: a %bitset behaves
 701    *  the same way as bits in integers do, with the bit at index 0 in
 702    *  the <em>least significant / right-hand</em> position, and the bit at
 703    *  index Nb-1 in the <em>most significant / left-hand</em> position.
 704    *  Thus, unlike other containers, a %bitset's index <em>counts from
 705    *  right to left</em>, to put it very loosely.
 706    *
 707    *  This behavior is preserved when translating to and from strings.  For
 708    *  example, the first line of the following program probably prints
 709    *  <em>b(&apos;a&apos;) is 0001100001</em> on a modern ASCII system.
 710    *
 711    *  @code
 712    *     #include <bitset>
 713    *     #include <iostream>
 714    *     #include <sstream>
 715    *
 716    *     using namespace std;
 717    *
 718    *     int main()
 719    *     {
 720    *         long         a = 'a';
 721    *         bitset<10>   b(a);
 722    *
 723    *         cout << "b('a') is " << b << endl;
 724    *
 725    *         ostringstream s;
 726    *         s << b;
 727    *         string  str = s.str();
 728    *         cout << "index 3 in the string is " << str[3] << " but\n"
 729    *              << "index 3 in the bitset is " << b[3] << endl;
 730    *     }
 731    *  @endcode
 732    *
 733    *  Also see:
 734    *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/ext_containers.html
 735    *  for a description of extensions.
 736    *
 737    *  Most of the actual code isn't contained in %bitset<> itself, but in the
 738    *  base class _Base_bitset.  The base class works with whole words, not with
 739    *  individual bits.  This allows us to specialize _Base_bitset for the
 740    *  important special case where the %bitset is only a single word.
 741    *
 742    *  Extra confusion can result due to the fact that the storage for
 743    *  _Base_bitset @e is a regular array, and is indexed as such.  This is
 744    *  carefully encapsulated.
 745   */
 746   template<size_t _Nb>
 747     class bitset
 748     : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)>
 749     {
 750     private:
 751       typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base;
 752       typedef unsigned long _WordT;
 753
 754       template<class _CharT, class _Traits, class _Alloc>
 755       void
 756       _M_check_initial_position(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
 757                                 size_t __position) const
 758       {
 759         if (__position > __s.size())
 760           __throw_out_of_range_fmt(__N("bitset::bitset: __position "
 761                                        "(which is %zu) > __s.size() "
 762                                        "(which is %zu)"),
 763                                    __position, __s.size());
 764       }
 765
 766       void _M_check(size_t __position, const char *__s) const
 767       {
 768         if (__position >= _Nb)
 769           __throw_out_of_range_fmt(__N("%s: __position (which is %zu) "
 770                                        ">= _Nb (which is %zu)"),
 771                                    __s, __position, _Nb);
 772       }
 773
 774       void
 775       _M_do_sanitize() _GLIBCXX_NOEXCEPT
 776       {
 777         typedef _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD> __sanitize_type;
 778         __sanitize_type::_S_do_sanitize(this->_M_hiword());
 779       }
 780
 781 #if __cplusplus >= 201103L
 782       template<typename> friend struct hash;
 783 #endif
 784
 785     public:
 786       /**
 787        *  This encapsulates the concept of a single bit.  An instance of this
 788        *  class is a proxy for an actual bit; this way the individual bit
 789        *  operations are done as faster word-size bitwise instructions.
 790        *
 791        *  Most users will never need to use this class directly; conversions
 792        *  to and from bool are automatic and should be transparent.  Overloaded
 793        *  operators help to preserve the illusion.
 794        *
 795        *  (On a typical system, this <em>bit %reference</em> is 64
 796        *  times the size of an actual bit.  Ha.)
 797        */
 798       class reference
 799       {
 800         friend class bitset;
 801
 802         _WordT* _M_wp;
 803         size_t  _M_bpos;
 804
 805         // left undefined
 806         reference();
 807
 808       public:
 809         reference(bitset& __b, size_t __pos) _GLIBCXX_NOEXCEPT
 810         {
 811           _M_wp = &__b._M_getword(__pos);
 812           _M_bpos = _Base::_S_whichbit(__pos);
 813         }
 814
 815         ~reference() _GLIBCXX_NOEXCEPT
 816         { }
 817
 818         // For b[i] = __x;
 819         reference&
 820         operator=(bool __x) _GLIBCXX_NOEXCEPT
 821         {
 822           if (__x)
 823             *_M_wp |= _Base::_S_maskbit(_M_bpos);
 824           else
 825             *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
 826           return *this;
 827         }
 828
 829         // For b[i] = b[__j];
 830         reference&
 831         operator=(const reference& __j) _GLIBCXX_NOEXCEPT
 832         {
 833           if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
 834             *_M_wp |= _Base::_S_maskbit(_M_bpos);
 835           else
 836             *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
 837           return *this;
 838         }
 839
 840         // Flips the bit
 841         bool
 842         operator~() const _GLIBCXX_NOEXCEPT
 843         { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; }
 844
 845         // For __x = b[i];
 846         operator bool() const _GLIBCXX_NOEXCEPT
 847         { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }
 848
 849         // For b[i].flip();
 850         reference&
 851         flip() _GLIBCXX_NOEXCEPT
 852         {
 853           *_M_wp ^= _Base::_S_maskbit(_M_bpos);
 854           return *this;
 855         }
 856       };
 857       friend class reference;
 858
 859       // 23.3.5.1 constructors:
 860       /// All bits set to zero.
 861       _GLIBCXX_CONSTEXPR bitset() _GLIBCXX_NOEXCEPT
 862       { }
 863
 864       /// Initial bits bitwise-copied from a single word (others set to zero).
 865 #if __cplusplus >= 201103L
 866       constexpr bitset(unsigned long long __val) noexcept
 867       : _Base(_Sanitize_val<_Nb>::_S_do_sanitize_val(__val)) { }
 868 #else
 869       bitset(unsigned long __val)
 870       : _Base(__val)
 871       { _M_do_sanitize(); }
 872 #endif
 873
 874       /**
 875        *  Use a subset of a string.
 876        *  @param  __s  A string of @a 0 and @a 1 characters.
 877        *  @param  __position  Index of the first character in @a __s to use;
 878        *                    defaults to zero.
 879        *  @throw  std::out_of_range  If @a pos is bigger the size of @a __s.
 880        *  @throw  std::invalid_argument  If a character appears in the string
 881        *                                 which is neither @a 0 nor @a 1.
 882        */
 883       template<class _CharT, class _Traits, class _Alloc>
 884         explicit
 885         bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
 886                size_t __position = 0)
 887         : _Base()
 888         {
 889           _M_check_initial_position(__s, __position);
 890           _M_copy_from_string(__s, __position,
 891                               std::basic_string<_CharT, _Traits, _Alloc>::npos,
 892                               _CharT('0'), _CharT('1'));
 893         }
 894
 895       /**
 896        *  Use a subset of a string.
 897        *  @param  __s  A string of @a 0 and @a 1 characters.
 898        *  @param  __position  Index of the first character in @a __s to use.
 899        *  @param  __n    The number of characters to copy.
 900        *  @throw std::out_of_range If @a __position is bigger the size
 901        *  of @a __s.
 902        *  @throw  std::invalid_argument  If a character appears in the string
 903        *                                 which is neither @a 0 nor @a 1.
 904        */
 905       template<class _CharT, class _Traits, class _Alloc>
 906         bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
 907                size_t __position, size_t __n)
 908         : _Base()
 909         {
 910           _M_check_initial_position(__s, __position);
 911           _M_copy_from_string(__s, __position, __n, _CharT('0'), _CharT('1'));
 912         }
 913
 914       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 915       // 396. what are characters zero and one.
 916       template<class _CharT, class _Traits, class _Alloc>
 917         bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
 918                size_t __position, size_t __n,
 919                _CharT __zero, _CharT __one = _CharT('1'))
 920         : _Base()
 921         {
 922           _M_check_initial_position(__s, __position);
 923           _M_copy_from_string(__s, __position, __n, __zero, __one);
 924         }
 925
 926 #if __cplusplus >= 201103L
 927       /**
 928        *  Construct from a character %array.
 929        *  @param  __str  An %array of characters @a zero and @a one.
 930        *  @param  __n    The number of characters to use.
 931        *  @param  __zero The character corresponding to the value 0.
 932        *  @param  __one  The character corresponding to the value 1.
 933        *  @throw  std::invalid_argument If a character appears in the string
 934        *                                which is neither @a __zero nor @a __one.
 935        */
 936       template<typename _CharT>
 937         explicit
 938         bitset(const _CharT* __str,
 939                typename std::basic_string<_CharT>::size_type __n
 940                = std::basic_string<_CharT>::npos,
 941                _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'))
 942         : _Base()
 943         {
 944           if (!__str)
 945             __throw_logic_error(__N("bitset::bitset(const _CharT*, ...)"));
 946
 947           if (__n == std::basic_string<_CharT>::npos)
 948             __n = std::char_traits<_CharT>::length(__str);
 949           _M_copy_from_ptr<_CharT, std::char_traits<_CharT>>(__str, __n, 0,
 950                                                              __n, __zero,
 951                                                              __one);
 952         }
 953 #endif
 954
 955       // 23.3.5.2 bitset operations:
 956       //@{
 957       /**
 958        *  Operations on bitsets.
 959        *  @param  __rhs  A same-sized bitset.
 960        *
 961        *  These should be self-explanatory.
 962        */
 963       bitset<_Nb>&
 964       operator&=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT
 965       {
 966         this->_M_do_and(__rhs);
 967         return *this;
 968       }
 969
 970       bitset<_Nb>&
 971       operator|=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT
 972       {
 973         this->_M_do_or(__rhs);
 974         return *this;
 975       }
 976
 977       bitset<_Nb>&
 978       operator^=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT
 979       {
 980         this->_M_do_xor(__rhs);
 981         return *this;
 982       }
 983       //@}
 984
 985       //@{
 986       /**
 987        *  Operations on bitsets.
 988        *  @param  __position  The number of places to shift.
 989        *
 990        *  These should be self-explanatory.
 991        */
 992       bitset<_Nb>&
 993       operator<<=(size_t __position) _GLIBCXX_NOEXCEPT
 994       {
 995         if (__builtin_expect(__position < _Nb, 1))
 996           {
 997             this->_M_do_left_shift(__position);
 998             this->_M_do_sanitize();
 999           }
1000         else
1001           this->_M_do_reset();
1002         return *this;
1003       }
1004
1005       bitset<_Nb>&
1006       operator>>=(size_t __position) _GLIBCXX_NOEXCEPT
1007       {
1008         if (__builtin_expect(__position < _Nb, 1))
1009           {
1010             this->_M_do_right_shift(__position);
1011             this->_M_do_sanitize();
1012           }
1013         else
1014           this->_M_do_reset();
1015         return *this;
1016       }
1017       //@}
1018
1019       //@{
1020       /**
1021        *  These versions of single-bit set, reset, flip, and test are
1022        *  extensions from the SGI version.  They do no range checking.
1023        *  @ingroup SGIextensions
1024        */
1025       bitset<_Nb>&
1026       _Unchecked_set(size_t __pos) _GLIBCXX_NOEXCEPT
1027       {
1028         this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
1029         return *this;
1030       }
1031
1032       bitset<_Nb>&
1033       _Unchecked_set(size_t __pos, int __val) _GLIBCXX_NOEXCEPT
1034       {
1035         if (__val)
1036           this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
1037         else
1038           this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
1039         return *this;
1040       }
1041
1042       bitset<_Nb>&
1043       _Unchecked_reset(size_t __pos) _GLIBCXX_NOEXCEPT
1044       {
1045         this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
1046         return *this;
1047       }
1048
1049       bitset<_Nb>&
1050       _Unchecked_flip(size_t __pos) _GLIBCXX_NOEXCEPT
1051       {
1052         this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
1053         return *this;
1054       }
1055
1056       _GLIBCXX_CONSTEXPR bool
1057       _Unchecked_test(size_t __pos) const _GLIBCXX_NOEXCEPT
1058       { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
1059                 != static_cast<_WordT>(0)); }
1060       //@}
1061
1062       // Set, reset, and flip.
1063       /**
1064        *  @brief Sets every bit to true.
1065        */
1066       bitset<_Nb>&
1067       set() _GLIBCXX_NOEXCEPT
1068       {
1069         this->_M_do_set();
1070         this->_M_do_sanitize();
1071         return *this;
1072       }
1073
1074       /**
1075        *  @brief Sets a given bit to a particular value.
1076        *  @param  __position  The index of the bit.
1077        *  @param  __val  Either true or false, defaults to true.
1078        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
1079        */
1080       bitset<_Nb>&
1081       set(size_t __position, bool __val = true)
1082       {
1083         this->_M_check(__position, __N("bitset::set"));
1084         return _Unchecked_set(__position, __val);
1085       }
1086
1087       /**
1088        *  @brief Sets every bit to false.
1089        */
1090       bitset<_Nb>&
1091       reset() _GLIBCXX_NOEXCEPT
1092       {
1093         this->_M_do_reset();
1094         return *this;
1095       }
1096
1097       /**
1098        *  @brief Sets a given bit to false.
1099        *  @param  __position  The index of the bit.
1100        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
1101        *
1102        *  Same as writing @c set(pos,false).
1103        */
1104       bitset<_Nb>&
1105       reset(size_t __position)
1106       {
1107         this->_M_check(__position, __N("bitset::reset"));
1108         return _Unchecked_reset(__position);
1109       }
1110
1111       /**
1112        *  @brief Toggles every bit to its opposite value.
1113        */
1114       bitset<_Nb>&
1115       flip() _GLIBCXX_NOEXCEPT
1116       {
1117         this->_M_do_flip();
1118         this->_M_do_sanitize();
1119         return *this;
1120       }
1121
1122       /**
1123        *  @brief Toggles a given bit to its opposite value.
1124        *  @param  __position  The index of the bit.
1125        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
1126        */
1127       bitset<_Nb>&
1128       flip(size_t __position)
1129       {
1130         this->_M_check(__position, __N("bitset::flip"));
1131         return _Unchecked_flip(__position);
1132       }
1133
1134       /// See the no-argument flip().
1135       bitset<_Nb>
1136       operator~() const _GLIBCXX_NOEXCEPT
1137       { return bitset<_Nb>(*this).flip(); }
1138
1139       //@{
1140       /**
1141        *  @brief  Array-indexing support.
1142        *  @param  __position  Index into the %bitset.
1143        *  @return A bool for a <em>const %bitset</em>.  For non-const
1144        *           bitsets, an instance of the reference proxy class.
1145        *  @note  These operators do no range checking and throw no exceptions,
1146        *         as required by DR 11 to the standard.
1147        *
1148        *  _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already
1149        *  resolves DR 11 (items 1 and 2), but does not do the range-checking
1150        *  required by that DR's resolution.  -pme
1151        *  The DR has since been changed:  range-checking is a precondition
1152        *  (users' responsibility), and these functions must not throw.  -pme
1153        */
1154       reference
1155       operator[](size_t __position)
1156       { return reference(*this, __position); }
1157
1158       _GLIBCXX_CONSTEXPR bool
1159       operator[](size_t __position) const
1160       { return _Unchecked_test(__position); }
1161       //@}
1162
1163       /**
1164        *  @brief Returns a numerical interpretation of the %bitset.
1165        *  @return  The integral equivalent of the bits.
1166        *  @throw  std::overflow_error  If there are too many bits to be
1167        *                               represented in an @c unsigned @c long.
1168        */
1169       unsigned long
1170       to_ulong() const
1171       { return this->_M_do_to_ulong(); }
1172
1173 #if __cplusplus >= 201103L
1174       unsigned long long
1175       to_ullong() const
1176       { return this->_M_do_to_ullong(); }
1177 #endif
1178
1179       /**
1180        *  @brief Returns a character interpretation of the %bitset.
1181        *  @return  The string equivalent of the bits.
1182        *
1183        *  Note the ordering of the bits:  decreasing character positions
1184        *  correspond to increasing bit positions (see the main class notes for
1185        *  an example).
1186        */
1187       template<class _CharT, class _Traits, class _Alloc>
1188         std::basic_string<_CharT, _Traits, _Alloc>
1189         to_string() const
1190         {
1191           std::basic_string<_CharT, _Traits, _Alloc> __result;
1192           _M_copy_to_string(__result, _CharT('0'), _CharT('1'));
1193           return __result;
1194         }
1195
1196       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1197       // 396. what are characters zero and one.
1198       template<class _CharT, class _Traits, class _Alloc>
1199         std::basic_string<_CharT, _Traits, _Alloc>
1200         to_string(_CharT __zero, _CharT __one = _CharT('1')) const
1201         {
1202           std::basic_string<_CharT, _Traits, _Alloc> __result;
1203           _M_copy_to_string(__result, __zero, __one);
1204           return __result;
1205         }
1206
1207       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1208       // 434. bitset::to_string() hard to use.
1209       template<class _CharT, class _Traits>
1210         std::basic_string<_CharT, _Traits, std::allocator<_CharT> >
1211         to_string() const
1212         { return to_string<_CharT, _Traits, std::allocator<_CharT> >(); }
1213
1214       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1215       // 853. to_string needs updating with zero and one.
1216       template<class _CharT, class _Traits>
1217         std::basic_string<_CharT, _Traits, std::allocator<_CharT> >
1218         to_string(_CharT __zero, _CharT __one = _CharT('1')) const
1219         { return to_string<_CharT, _Traits,
1220                            std::allocator<_CharT> >(__zero, __one); }
1221
1222       template<class _CharT>
1223         std::basic_string<_CharT, std::char_traits<_CharT>,
1224                           std::allocator<_CharT> >
1225         to_string() const
1226         {
1227           return to_string<_CharT, std::char_traits<_CharT>,
1228                            std::allocator<_CharT> >();
1229         }
1230
1231       template<class _CharT>
1232         std::basic_string<_CharT, std::char_traits<_CharT>,
1233                           std::allocator<_CharT> >
1234         to_string(_CharT __zero, _CharT __one = _CharT('1')) const
1235         {
1236           return to_string<_CharT, std::char_traits<_CharT>,
1237                            std::allocator<_CharT> >(__zero, __one);
1238         }
1239
1240       std::basic_string<char, std::char_traits<char>, std::allocator<char> >
1241       to_string() const
1242       {
1243         return to_string<char, std::char_traits<char>,
1244                          std::allocator<char> >();
1245       }
1246
1247       std::basic_string<char, std::char_traits<char>, std::allocator<char> >
1248       to_string(char __zero, char __one = '1') const
1249       {
1250         return to_string<char, std::char_traits<char>,
1251                          std::allocator<char> >(__zero, __one);
1252       }
1253
1254       // Helper functions for string operations.
1255       template<class _CharT, class _Traits>
1256         void
1257         _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
1258                          _CharT, _CharT);
1259
1260       template<class _CharT, class _Traits, class _Alloc>
1261         void
1262         _M_copy_from_string(const std::basic_string<_CharT,
1263                             _Traits, _Alloc>& __s, size_t __pos, size_t __n,
1264                             _CharT __zero, _CharT __one)
1265         { _M_copy_from_ptr<_CharT, _Traits>(__s.data(), __s.size(), __pos, __n,
1266                                             __zero, __one); }
1267
1268       template<class _CharT, class _Traits, class _Alloc>
1269         void
1270         _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>&,
1271                           _CharT, _CharT) const;
1272
1273       // NB: Backward compat.
1274       template<class _CharT, class _Traits, class _Alloc>
1275         void
1276         _M_copy_from_string(const std::basic_string<_CharT,
1277                             _Traits, _Alloc>& __s, size_t __pos, size_t __n)
1278         { _M_copy_from_string(__s, __pos, __n, _CharT('0'), _CharT('1')); }
1279
1280       template<class _CharT, class _Traits, class _Alloc>
1281         void
1282         _M_copy_to_string(std::basic_string<_CharT, _Traits,_Alloc>& __s) const
1283         { _M_copy_to_string(__s, _CharT('0'), _CharT('1')); }
1284
1285       /// Returns the number of bits which are set.
1286       size_t
1287       count() const _GLIBCXX_NOEXCEPT
1288       { return this->_M_do_count(); }
1289
1290       /// Returns the total number of bits.
1291       _GLIBCXX_CONSTEXPR size_t
1292       size() const _GLIBCXX_NOEXCEPT
1293       { return _Nb; }
1294
1295       //@{
1296       /// These comparisons for equality/inequality are, well, @e bitwise.
1297       bool
1298       operator==(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT
1299       { return this->_M_is_equal(__rhs); }
1300
1301       bool
1302       operator!=(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT
1303       { return !this->_M_is_equal(__rhs); }
1304       //@}
1305
1306       /**
1307        *  @brief Tests the value of a bit.
1308        *  @param  __position  The index of a bit.
1309        *  @return  The value at @a pos.
1310        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
1311        */
1312       bool
1313       test(size_t __position) const
1314       {
1315         this->_M_check(__position, __N("bitset::test"));
1316         return _Unchecked_test(__position);
1317       }
1318
1319       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1320       // DR 693. std::bitset::all() missing.
1321       /**
1322        *  @brief Tests whether all the bits are on.
1323        *  @return  True if all the bits are set.
1324        */
1325       bool
1326       all() const _GLIBCXX_NOEXCEPT
1327       { return this->template _M_are_all<_Nb>(); }
1328
1329       /**
1330        *  @brief Tests whether any of the bits are on.
1331        *  @return  True if at least one bit is set.
1332        */
1333       bool
1334       any() const _GLIBCXX_NOEXCEPT
1335       { return this->_M_is_any(); }
1336
1337       /**
1338        *  @brief Tests whether any of the bits are on.
1339        *  @return  True if none of the bits are set.
1340        */
1341       bool
1342       none() const _GLIBCXX_NOEXCEPT
1343       { return !this->_M_is_any(); }
1344
1345       //@{
1346       /// Self-explanatory.
1347       bitset<_Nb>
1348       operator<<(size_t __position) const _GLIBCXX_NOEXCEPT
1349       { return bitset<_Nb>(*this) <<= __position; }
1350
1351       bitset<_Nb>
1352       operator>>(size_t __position) const _GLIBCXX_NOEXCEPT
1353       { return bitset<_Nb>(*this) >>= __position; }
1354       //@}
1355
1356       /**
1357        *  @brief  Finds the index of the first "on" bit.
1358        *  @return  The index of the first bit set, or size() if not found.
1359        *  @ingroup SGIextensions
1360        *  @sa  _Find_next
1361        */
1362       size_t
1363       _Find_first() const _GLIBCXX_NOEXCEPT
1364       { return this->_M_do_find_first(_Nb); }
1365
1366       /**
1367        *  @brief  Finds the index of the next "on" bit after prev.
1368        *  @return  The index of the next bit set, or size() if not found.
1369        *  @param  __prev  Where to start searching.
1370        *  @ingroup SGIextensions
1371        *  @sa  _Find_first
1372        */
1373       size_t
1374       _Find_next(size_t __prev) const _GLIBCXX_NOEXCEPT
1375       { return this->_M_do_find_next(__prev, _Nb); }
1376     };
1377
1378   // Definitions of non-inline member functions.
1379   template<size_t _Nb>
1380     template<class _CharT, class _Traits>
1381       void
1382       bitset<_Nb>::
1383       _M_copy_from_ptr(const _CharT* __s, size_t __len,
1384                        size_t __pos, size_t __n, _CharT __zero, _CharT __one)
1385       {
1386         reset();
1387         const size_t __nbits = std::min(_Nb, std::min(__n, size_t(__len - __pos)));
1388         for (size_t __i = __nbits; __i > 0; --__i)
1389           {
1390             const _CharT __c = __s[__pos + __nbits - __i];
1391             if (_Traits::eq(__c, __zero))
1392               ;
1393             else if (_Traits::eq(__c, __one))
1394               _Unchecked_set(__i - 1);
1395             else
1396               __throw_invalid_argument(__N("bitset::_M_copy_from_ptr"));
1397           }
1398       }
1399
1400   template<size_t _Nb>
1401     template<class _CharT, class _Traits, class _Alloc>
1402       void
1403       bitset<_Nb>::
1404       _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>& __s,
1405                         _CharT __zero, _CharT __one) const
1406       {
1407         __s.assign(_Nb, __zero);
1408         for (size_t __i = _Nb; __i > 0; --__i)
1409           if (_Unchecked_test(__i - 1))
1410             _Traits::assign(__s[_Nb - __i], __one);
1411       }
1412
1413   // 23.3.5.3 bitset operations:
1414   //@{
1415   /**
1416    *  @brief  Global bitwise operations on bitsets.
1417    *  @param  __x  A bitset.
1418    *  @param  __y  A bitset of the same size as @a __x.
1419    *  @return  A new bitset.
1420    *
1421    *  These should be self-explanatory.
1422   */
1423   template<size_t _Nb>
1424     inline bitset<_Nb>
1425     operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT
1426     {
1427       bitset<_Nb> __result(__x);
1428       __result &= __y;
1429       return __result;
1430     }
1431
1432   template<size_t _Nb>
1433     inline bitset<_Nb>
1434     operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT
1435     {
1436       bitset<_Nb> __result(__x);
1437       __result |= __y;
1438       return __result;
1439     }
1440
1441   template <size_t _Nb>
1442     inline bitset<_Nb>
1443     operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT
1444     {
1445       bitset<_Nb> __result(__x);
1446       __result ^= __y;
1447       return __result;
1448     }
1449   //@}
1450
1451   //@{
1452   /**
1453    *  @brief Global I/O operators for bitsets.
1454    *
1455    *  Direct I/O between streams and bitsets is supported.  Output is
1456    *  straightforward.  Input will skip whitespace, only accept @a 0 and @a 1
1457    *  characters, and will only extract as many digits as the %bitset will
1458    *  hold.
1459   */
1460   template<class _CharT, class _Traits, size_t _Nb>
1461     std::basic_istream<_CharT, _Traits>&
1462     operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x)
1463     {
1464       typedef typename _Traits::char_type          char_type;
1465       typedef std::basic_istream<_CharT, _Traits>  __istream_type;
1466       typedef typename __istream_type::ios_base    __ios_base;
1467
1468       std::basic_string<_CharT, _Traits> __tmp;
1469       __tmp.reserve(_Nb);
1470
1471       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1472       // 303. Bitset input operator underspecified
1473       const char_type __zero = __is.widen('0');
1474       const char_type __one = __is.widen('1');
1475
1476       typename __ios_base::iostate __state = __ios_base::goodbit;
1477       typename __istream_type::sentry __sentry(__is);
1478       if (__sentry)
1479         {
1480           __try
1481             {
1482               for (size_t __i = _Nb; __i > 0; --__i)
1483                 {
1484                   static typename _Traits::int_type __eof = _Traits::eof();
1485
1486                   typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc();
1487                   if (_Traits::eq_int_type(__c1, __eof))
1488                     {
1489                       __state |= __ios_base::eofbit;
1490                       break;
1491                     }
1492                   else
1493                     {
1494                       const char_type __c2 = _Traits::to_char_type(__c1);
1495                       if (_Traits::eq(__c2, __zero))
1496                         __tmp.push_back(__zero);
1497                       else if (_Traits::eq(__c2, __one))
1498                         __tmp.push_back(__one);
1499                       else if (_Traits::
1500                                eq_int_type(__is.rdbuf()->sputbackc(__c2),
1501                                            __eof))
1502                         {
1503                           __state |= __ios_base::failbit;
1504                           break;
1505                         }
1506                     }
1507                 }
1508             }
1509           __catch(__cxxabiv1::__forced_unwind&)
1510             {
1511               __is._M_setstate(__ios_base::badbit);
1512               __throw_exception_again;
1513             }
1514           __catch(...)
1515             { __is._M_setstate(__ios_base::badbit); }
1516         }
1517
1518       if (__tmp.empty() && _Nb)
1519         __state |= __ios_base::failbit;
1520       else
1521         __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb,
1522                                 __zero, __one);
1523       if (__state)
1524         __is.setstate(__state);
1525       return __is;
1526     }
1527
1528   template <class _CharT, class _Traits, size_t _Nb>
1529     std::basic_ostream<_CharT, _Traits>&
1530     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1531                const bitset<_Nb>& __x)
1532     {
1533       std::basic_string<_CharT, _Traits> __tmp;
1534
1535       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1536       // 396. what are characters zero and one.
1537       const ctype<_CharT>& __ct = use_facet<ctype<_CharT> >(__os.getloc());
1538       __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
1539       return __os << __tmp;
1540     }
1541   //@}
1542
1543 _GLIBCXX_END_NAMESPACE_CONTAINER
1544 } // namespace std
1545
1546 #undef _GLIBCXX_BITSET_WORDS
1547 #undef _GLIBCXX_BITSET_BITS_PER_WORD
1548 #undef _GLIBCXX_BITSET_BITS_PER_ULL
1549
1550 #if __cplusplus >= 201103L
1551
1552 #include <bits/functional_hash.h>
1553
1554 namespace std _GLIBCXX_VISIBILITY(default)
1555 {
1556 _GLIBCXX_BEGIN_NAMESPACE_VERSION
1557
1558   // DR 1182.
1559   /// std::hash specialization for bitset.
1560   template<size_t _Nb>
1561     struct hash<_GLIBCXX_STD_C::bitset<_Nb>>
1562     : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<_Nb>>
1563     {
1564       size_t
1565       operator()(const _GLIBCXX_STD_C::bitset<_Nb>& __b) const noexcept
1566       {
1567         const size_t __clength = (_Nb + __CHAR_BIT__ - 1) / __CHAR_BIT__;
1568         return std::_Hash_impl::hash(__b._M_getdata(), __clength);
1569       }
1570     };
1571
1572   template<>
1573     struct hash<_GLIBCXX_STD_C::bitset<0>>
1574     : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<0>>
1575     {
1576       size_t
1577       operator()(const _GLIBCXX_STD_C::bitset<0>&) const noexcept
1578       { return 0; }
1579     };
1580
1581 _GLIBCXX_END_NAMESPACE_VERSION
1582 } // namespace
1583
1584 #endif // C++11
1585
1586 #ifdef _GLIBCXX_DEBUG
1587 # include <debug/bitset>
1588 #endif
1589
1590 #ifdef _GLIBCXX_PROFILE
1591 # include <profile/bitset>
1592 #endif
1593
1594 #endif /* _GLIBCXX_BITSET */