bitset.hpp

C++的一个好库。。。现在很流行

        s.assign(size(), '0');
        
        for (size_type i = 0; i < size(); ++i)
          if (test(i))
            s[size() - 1 - i] = '1';
      }

      //-----------------------------------------------------------------------
      // Stuff not in std::bitset

      // difference:  this = this - x
      Derived& operator-=(const Derived& x) {
        for (size_type i = 0; i < num_words(); ++i)
          data()[i] &= ~x.data()[i];
        return static_cast<Derived&>(*this);
      }

      // this wasn't working, why?
      int compare_3way(const Derived& x) const {
        return std::lexicographical_compare_3way
          (data(), data() + num_words(), x.data(), x.data() + x.num_words());
      }

      // less-than compare
      bool operator<(const Derived& x) const {
        return std::lexicographical_compare
          (data(), data() + num_words(), x.data(), x.data() + x.num_words());
      }

      // find the index of the first "on" bit
      size_type find_first() const;

      // find the index of the next "on" bit after prev
      size_type find_next(size_type prev) const;

      
      size_type _Find_first() const { return find_first(); }

      // find the index of the next "on" bit after prev
      size_type _Find_next(size_type prev) const { return find_next(prev); }

      //    private:
      word_type* data()
        { return static_cast<Derived*>(this)->data(); }

      const word_type* data() const 
        { return static_cast<const Derived*>(this)->data(); }

      size_type num_words() const 
        { return static_cast<const Derived*>(this)->num_words(); }

      size_type size() const 
        { return static_cast<const Derived*>(this)->size(); }
    };

    // 23.3.5.3 bitset operations:
    template <class W, class S, class D>
    inline D operator&(const bitset_base<W,S,D>& x,
                       const bitset_base<W,S,D>& y) {
      D result(static_cast<const D&>(x));
      result &= static_cast<const D&>(y);
      return result;
    }

    template <class W, class S, class D>
    inline D operator|(const bitset_base<W,S,D>& x,
                       const bitset_base<W,S,D>& y) {
      D result(static_cast<const D&>(x));
      result |= static_cast<const D&>(y);
      return result;
    }

    template <class W, class S, class D>
    inline D operator^(const bitset_base<W,S,D>& x,
                       const bitset_base<W,S,D>& y) {
      D result(static_cast<const D&>(x));
      result ^= static_cast<const D&>(y);
      return result;
    }

    // this one is an extension
    template <class W, class S, class D>
    inline D operator-(const bitset_base<W,S,D>& x,
                       const bitset_base<W,S,D>& y) {
      D result(static_cast<const D&>(x));
      result -= static_cast<const D&>(y);
      return result;
    }

    template <class W, class S, class D>
    inline int compare_3way(const bitset_base<W,S,D>& x,
                            const bitset_base<W,S,D>& y) {
      return std::lexicographical_compare_3way
        (x.data(), x.data() + x.num_words(), 
         y.data(), y.data() + y.num_words());
    }


    template <class W, class S, class D>
    std::istream&
    operator>>(std::istream& is, bitset_base<W,S,D>& x) {
      std::string tmp;
      tmp.reserve(x.size());

      // In new templatized iostreams, use istream::sentry
      if (is.flags() & ios::skipws) {
        char c;
        do
          is.get(c);
        while (is && isspace(c));
        if (is)
          is.putback(c);
      }

      for (S i = 0; i < x.size(); ++i) {
        char c;
        is.get(c);

        if (!is)
          break;
        else if (c != '0' && c != '1') {
          is.putback(c);
          break;
        }
        else
          //      tmp.push_back(c);
          tmp += c;
      }

      if (tmp.empty())
        is.clear(is.rdstate() | ios::failbit);
      else
        x.m_copy_from_string(tmp, static_cast<S>(0), x.size());

      return is;
    }

    template <class W, class S, class D>
    std::ostream& operator<<(std::ostream& os, 
                             const bitset_base<W,S,D>& x) {
      std::string tmp;
      x.m_copy_to_string(tmp);
      return os << tmp;
    }

    //=========================================================================
    template <typename WordType = unsigned long,
              typename SizeType = std::size_t,
              typename Allocator = std::allocator<WordType>
             >
    class dyn_size_bitset
      : public bitset_base<word_traits<WordType>, SizeType,
          dyn_size_bitset<WordType,SizeType,Allocator> >
    {
      typedef dyn_size_bitset self;
    public:
      typedef SizeType size_type;
    private:
      typedef word_traits<WordType> WordTraits;
      static const size_type word_size = WordTraits::word_size;

    public:
      dyn_size_bitset(unsigned long val, 
                      size_type n,
                      const Allocator& alloc = Allocator()) 
        : m_data(alloc.allocate((n + word_size - 1) / word_size)),
          m_size(n),
          m_num_words((n + word_size - 1) / word_size),
          m_alloc(alloc)
      {
        init_from_ulong(val);
      }

      dyn_size_bitset(size_type n,  // size of the set's "universe"
                      const Allocator& alloc = Allocator())
        : m_data(alloc.allocate((n + word_size - 1) / word_size)), 
          m_size(n), m_num_words((n + word_size - 1) / word_size),
          m_alloc(alloc)
      { }

      template<class CharT, class Traits, class Alloc>
      explicit dyn_size_bitset
        (const basic_string<CharT,Traits,Alloc>& s,
         std::size_t pos = 0,
         std::size_t n = std::size_t(basic_string<CharT,Traits,Alloc>::npos),
         const Allocator& alloc = Allocator())
        : m_data(alloc.allocate((n + word_size - 1) / word_size)), 
          m_size(n), m_num_words((n + word_size - 1) / word_size),
          m_alloc(alloc)
      {
        BOOST_ASSERT_THROW(pos < s.size(), std::out_of_range("dyn_size_bitset::dyn_size_bitset(s,pos,n,alloc)"));
        m_copy_from_string(s, pos, n);
      }

      template <typename InputIterator>
      explicit dyn_size_bitset
        (InputIterator first, InputIterator last,
         size_type n,  // size of the set's "universe"
         const Allocator& alloc = Allocator())
        : m_data(alloc.allocate((n + word_size - 1) / word_size)), 
          m_size(N), m_num_words((n + word_size - 1) / word_size),
          m_alloc(alloc)
      {
        while (first != last)
          this->set(*first++);
      }

      ~dyn_size_bitset() { 
        m_alloc.deallocate(m_data, m_num_words); 
      }
      
      size_type size() const { return m_size; }

      // protected:
      size_type num_words() const { return m_num_words; }

      word_type* data() { return m_data; }
      const word_type* data() const { return m_data; }

    protected:
      word_type* m_data;
      SizeType m_size;
      SizeType m_num_words;
      Allocator m_alloc;
    };

    //=========================================================================
    template <std::size_t N, typename WordType = unsigned long,
      typename SizeType = std::size_t>
    class bitset
      : public bitset_base<word_traits<WordType>, SizeType,
          bitset<N, WordType, SizeType> >
    {
      typedef bitset self;
      static const std::size_t word_size = word_traits<WordType>::word_size;
    public:
        // 23.3.5.1 constructors:
      bitset() {
#if defined(__GNUC__)
        for (size_type i = 0; i < num_words(); ++i)
          m_data[i] = static_cast<WordType>(0);
#endif
      }

      bitset(unsigned long val) {
        init_from_ulong(val);
      }

      template<class CharT, class Traits, class Alloc>
      explicit bitset
        (const basic_string<CharT,Traits,Alloc>& s,
         std::size_t pos = 0,
         std::size_t n = std::size_t(basic_string<CharT,Traits,Alloc>::npos))
      {
        BOOST_ASSERT_THROW
          (pos < s.size(), std::out_of_range("bitset::bitset(s,pos,n)"));
        m_copy_from_string(s, pos, n);
      }

      size_type size() const { return N; }

      // protected:
      size_type num_words() const { return (N + word_size - 1) / word_size; }

      word_type* data() { return m_data; }
      const word_type* data() const { return m_data; }
    protected:
      word_type m_data[(N + word_size - 1) / word_size];
    };

    //=========================================================================
    struct select_static_bitset {
      template <std::size_t N, typename WordT, typename SizeT, typename Alloc>
      struct bind_ {
        typedef bitset<N, WordT, SizeT> type;
      };
    };
    struct select_dyn_size_bitset {
      template <std::size_t N, typename WordT, typename SizeT, typename Alloc>
      struct bind_ {
        typedef dyn_size_bitset<WordT, SizeT, Alloc> type;
      };
    };

    template <std::size_t N = 0, // 0 means use dynamic
      typename WordType = unsigned long,
      typename Size_type = std::size_t, 
      typename Allocator = std::allocator<WordType>
             >
    class bitset_generator {
      typedef typename ct_if<N, select_dyn_size_bitset,
        select_static_bitset>::type selector;
    public:
      typedef typename selector
        ::template bind_<N, WordType, SizeType, Allocator>::type type;
    };


    //=========================================================================
    // bitset_base non-inline member function implementations

    template <class WordTraits, class SizeType, class Derived>
    Derived&