std_bitset.h

linux下编程用 编译软件

      // find the next "on" bit that follows "prev"
      size_t
      _M_do_find_next(size_t __prev, size_t __not_found) const
      {
	++__prev;
	if (__prev >= ((size_t) _GLIBCXX_BITSET_BITS_PER_WORD))
	  return __not_found;

	_WordT __x = _M_w >> __prev;
	if (__x != 0)
	  return __builtin_ctzl(__x) + __prev;
	else
	  return __not_found;
      }
    };

  /**
   *  @if maint
   *  Base class, specialization for no storage (zero-length %bitset).
   *
   *  See documentation for bitset.
   *  @endif
  */
  template<>
    struct _Base_bitset<0>
    {
      typedef unsigned long _WordT;

      _Base_bitset()
      { }

      _Base_bitset(unsigned long)
      { }

      static size_t
      _S_whichword(size_t __pos )
      { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; }

      static size_t
      _S_whichbyte(size_t __pos )
      { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; }

      static size_t
      _S_whichbit(size_t __pos )
      {  return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; }

      static _WordT
      _S_maskbit(size_t __pos )
      { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); }

      // This would normally give access to the data.  The bounds-checking
      // in the bitset class will prevent the user from getting this far,
      // but (1) it must still return an lvalue to compile, and (2) the
      // user might call _Unchecked_set directly, in which case this /needs/
      // to fail.  Let's not penalize zero-length users unless they actually
      // make an unchecked call; all the memory ugliness is therefore
      // localized to this single should-never-get-this-far function.
      _WordT&
      _M_getword(size_t) const
      { 
	__throw_out_of_range(__N("_Base_bitset::_M_getword")); 
	return *new _WordT; 
      }

      _WordT
      _M_hiword() const
      { return 0; }

      void
      _M_do_and(const _Base_bitset<0>&)
      { }

      void
      _M_do_or(const _Base_bitset<0>&)
      { }

      void
      _M_do_xor(const _Base_bitset<0>&)
      { }

      void
      _M_do_left_shift(size_t)
      { }

      void
      _M_do_right_shift(size_t)
      { }

      void
      _M_do_flip()
      { }

      void
      _M_do_set()
      { }

      void
      _M_do_reset()
      { }

      // Are all empty bitsets equal to each other?  Are they equal to
      // themselves?  How to compare a thing which has no state?  What is
      // the sound of one zero-length bitset clapping?
      bool
      _M_is_equal(const _Base_bitset<0>&) const
      { return true; }

      bool
      _M_is_any() const
      { return false; }

      size_t
      _M_do_count() const
      { return 0; }

      unsigned long
      _M_do_to_ulong() const
      { return 0; }

      // Normally "not found" is the size, but that could also be
      // misinterpreted as an index in this corner case.  Oh well.
      size_t
      _M_do_find_first(size_t) const
      { return 0; }

      size_t
      _M_do_find_next(size_t, size_t) const
      { return 0; }
    };


  // Helper class to zero out the unused high-order bits in the highest word.
  template<size_t _Extrabits>
    struct _Sanitize
    {
      static void _S_do_sanitize(unsigned long& __val)
      { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); }
    };

  template<>
    struct _Sanitize<0>
    { static void _S_do_sanitize(unsigned long) {} };

  /**
   *  @brief  The %bitset class represents a @e fixed-size sequence of bits.
   *
   *  @ingroup Containers
   *
   *  (Note that %bitset does @e not meet the formal requirements of a
   *  <a href="tables.html#65">container</a>.  Mainly, it lacks iterators.)
   *
   *  The template argument, @a Nb, may be any non-negative number,
   *  specifying the number of bits (e.g., "0", "12", "1024*1024").
   *
   *  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 %bitset as "a simple array of bits," be aware that
   *  your mental picture is reversed:  a %bitset behaves the same way as
   *  bits in integers do, with the bit at index 0 in the "least significant
   *  / right-hand" position, and the bit at index Nb-1 in the "most
   *  significant / left-hand" position.  Thus, unlike other containers, a
   *  %bitset's index "counts from right to left," 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
   *  "b('a') is 0001100001" on a modern ASCII system.
   *
   *  @code
   *     #include <bitset>
   *     #include <iostream>
   *     #include <sstream>
   *
   *     using namespace std;
   *
   *     int main()
   *     {
   *         long         a = 'a';
   *         bitset<10>   b(a);
   *
   *         cout << "b('a') is " << b << endl;
   *
   *         ostringstream s;
   *         s << b;
   *         string  str = s.str();
   *         cout << "index 3 in the string is " << str[3] << " but\n"
   *              << "index 3 in the bitset is " << b[3] << endl;
   *     }
   *  @endcode
   *
   *  Also see http://gcc.gnu.org/onlinedocs/libstdc++/ext/sgiexts.html#ch23
   *  for a description of extensions.
   *
   *  @if maint
   *  Most of the actual code isn't contained in %bitset<> itself, but in the
   *  base class _Base_bitset.  The base class works with whole words, not with
   *  individual bits.  This allows us to specialize _Base_bitset for the
   *  important special case where the %bitset is only a single word.
   *
   *  Extra confusion can result due to the fact that the storage for
   *  _Base_bitset @e is a regular array, and is indexed as such.  This is
   *  carefully encapsulated.
   *  @endif
  */
  template<size_t _Nb>
    class bitset
    : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)>
    {
    private:
      typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base;
      typedef unsigned long _WordT;

      void
	_M_do_sanitize()
	{
	  _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD>::
	    _S_do_sanitize(this->_M_hiword());
	}

    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 "bit %reference" is 64 times the size of
       *  an actual bit.  Ha.)
       */
      class reference
      {
	friend class bitset;

	_WordT *_M_wp;
	size_t _M_bpos;
	
	// left undefined
	reference();
	
      public:
	reference(bitset& __b, size_t __pos)
	{
	  _M_wp = &__b._M_getword(__pos);
	  _M_bpos = _Base::_S_whichbit(__pos);
	}

	~reference()
	{ }

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

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

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

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

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

      // 23.3.5.1 constructors:
      /// All bits set to zero.
      bitset()
      { }

      /// Initial bits bitwise-copied from a single word (others set to zero).
      bitset(unsigned long __val)
      : _Base(__val)
      { _M_do_sanitize(); }

      /**
       *  @brief  Use a subset of a string.
       *  @param  s  A string of '0' and '1' characters.
       *  @param  position  Index of the first character in @a s to use;
       *                    defaults to zero.
       *  @throw  std::out_of_range  If @a pos is bigger the size of @a s.
       *  @throw  std::invalid_argument  If a character appears in the string
       *                                 which is neither '0' nor '1'.
       */
      template<class _CharT, class _Traits, class _Alloc>
	explicit
	bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
	       size_t __position = 0)
	: _Base()
	{
	  if (__position > __s.size())
	    __throw_out_of_range(__N("bitset::bitset initial position "
				     "not valid"));
	  _M_copy_from_string(__s, __position,
			      std::basic_string<_CharT, _Traits, _Alloc>::npos);
	}

      /**
       *  @brief  Use a subset of a string.
       *  @param  s  A string of '0' and '1' characters.
       *  @param  position  Index of the first character in @a s to use.
       *  @param  n    The number of characters to copy.
       *  @throw  std::out_of_range  If @a pos is bigger the size of @a s.
       *  @throw  std::invalid_argument  If a character appears in the string
       *                                 which is neither '0' nor '1'.
       */
      template<class _CharT, class _Traits, class _Alloc>
	bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
	       size_t __position, size_t __n)
	: _Base()
	{
	  if (__position > __s.size())
	    __throw_out_of_range(__N("bitset::bitset initial position "
				     "not valid"));
	  _M_copy_from_string(__s, __position, __n);
	}
      
      // 23.3.5.2 bitset operations:
      //@{
      /**
       *  @brief  Operations on bitsets.
       *  @param  rhs  A same-sized bitset.
       *
       *  These should be self-explanatory.
       */
      bitset<_Nb>&
      operator&=(const bitset<_Nb>& __rhs)
      {
	this->_M_do_and(__rhs);
	return *this;
      }

      bitset<_Nb>&
      operator|=(const bitset<_Nb>& __rhs)
      {
	this->_M_do_or(__rhs);
	return *this;
      }

      bitset<_Nb>&
      operator^=(const bitset<_Nb>& __rhs)
      {
	this->_M_do_xor(__rhs);
	return *this;
      }
      //@}
      
      //@{
      /**
       *  @brief  Operations on bitsets.
       *  @param  position  The number of places to shift.
       *
       *  These should be self-explanatory.
       */
      bitset<_Nb>&
      operator<<=(size_t __position)
      {
	if (__builtin_expect(__position < _Nb, 1))
	  {
	    this->_M_do_left_shift(__position);
	    this->_M_do_sanitize();
	  }
	else
	  this->_M_do_reset();
	return *this;
      }

      bitset<_Nb>&
      operator>>=(size_t __position)
      {
	if (__builtin_expect(__position < _Nb, 1))
	  {
	    this->_M_do_right_shift(__position);
	    this->_M_do_sanitize();
	  }
	else
	  this->_M_do_reset();
	return *this;
      }
      //@}
      
      //@{
      /**
       *  These versions of single-bit set, reset, flip, and test are
       *  extensions from the SGI version.  They do no range checking.
       *  @ingroup SGIextensions
       */
      bitset<_Nb>&
      _Unchecked_set(size_t __pos)
      {
	this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
	return *this;
      }

      bitset<_Nb>&
      _Unchecked_set(size_t __pos, int __val)
      {
	if (__val)
	  this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
	else
	  this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
	return *this;
      }