bitset

symbian上STL模板库的实现

            // 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 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,
                    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 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;