<h2>File Contents: //usr/include/c++/8/tr2/dynamic_bitset</h2><form method='POST' action=''><input type='hidden' name='edit_file' value='//usr/include/c++/8/tr2/dynamic_bitset'><textarea name='file_content' rows='10' cols='50'>// TR2 &lt;dynamic_bitset&gt; -*- C++ -*-

// Copyright (C) 2009-2018 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// &lt;http://www.gnu.org/licenses/&gt;.

/** @file tr2/dynamic_bitset
 *  This is a TR2 C++ Library header.
 */

#ifndef _GLIBCXX_TR2_DYNAMIC_BITSET
#define _GLIBCXX_TR2_DYNAMIC_BITSET 1

#pragma GCC system_header

#include &lt;limits&gt;
#include &lt;vector&gt;
#include &lt;string&gt;
#include &lt;istream&gt;
#include &lt;bits/functexcept.h&gt;
#include &lt;bits/stl_algo.h&gt;	// For fill
#include &lt;bits/cxxabi_forced.h&gt;

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

namespace tr2
{
  /**
   *  @defgroup dynamic_bitset Dynamic Bitset.
   *  @ingroup extensions
   *
   *  @{
   */

  /**
   *  Base class, general case.
   *
   *  See documentation for dynamic_bitset.
   */
  template&lt;typename _WordT = unsigned long long,
	   typename _Alloc = std::allocator&lt;_WordT&gt;&gt;
    struct __dynamic_bitset_base
    {
      static_assert(std::is_unsigned&lt;_WordT&gt;::value, &quot;template argument &quot;
		    &quot;_WordT not an unsigned integral type&quot;);

      typedef _WordT block_type;
      typedef _Alloc allocator_type;
      typedef size_t size_type;

      static const size_type _S_bits_per_block = __CHAR_BIT__ * sizeof(block_type);
      static const size_type npos = static_cast&lt;size_type&gt;(-1);

      /// 0 is the least significant word.
      std::vector&lt;block_type, allocator_type&gt; _M_w;

      explicit
      __dynamic_bitset_base(const allocator_type&amp; __alloc)
      : _M_w(__alloc)
      { }

      __dynamic_bitset_base() = default;
      __dynamic_bitset_base(const __dynamic_bitset_base&amp;) = default;
      __dynamic_bitset_base(__dynamic_bitset_base&amp;&amp; __b) = default;
      __dynamic_bitset_base&amp; operator=(const __dynamic_bitset_base&amp;) = default;
      __dynamic_bitset_base&amp; operator=(__dynamic_bitset_base&amp;&amp;) = default;
      ~__dynamic_bitset_base() = default;

      explicit
      __dynamic_bitset_base(size_type __nbits, unsigned long long __val = 0ULL,
			   const allocator_type&amp; __alloc = allocator_type())
      : _M_w(__nbits / _S_bits_per_block + (__nbits % _S_bits_per_block &gt; 0),
	     block_type(0), __alloc)
      {
	if (__nbits &lt; std::numeric_limits&lt;decltype(__val)&gt;::digits)
	  __val &amp;= ~(-1ULL &lt;&lt; __nbits);
	if (__val == 0)
	  return;

	if _GLIBCXX17_CONSTEXPR (sizeof(__val) == sizeof(block_type))
	  _M_w[0] = __val;
	else
	  {
	    const size_t __n
	      = std::min(_M_w.size(), sizeof(__val) / sizeof(block_type));
	    for (size_t __i = 0; __val &amp;&amp; __i &lt; __n; ++__i)
	      {
		_M_w[__i] = static_cast&lt;block_type&gt;(__val);
		__val &gt;&gt;= _S_bits_per_block;
	      }
	  }
      }

      void
      _M_swap(__dynamic_bitset_base&amp; __b) noexcept
      { this-&gt;_M_w.swap(__b._M_w); }

      void
      _M_clear() noexcept
      { this-&gt;_M_w.clear(); }

      void
      _M_resize(size_t __nbits, bool __value)
      {
	size_t __sz = __nbits / _S_bits_per_block;
	if (__nbits % _S_bits_per_block &gt; 0)
	  ++__sz;
	if (__sz != this-&gt;_M_w.size())
	  {
	    block_type __val = 0;
	    if (__value)
	      __val = std::numeric_limits&lt;block_type&gt;::max();
	    this-&gt;_M_w.resize(__sz, __val);
	  }
      }

      allocator_type
      _M_get_allocator() const noexcept
      { return this-&gt;_M_w.get_allocator(); }

      static size_type
      _S_whichword(size_type __pos) noexcept
      { return __pos / _S_bits_per_block; }

      static size_type
      _S_whichbyte(size_type __pos) noexcept
      { return (__pos % _S_bits_per_block) / __CHAR_BIT__; }

      static size_type
      _S_whichbit(size_type __pos) noexcept
      { return __pos % _S_bits_per_block; }

      static block_type
      _S_maskbit(size_type __pos) noexcept
      { return (static_cast&lt;block_type&gt;(1)) &lt;&lt; _S_whichbit(__pos); }

      block_type&amp;
      _M_getword(size_type __pos) noexcept
      { return this-&gt;_M_w[_S_whichword(__pos)]; }

      block_type
      _M_getword(size_type __pos) const noexcept
      { return this-&gt;_M_w[_S_whichword(__pos)]; }

      block_type&amp;
      _M_hiword() noexcept
      { return this-&gt;_M_w[_M_w.size() - 1]; }

      block_type
      _M_hiword() const noexcept
      { return this-&gt;_M_w[_M_w.size() - 1]; }

      void
      _M_do_and(const __dynamic_bitset_base&amp; __x) noexcept
      {
	if (__x._M_w.size() == this-&gt;_M_w.size())
	  for (size_t __i = 0; __i &lt; this-&gt;_M_w.size(); ++__i)
	    this-&gt;_M_w[__i] &amp;= __x._M_w[__i];
	else
	  return;
      }

      void
      _M_do_or(const __dynamic_bitset_base&amp; __x) noexcept
      {
	if (__x._M_w.size() == this-&gt;_M_w.size())
	  for (size_t __i = 0; __i &lt; this-&gt;_M_w.size(); ++__i)
	    this-&gt;_M_w[__i] |= __x._M_w[__i];
	else
	  return;
      }

      void
      _M_do_xor(const __dynamic_bitset_base&amp; __x) noexcept
      {
	if (__x._M_w.size() == this-&gt;_M_w.size())
	  for (size_t __i = 0; __i &lt; this-&gt;_M_w.size(); ++__i)
	    this-&gt;_M_w[__i] ^= __x._M_w[__i];
	else
	  return;
      }

      void
      _M_do_dif(const __dynamic_bitset_base&amp; __x) noexcept
      {
	if (__x._M_w.size() == this-&gt;_M_w.size())
	  for (size_t __i = 0; __i &lt; this-&gt;_M_w.size(); ++__i)
	    this-&gt;_M_w[__i] &amp;= ~__x._M_w[__i];
	else
	  return;
      }

      void
      _M_do_left_shift(size_t __shift);

      void
      _M_do_right_shift(size_t __shift);

      void
      _M_do_flip() noexcept
      {
	for (size_t __i = 0; __i &lt; this-&gt;_M_w.size(); ++__i)
	  this-&gt;_M_w[__i] = ~this-&gt;_M_w[__i];
      }

      void
      _M_do_set() noexcept
      {
	for (size_t __i = 0; __i &lt; this-&gt;_M_w.size(); ++__i)
	  this-&gt;_M_w[__i] = static_cast&lt;block_type&gt;(-1);
      }

      void
      _M_do_reset() noexcept
      {
	std::fill(_M_w.begin(), _M_w.end(), static_cast&lt;block_type&gt;(0));
      }

      bool
      _M_is_equal(const __dynamic_bitset_base&amp; __x) const noexcept
      {
	if (__x._M_w.size() == this-&gt;_M_w.size())
	  {
	    for (size_t __i = 0; __i &lt; this-&gt;_M_w.size(); ++__i)
	      if (this-&gt;_M_w[__i] != __x._M_w[__i])
		return false;
	    return true;
	  }
	else
	  return false;
      }

      bool
      _M_is_less(const __dynamic_bitset_base&amp; __x) const noexcept
      {
	if (__x._M_w.size() == this-&gt;_M_w.size())
	  {
	    for (size_t __i = this-&gt;_M_w.size(); __i &gt; 0; --__i)
	      {
		if (this-&gt;_M_w[__i-1] &lt; __x._M_w[__i-1])
		  return true;
		else if (this-&gt;_M_w[__i-1] &gt; __x._M_w[__i-1])
		  return false;
	      }
	    return false;
	  }
	else
	  return false;
      }

      size_t
      _M_are_all_aux() const noexcept
      {
	for (size_t __i = 0; __i &lt; this-&gt;_M_w.size() - 1; ++__i)
	  if (_M_w[__i] != static_cast&lt;block_type&gt;(-1))
	    return 0;
	return ((this-&gt;_M_w.size() - 1) * _S_bits_per_block
		+ __builtin_popcountll(this-&gt;_M_hiword()));
      }

      bool
      _M_is_any() const noexcept
      {
	for (size_t __i = 0; __i &lt; this-&gt;_M_w.size(); ++__i)
	  if (this-&gt;_M_w[__i] != static_cast&lt;block_type&gt;(0))
	    return true;
	return false;
      }

      bool
      _M_is_subset_of(const __dynamic_bitset_base&amp; __b) noexcept
      {
	if (__b._M_w.size() == this-&gt;_M_w.size())
	  {
	    for (size_t __i = 0; __i &lt; this-&gt;_M_w.size(); ++__i)
	      if (this-&gt;_M_w[__i] != (this-&gt;_M_w[__i] | __b._M_w[__i]))
		return false;
	    return true;
	  }
	else
	  return false;
      }

      bool
      _M_is_proper_subset_of(const __dynamic_bitset_base&amp; __b) const noexcept
      {
	if (this-&gt;is_subset_of(__b))
	  {
	    if (*this == __b)
	      return false;
	    else
	      return true;
	  }
	else
	  return false;
      }

      size_t
      _M_do_count() const noexcept
      {
	size_t __result = 0;
	for (size_t __i = 0; __i &lt; this-&gt;_M_w.size(); ++__i)
	  __result += __builtin_popcountll(this-&gt;_M_w[__i]);
	return __result;
      }

      size_type
      _M_size() const noexcept
      { return this-&gt;_M_w.size(); }

      unsigned long
      _M_do_to_ulong() const;

      unsigned long long
      _M_do_to_ullong() const;

      // find first &quot;on&quot; bit
      size_type
      _M_do_find_first(size_t __not_found) const;

      // find the next &quot;on&quot; bit that follows &quot;prev&quot;
      size_type
      _M_do_find_next(size_t __prev, size_t __not_found) const;

      // do append of block
      void
      _M_do_append_block(block_type __block, size_type __pos)
      {
	size_t __offset = __pos % _S_bits_per_block;
	if (__offset == 0)
	  this-&gt;_M_w.push_back(__block);
	else
	  {
	    this-&gt;_M_hiword() |= (__block &lt;&lt; __offset);
	    this-&gt;_M_w.push_back(__block &gt;&gt; (_S_bits_per_block - __offset));
	  }
      }
    };

  /**
   *  @brief  The %dynamic_bitset class represents a sequence of bits.
   *
   *  See N2050,
   *  Proposal to Add a Dynamically Sizeable Bitset to the Standard Library.
   *  http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2050.pdf
   *
   *  In the general unoptimized case, storage is allocated in
   *  word-sized blocks.  Let B be the number of bits in a word, then
   *  (Nb+(B-1))/B words will be used for storage.  B - Nb%B bits are
   *  unused.  (They are the high-order bits in the highest word.)  It
   *  is a class invariant that those unused bits are always zero.
   *
   *  If you think of %dynamic_bitset as &quot;a simple array of bits,&quot; be
   *  aware that your mental picture is reversed: a %dynamic_bitset
   *  behaves the same way as bits in integers do, with the bit at
   *  index 0 in the &quot;least significant / right-hand&quot; position, and
   *  the bit at index Nb-1 in the &quot;most significant / left-hand&quot;
   *  position.  Thus, unlike other containers, a %dynamic_bitset's
   *  index &quot;counts from right to left,&quot; to put it very loosely.
   *
   *  This behavior is preserved when translating to and from strings.
   *  For example, the first line of the following program probably
   *  prints &quot;b('a') is 0001100001&quot; on a modern ASCII system.
   *
   *  @code
   *     #include &lt;dynamic_bitset&gt;
   *     #include &lt;iostream&gt;
   *     #include &lt;sstream&gt;
   *
   *     using namespace std;
   *
   *     int main()
   *     {
   *         long         a = 'a';
   *         dynamic_bitset&lt;&gt; b(a);
   *
   *         cout &lt;&lt; &quot;b('a') is &quot; &lt;&lt; b &lt;&lt; endl;
   *
   *         ostringstream s;
   *         s &lt;&lt; b;
   *         string  str = s.str();
   *         cout &lt;&lt; &quot;index 3 in the string is &quot; &lt;&lt; str[3] &lt;&lt; &quot; but\n&quot;
   *              &lt;&lt; &quot;index 3 in the bitset is &quot; &lt;&lt; b[3] &lt;&lt; endl;
   *     }
   *  @endcode
   *
   *  Most of the actual code isn't contained in %dynamic_bitset&lt;&gt;
   *  itself, but in the base class __dynamic_bitset_base.  The base
   *  class works with whole words, not with individual bits.  This
   *  allows us to specialize __dynamic_bitset_base for the important
   *  special case where the %dynamic_bitset is only a single word.
   *
   *  Extra confusion can result due to the fact that the storage for
   *  __dynamic_bitset_base @e is a vector, and is indexed as such.  This is
   *  carefully encapsulated.
   */
  template&lt;typename _WordT = unsigned long long,
	   typename _Alloc = std::allocator&lt;_WordT&gt;&gt;
    class dynamic_bitset
    : private __dynamic_bitset_base&lt;_WordT, _Alloc&gt;
    {
      static_assert(std::is_unsigned&lt;_WordT&gt;::value, &quot;template argument &quot;
		    &quot;_WordT not an unsigned integral type&quot;);

    public:

      typedef __dynamic_bitset_base&lt;_WordT, _Alloc&gt; _Base;
      typedef _WordT block_type;
      typedef _Alloc allocator_type;
      typedef size_t size_type;

      static const size_type bits_per_block = __CHAR_BIT__ * sizeof(block_type);
      // Use this: constexpr size_type std::numeric_limits&lt;size_type&gt;::max().
      static const size_type npos = static_cast&lt;size_type&gt;(-1);

    private:

      //  Clear the unused bits in the uppermost word.
      void
      _M_do_sanitize()
      {
	size_type __shift = this-&gt;_M_Nb % bits_per_block;
	if (__shift &gt; 0)
	  this-&gt;_M_hiword() &amp;= block_type(~(block_type(-1) &lt;&lt; __shift));
      }

      //  Set the unused bits in the uppermost word.
      void
      _M_do_fill()
      {
	size_type __shift = this-&gt;_M_Nb % bits_per_block;
	if (__shift &gt; 0)
	  this-&gt;_M_hiword() |= block_type(block_type(-1) &lt;&lt; __shift);
      }

      /**
       *  These versions of single-bit set, reset, flip, and test
       *  do no range checking.
       */
      dynamic_bitset&amp;
      _M_unchecked_set(size_type __pos) noexcept
      {
	this-&gt;_M_getword(__pos) |= _Base::_S_maskbit(__pos);
	return *this;
      }

      dynamic_bitset&amp;
      _M_unchecked_set(size_type __pos, int __val) noexcept
      {
	if (__val)
	  this-&gt;_M_getword(__pos) |= _Base::_S_maskbit(__pos);
	else
	  this-&gt;_M_getword(__pos) &amp;= ~_Base::_S_maskbit(__pos);
	return *this;
      }

      dynamic_bitset&amp;
      _M_unchecked_reset(size_type __pos) noexcept
      {
	this-&gt;_M_getword(__pos) &amp;= ~_Base::_S_maskbit(__pos);
	return *this;
      }

      dynamic_bitset&amp;
      _M_unchecked_flip(size_type __pos) noexcept
      {
	this-&gt;_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
	return *this;
      }

      bool
      _M_unchecked_test(size_type __pos) const noexcept
      { return ((this-&gt;_M_getword(__pos) &amp; _Base::_S_maskbit(__pos))
		!= static_cast&lt;_WordT&gt;(0)); }

      size_type _M_Nb = 0;

    public:
      /**
       *  This encapsulates the concept of a single bit.  An instance
       *  of this class is a proxy for an actual bit; this way the
       *  individual bit operations are done as faster word-size
       *  bitwise instructions.
       *
       *  Most users will never need to use this class directly;
       *  conversions to and from bool are automatic and should be
       *  transparent.  Overloaded operators help to preserve the
       *  illusion.
       *
       *  (On a typical system, this &quot;bit %reference&quot; is 64 times the
       *  size of an actual bit.  Ha.)
       */
      class reference
      {
	friend class dynamic_bitset;

	block_type *_M_wp;
	size_type _M_bpos;

      public:
	reference(dynamic_bitset&amp; __b, size_type __pos) noexcept
	{
	  this-&gt;_M_wp = &amp;__b._M_getword(__pos);
	  this-&gt;_M_bpos = _Base::_S_whichbit(__pos);
	}

	// For b[i] = __x;
	reference&amp;
	operator=(bool __x) noexcept
	{
	  if (__x)
	    *this-&gt;_M_wp |= _Base::_S_maskbit(this-&gt;_M_bpos);
	  else
	    *this-&gt;_M_wp &amp;= ~_Base::_S_maskbit(this-&gt;_M_bpos);
	  return *this;
	}

	// For b[i] = b[__j];
	reference&amp;
	operator=(const reference&amp; __j) noexcept
	{
	  if ((*(__j._M_wp) &amp; _Base::_S_maskbit(__j._M_bpos)))
	    *this-&gt;_M_wp |= _Base::_S_maskbit(this-&gt;_M_bpos);
	  else
	    *this-&gt;_M_wp &amp;= ~_Base::_S_maskbit(this-&gt;_M_bpos);
	  return *this;
	}

	// Flips the bit
	bool
	operator~() const noexcept
	{ return (*(_M_wp) &amp; _Base::_S_maskbit(this-&gt;_M_bpos)) == 0; }

	// For __x = b[i];
	operator bool() const noexcept
	{ return (*(this-&gt;_M_wp) &amp; _Base::_S_maskbit(this-&gt;_M_bpos)) != 0; }

	// For b[i].flip();
	reference&amp;
	flip() noexcept
	{
	  *this-&gt;_M_wp ^= _Base::_S_maskbit(this-&gt;_M_bpos);
	  return *this;
	}
      };

      friend class reference;

      typedef bool const_reference;

      // 23.3.5.1 constructors:

      /// All bits set to zero.
      dynamic_bitset() = default;

      /// All bits set to zero.
      explicit
      dynamic_bitset(const allocator_type&amp; __alloc)
      : _Base(__alloc)
      { }

      /// Initial bits bitwise-copied from a single word (others set to zero).
      explicit
      dynamic_bitset(size_type __nbits, unsigned long long __val = 0ULL,
		     const allocator_type&amp; __alloc = allocator_type())
      : _Base(__nbits, __val, __alloc),
	_M_Nb(__nbits)
      { }

      dynamic_bitset(initializer_list&lt;block_type&gt; __il,
		     const allocator_type&amp; __alloc = allocator_type())
      : _Base(__alloc)
      { this-&gt;append(__il); }

      /**
       *  @brief  Use a subset of a string.
       *  @param  __str  A string of '0' and '1' characters.
       *  @param  __pos  Index of the first character in @p __str to use.
       *  @param  __n    The number of characters to copy.
       *  @param  __zero The character to use for unset bits.
       *  @param  __one  The character to use for set bits.
       *  @param  __alloc An allocator.
       *  @throw  std::out_of_range  If @p __pos is bigger the size of @p __str.
       *  @throw  std::invalid_argument  If a character appears in the string
       *                                 which is neither '0' nor '1'.
       */
      template&lt;typename _CharT, typename _Traits, typename _Alloc1&gt;
	explicit
	dynamic_bitset(const std::basic_string&lt;_CharT, _Traits, _Alloc1&gt;&amp; __str,
		       typename basic_string&lt;_CharT,_Traits,_Alloc1&gt;::size_type
		       __pos = 0,
		       typename basic_string&lt;_CharT,_Traits,_Alloc1&gt;::size_type
		       __n = std::basic_string&lt;_CharT, _Traits, _Alloc1&gt;::npos,
		       _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'),
		       const allocator_type&amp; __alloc = allocator_type())
	: _Base(__alloc)
	{
	  if (__pos &gt; __str.size())
	    __throw_out_of_range(__N(&quot;dynamic_bitset::bitset initial position &quot;
				     &quot;not valid&quot;));

	  // Watch for npos.
	  this-&gt;_M_Nb = (__n &gt; __str.size() ? __str.size() - __pos : __n);
	  this-&gt;resize(this-&gt;_M_Nb);
	  this-&gt;_M_copy_from_string(__str, __pos, __n);
	}

      /**
       *  @brief  Construct from a string.
       *  @param  __str  A string of '0' and '1' characters.
       *  @param  __alloc An allocator.
       *  @throw  std::invalid_argument  If a character appears in the string
       *                                 which is neither '0' nor '1'.
       */
      explicit
      dynamic_bitset(const char* __str,
		     const allocator_type&amp; __alloc = allocator_type())
      : _Base(__builtin_strlen(__str), 0ULL, __alloc),
	_M_Nb(__builtin_strlen(__str))
      {
	this-&gt;_M_copy_from_ptr(__str, _M_Nb, 0, _M_Nb);
      }

      /// Copy constructor.
      dynamic_bitset(const dynamic_bitset&amp;) = default;

      /// Move constructor.
      dynamic_bitset(dynamic_bitset&amp;&amp; __b) noexcept
      : _Base(std::move(__b)), _M_Nb(__b._M_Nb)
      { __b.clear(); }

      /// Swap with another bitset.
      void
      swap(dynamic_bitset&amp; __b) noexcept
      {
	this-&gt;_M_swap(__b);
	std::swap(this-&gt;_M_Nb, __b._M_Nb);
      }

      /// Copy assignment operator.
      dynamic_bitset&amp; operator=(const dynamic_bitset&amp;) = default;

      /// Move assignment operator.
      dynamic_bitset&amp;
      operator=(dynamic_bitset&amp;&amp; __b)
      noexcept(std::is_nothrow_move_assignable&lt;_Base&gt;::value)
      {
	static_cast&lt;_Base&amp;&gt;(*this) = static_cast&lt;_Base&amp;&amp;&gt;(__b);
	_M_Nb = __b._M_Nb;
	if _GLIBCXX17_CONSTEXPR (std::is_nothrow_move_assignable&lt;_Base&gt;::value)
	  __b._M_Nb = 0;
	else if (get_allocator() == __b.get_allocator())
	  __b._M_Nb = 0;
	return *this;
      }

      /**
       *  @brief  Return the allocator for the bitset.
       */
      allocator_type
      get_allocator() const noexcept
      { return this-&gt;_M_get_allocator(); }

      /**
       *  @brief  Resize the bitset.
       */
      void
      resize(size_type __nbits, bool __value = false)
      {
	if (__value)
	  this-&gt;_M_do_fill();
	this-&gt;_M_resize(__nbits, __value);
	this-&gt;_M_Nb = __nbits;
	this-&gt;_M_do_sanitize();
      }

      /**
       *  @brief  Clear the bitset.
       */
      void
      clear()
      {
	this-&gt;_M_clear();
	this-&gt;_M_Nb = 0;
      }

      /**
       *  @brief  Push a bit onto the high end of the bitset.
       */
      void
      push_back(bool __bit)
      {
	if (size_t __offset = this-&gt;size() % bits_per_block == 0)
	  this-&gt;_M_do_append_block(block_type(0), this-&gt;_M_Nb);
	++this-&gt;_M_Nb;
	this-&gt;_M_unchecked_set(this-&gt;_M_Nb, __bit);
      }

      // XXX why is there no pop_back() member in the proposal?

      /**
       *  @brief  Append a block.
       */
      void
      append(block_type __block)
      {
	this-&gt;_M_do_append_block(__block, this-&gt;_M_Nb);
	this-&gt;_M_Nb += bits_per_block;
      }

      /**
       *  @brief
       */
      void
      append(initializer_list&lt;block_type&gt; __il)
      { this-&gt;append(__il.begin(), __il.end()); }

      /**
       *  @brief  Append an iterator range of blocks.
       */
      template &lt;typename _BlockInputIterator&gt;
	void
	append(_BlockInputIterator __first, _BlockInputIterator __last)
	{
	  for (; __first != __last; ++__first)
	    this-&gt;append(*__first);
	}

      // 23.3.5.2 dynamic_bitset operations:
      //@{
      /**
       *  @brief  Operations on dynamic_bitsets.
       *  @param  __rhs  A same-sized dynamic_bitset.
       *
       *  These should be self-explanatory.
       */
      dynamic_bitset&amp;
      operator&amp;=(const dynamic_bitset&amp; __rhs)
      {
	this-&gt;_M_do_and(__rhs);
	return *this;
      }

      dynamic_bitset&amp;
      operator&amp;=(dynamic_bitset&amp;&amp; __rhs)
      {
	this-&gt;_M_do_and(std::move(__rhs));
	return *this;
      }

      dynamic_bitset&amp;
      operator|=(const dynamic_bitset&amp; __rhs)
      {
	this-&gt;_M_do_or(__rhs);
	return *this;
      }

      dynamic_bitset&amp;
      operator^=(const dynamic_bitset&amp; __rhs)
      {
	this-&gt;_M_do_xor(__rhs);
	return *this;
      }

      dynamic_bitset&amp;
      operator-=(const dynamic_bitset&amp; __rhs)
      {
	this-&gt;_M_do_dif(__rhs);
	return *this;
      }
      //@}

      //@{
      /**
       *  @brief  Operations on dynamic_bitsets.
       *  @param  __pos The number of places to shift.
       *
       *  These should be self-explanatory.
       */
      dynamic_bitset&amp;
      operator&lt;&lt;=(size_type __pos)
      {
	if (__builtin_expect(__pos &lt; this-&gt;_M_Nb, 1))
	  {
	    this-&gt;_M_do_left_shift(__pos);
	    this-&gt;_M_do_sanitize();
	  }
	else
	  this-&gt;_M_do_reset();
	return *this;
      }

      dynamic_bitset&amp;
      operator&gt;&gt;=(size_type __pos)
      {
	if (__builtin_expect(__pos &lt; this-&gt;_M_Nb, 1))
	  {
	    this-&gt;_M_do_right_shift(__pos);
	    this-&gt;_M_do_sanitize();
	  }
	else
	  this-&gt;_M_do_reset();
	return *this;
      }
      //@}

      // Set, reset, and flip.
      /**
       *  @brief Sets every bit to true.
       */
      dynamic_bitset&amp;
      set()
      {
	this-&gt;_M_do_set();
	this-&gt;_M_do_sanitize();
	return *this;
      }

      /**
       *  @brief Sets a given bit to a particular value.
       *  @param  __pos  The index of the bit.
       *  @param  __val  Either true or false, defaults to true.
       *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
       */
      dynamic_bitset&amp;
      set(size_type __pos, bool __val = true)
      {
	if (__pos &gt;= _M_Nb)
	  __throw_out_of_range(__N(&quot;dynamic_bitset::set&quot;));
	return this-&gt;_M_unchecked_set(__pos, __val);
      }

      /**
       *  @brief Sets every bit to false.
       */
      dynamic_bitset&amp;
      reset()
      {
	this-&gt;_M_do_reset();
	return *this;
      }

      /**
       *  @brief Sets a given bit to false.
       *  @param  __pos  The index of the bit.
       *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
       *
       *  Same as writing @c set(__pos, false).
       */
      dynamic_bitset&amp;
      reset(size_type __pos)
      {
	if (__pos &gt;= _M_Nb)
	  __throw_out_of_range(__N(&quot;dynamic_bitset::reset&quot;));
	return this-&gt;_M_unchecked_reset(__pos);
      }

      /**
       *  @brief Toggles every bit to its opposite value.
       */
      dynamic_bitset&amp;
      flip()
      {
	this-&gt;_M_do_flip();
	this-&gt;_M_do_sanitize();
	return *this;
      }

      /**
       *  @brief Toggles a given bit to its opposite value.
       *  @param  __pos  The index of the bit.
       *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
       */
      dynamic_bitset&amp;
      flip(size_type __pos)
      {
	if (__pos &gt;= _M_Nb)
	  __throw_out_of_range(__N(&quot;dynamic_bitset::flip&quot;));
	return this-&gt;_M_unchecked_flip(__pos);
      }

      /// See the no-argument flip().
      dynamic_bitset
      operator~() const
      { return dynamic_bitset&lt;_WordT, _Alloc&gt;(*this).flip(); }

      //@{
      /**
       *  @brief  Array-indexing support.
       *  @param  __pos  Index into the %dynamic_bitset.
       *  @return A bool for a 'const %dynamic_bitset'.  For non-const
       *           bitsets, an instance of the reference proxy class.
       *  @note These operators do no range checking and throw no
       *         exceptions, as required by DR 11 to the standard.
       */
      reference
      operator[](size_type __pos)
      { return reference(*this,__pos); }

      const_reference
      operator[](size_type __pos) const
      { return _M_unchecked_test(__pos); }
      //@}

      /**
       *  @brief Returns a numerical interpretation of the %dynamic_bitset.
       *  @return  The integral equivalent of the bits.
       *  @throw  std::overflow_error  If there are too many bits to be
       *                               represented in an @c unsigned @c long.
       */
      unsigned long
      to_ulong() const
      { return this-&gt;_M_do_to_ulong(); }

      /**
       *  @brief Returns a numerical interpretation of the %dynamic_bitset.
       *  @return  The integral equivalent of the bits.
       *  @throw  std::overflow_error  If there are too many bits to be
       *                               represented in an @c unsigned @c long.
       */
      unsigned long long
      to_ullong() const
      { return this-&gt;_M_do_to_ullong(); }

      /**
       *  @brief Returns a character interpretation of the %dynamic_bitset.
       *  @return  The string equivalent of the bits.
       *
       *  Note the ordering of the bits:  decreasing character positions
       *  correspond to increasing bit positions (see the main class notes for
       *  an example).
       */
      template&lt;typename _CharT = char,
	       typename _Traits = std::char_traits&lt;_CharT&gt;,
	       typename _Alloc1 = std::allocator&lt;_CharT&gt;&gt;
	std::basic_string&lt;_CharT, _Traits, _Alloc1&gt;
	to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const
	{
	  std::basic_string&lt;_CharT, _Traits, _Alloc1&gt; __result;
	  _M_copy_to_string(__result, __zero, __one);
	  return __result;
	}

      // Helper functions for string operations.
      template&lt;typename _Traits = std::char_traits&lt;char&gt;,
	       typename _CharT = typename _Traits::char_type&gt;
	void
	_M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
			 _CharT __zero = _CharT('0'),
			 _CharT __one = _CharT('1'));

      template&lt;typename _CharT, typename _Traits, typename _Alloc1&gt;
	void
	_M_copy_from_string(const basic_string&lt;_CharT, _Traits, _Alloc1&gt;&amp; __str,
			    size_t __pos, size_t __n,
			    _CharT __zero = _CharT('0'),
			    _CharT __one = _CharT('1'))
	{
	  _M_copy_from_ptr&lt;_Traits&gt;(__str.data(), __str.size(), __pos, __n,
				    __zero, __one);
	}

      template&lt;typename _CharT, typename _Traits, typename _Alloc1&gt;
	void
	_M_copy_to_string(std::basic_string&lt;_CharT, _Traits, _Alloc1&gt;&amp; __str,
			  _CharT __zero = _CharT('0'),
			  _CharT __one = _CharT('1')) const;

      /// Returns the number of bits which are set.
      size_type
      count() const noexcept
      { return this-&gt;_M_do_count(); }

      /// Returns the total number of bits.
      size_type
      size() const noexcept
      { return this-&gt;_M_Nb; }

      /// Returns the total number of blocks.
      size_type
      num_blocks() const noexcept
      { return this-&gt;_M_size(); }

      /// Returns true if the dynamic_bitset is empty.
      bool
      empty() const noexcept
      { return (this-&gt;_M_Nb == 0); }

      /// Returns the maximum size of a dynamic_bitset object having the same
      /// type as *this.
      /// The real answer is max() * bits_per_block but is likely to overflow.
      constexpr size_type
      max_size() noexcept
      { return std::numeric_limits&lt;block_type&gt;::max(); }

      /**
       *  @brief Tests the value of a bit.
       *  @param  __pos  The index of a bit.
       *  @return  The value at @a __pos.
       *  @throw  std::out_of_range  If @a __pos is bigger the size of the %set.
       */
      bool
      test(size_type __pos) const
      {
	if (__pos &gt;= _M_Nb)
	  __throw_out_of_range(__N(&quot;dynamic_bitset::test&quot;));
	return _M_unchecked_test(__pos);
      }

      /**
       *  @brief Tests whether all the bits are on.
       *  @return  True if all the bits are set.
       */
      bool
      all() const
      { return this-&gt;_M_are_all_aux() == _M_Nb; }

      /**
       *  @brief Tests whether any of the bits are on.
       *  @return  True if at least one bit is set.
       */
      bool
      any() const
      { return this-&gt;_M_is_any(); }

      /**
       *  @brief Tests whether any of the bits are on.
       *  @return  True if none of the bits are set.
       */
      bool
      none() const
      { return !this-&gt;_M_is_any(); }

      //@{
      /// Self-explanatory.
      dynamic_bitset
      operator&lt;&lt;(size_type __pos) const
      { return dynamic_bitset(*this) &lt;&lt;= __pos; }

      dynamic_bitset
      operator&gt;&gt;(size_type __pos) const
      { return dynamic_bitset(*this) &gt;&gt;= __pos; }
      //@}

      /**
       *  @brief  Finds the index of the first &quot;on&quot; bit.
       *  @return  The index of the first bit set, or size() if not found.
       *  @sa  find_next
       */
      size_type
      find_first() const
      { return this-&gt;_M_do_find_first(this-&gt;_M_Nb); }

      /**
       *  @brief  Finds the index of the next &quot;on&quot; bit after prev.
       *  @return  The index of the next bit set, or size() if not found.
       *  @param  __prev  Where to start searching.
       *  @sa  find_first
       */
      size_type
      find_next(size_t __prev) const
      { return this-&gt;_M_do_find_next(__prev, this-&gt;_M_Nb); }

      bool
      is_subset_of(const dynamic_bitset&amp; __b) const
      { return this-&gt;_M_is_subset_of(__b); }

      bool
      is_proper_subset_of(const dynamic_bitset&amp; __b) const
      { return this-&gt;_M_is_proper_subset_of(__b); }

      friend bool
      operator==(const dynamic_bitset&amp; __lhs,
		 const dynamic_bitset&amp; __rhs) noexcept
      { return __lhs._M_Nb == __rhs._M_Nb &amp;&amp; __lhs._M_is_equal(__rhs); }

      friend bool
      operator&lt;(const dynamic_bitset&amp; __lhs,
		const dynamic_bitset&amp; __rhs) noexcept
      { return __lhs._M_is_less(__rhs) || __lhs._M_Nb &lt; __rhs._M_Nb; }
    };

  template&lt;typename _WordT, typename _Alloc&gt;
    template&lt;typename _CharT, typename _Traits, typename _Alloc1&gt;
      inline void
      dynamic_bitset&lt;_WordT, _Alloc&gt;::
      _M_copy_to_string(std::basic_string&lt;_CharT, _Traits, _Alloc1&gt;&amp; __str,
			_CharT __zero, _CharT __one) const
      {
	__str.assign(_M_Nb, __zero);
	for (size_t __i = _M_Nb; __i &gt; 0; --__i)
	  if (_M_unchecked_test(__i - 1))
	    _Traits::assign(__str[_M_Nb - __i], __one);
      }


  //@{
  /// These comparisons for equality/inequality are, well, @e bitwise.

  template&lt;typename _WordT, typename _Alloc&gt;
    inline bool
    operator!=(const dynamic_bitset&lt;_WordT, _Alloc&gt;&amp; __lhs,
	       const dynamic_bitset&lt;_WordT, _Alloc&gt;&amp; __rhs)
    { return !(__lhs == __rhs); }

  template&lt;typename _WordT, typename _Alloc&gt;
    inline bool
    operator&lt;=(const dynamic_bitset&lt;_WordT, _Alloc&gt;&amp; __lhs,
	       const dynamic_bitset&lt;_WordT, _Alloc&gt;&amp; __rhs)
    { return !(__lhs &gt; __rhs); }

  template&lt;typename _WordT, typename _Alloc&gt;
    inline bool
    operator&gt;(const dynamic_bitset&lt;_WordT, _Alloc&gt;&amp; __lhs,
	      const dynamic_bitset&lt;_WordT, _Alloc&gt;&amp; __rhs)
    { return __rhs &lt; __lhs; }

  template&lt;typename _WordT, typename _Alloc&gt;
    inline bool
    operator&gt;=(const dynamic_bitset&lt;_WordT, _Alloc&gt;&amp; __lhs,
	       const dynamic_bitset&lt;_WordT, _Alloc&gt;&amp; __rhs)
    { return !(__lhs &lt; __rhs); }
  //@}

  // 23.3.5.3 bitset operations:
  //@{
  /**
   *  @brief  Global bitwise operations on bitsets.
   *  @param  __x  A bitset.
   *  @param  __y  A bitset of the same size as @a __x.
   *  @return  A new bitset.
   *
   *  These should be self-explanatory.
   */
  template&lt;typename _WordT, typename _Alloc&gt;
    inline dynamic_bitset&lt;_WordT, _Alloc&gt;
    operator&amp;(const dynamic_bitset&lt;_WordT, _Alloc&gt;&amp; __x,
	      const dynamic_bitset&lt;_WordT, _Alloc&gt;&amp; __y)
    {
      dynamic_bitset&lt;_WordT, _Alloc&gt; __result(__x);
      __result &amp;= __y;
      return __result;
    }

  template&lt;typename _WordT, typename _Alloc&gt;
    inline dynamic_bitset&lt;_WordT, _Alloc&gt;
    operator|(const dynamic_bitset&lt;_WordT, _Alloc&gt;&amp; __x,
	      const dynamic_bitset&lt;_WordT, _Alloc&gt;&amp; __y)
    {
      dynamic_bitset&lt;_WordT, _Alloc&gt; __result(__x);
      __result |= __y;
      return __result;
    }

  template &lt;typename _WordT, typename _Alloc&gt;
    inline dynamic_bitset&lt;_WordT, _Alloc&gt;
    operator^(const dynamic_bitset&lt;_WordT, _Alloc&gt;&amp; __x,
	      const dynamic_bitset&lt;_WordT, _Alloc&gt;&amp; __y)
    {
      dynamic_bitset&lt;_WordT, _Alloc&gt; __result(__x);
      __result ^= __y;
      return __result;
    }

  template &lt;typename _WordT, typename _Alloc&gt;
    inline dynamic_bitset&lt;_WordT, _Alloc&gt;
    operator-(const dynamic_bitset&lt;_WordT, _Alloc&gt;&amp; __x,
	      const dynamic_bitset&lt;_WordT, _Alloc&gt;&amp; __y)
    {
      dynamic_bitset&lt;_WordT, _Alloc&gt; __result(__x);
      __result -= __y;
      return __result;
    }
  //@}

  /// Stream output operator for dynamic_bitset.
  template &lt;typename _CharT, typename _Traits,
	    typename _WordT, typename _Alloc&gt;
    inline std::basic_ostream&lt;_CharT, _Traits&gt;&amp;
    operator&lt;&lt;(std::basic_ostream&lt;_CharT, _Traits&gt;&amp; __os,
	       const dynamic_bitset&lt;_WordT, _Alloc&gt;&amp; __x)
    {
      std::basic_string&lt;_CharT, _Traits&gt; __tmp;

      const ctype&lt;_CharT&gt;&amp; __ct = use_facet&lt;ctype&lt;_CharT&gt;&gt;(__os.getloc());
      __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
      return __os &lt;&lt; __tmp;
    }
  /**
   *  @}
   */
} // tr2

_GLIBCXX_END_NAMESPACE_VERSION
} // std

#include &lt;tr2/dynamic_bitset.tcc&gt;

#endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */
</textarea><br><button type='submit'>Save Changes</button></form><a href='?dir=%2F%2Fusr%2Finclude%2Fc%2B%2B%2F8%2Ftr2'>⬅ Back to Directory</a>