Re: [Boost-users] set() of dynamic_bitset is too slow.

From: Gennaro Prota (gennaro_prota_at_[hidden])
Date: 2006-06-04 13:42:27

On Sun, 4 Jun 2006 00:37:28 -0500, "Bo Peng" <ben.bob_at_[hidden]>
wrote:

>> succ.clear();
>> size_t numblock = m_N/BitSet::bits_per_block;
>> vector<BitSet::block_type> first_blocks(numblock);
>> for(size_t i=0; i<numblock; ++i)
>>         first_blocks[i] = rng().randInt(~BitSet::block_type(0));
>> succ.append(first_blocks.begin(), first_blocks.end());
>> // last block
>> BitSet::block_type last_block = rng().randInt(~BitSet::block_type(0));
>> for(size_t i=0; i < m_N - numblock*BitSet::bits_per_block; ++i)
>> {
>>         if((last_block >> i) & 0x1)
>>                 succ.set(numblock*BitSet::bits_per_block+i);
>> }
>
>When I think again about this, the special treatment of the last block
>is unnecessary, and because succ is already allocated, the following
>code is  clearer:
>
>vector<BitSet::block_type> blocks(succ.num_blocks());
>for(size_t i=0; i<blocks.size(); ++i)
>    blocks[i] = rng().randInt(~BitSet::block_type(0));
>from_block_range(blocks.begin(), blocks.end(), succ);
>
>I guess more efficiency can only be achieved through block_begin() and
>block_end() functions so that I can write to the blocks directly. Is
>this possible?

No, that is intentionally not possible. But you can construct the
dynamic_bitset object directly from a suitable iterator range (no need
to use an intermediate vector). Just to illustrate the point, this is
an example iterator based on boost::iterator_facade. Use it with
caution as I wrote it off the top of my head without verifying if it
really satisfies all iterator requirements:

 #include <cstddef>
 #include "boost/iterator/iterator_facade.hpp"
 #include "boost/dynamic_bitset.hpp"

 template<typename v>
 class rng_iterator_impl : public boost::iterator_facade<
         rng_iterator_impl<v>,
         v,
         boost::random_access_traversal_tag
        >
 {
             std::size_t count;
     mutable v           val;

 public:
     rng_iterator_impl(): count(0), val(0) {}
     explicit rng_iterator_impl(v c): count(c), val(0) { }

 private:

     friend class boost::iterator_core_access;

     value_type& dereference() const { return val=generate(); }

     bool equal(rng_iterator_impl const& rhs) const {
         return count == rhs.count;
     }

     void increment() { ++count; }

     void decrement() { --count; }

     void advance(difference_type n) { count+=n; }

     difference_type distance_to(rng_iterator_impl const & r) const {
         return r.count - count;
     }

     v generate() const { /* call you generating function here */ }
 };

 typedef boost::dynamic_bitset<> my_bitset_type;
 typedef rng_iterator_impl<my_bitset_type::block_type> rng_iterator;

Now, you should be able to do:

 int main()
 {
     const int how_many = 8;
     rng_iterator it;

     my_bitset_type b(it, it + how_many);
 }

If the last line in main() gives you problem please replace it with:

    my_bitset_type b;
    b.append(it, it + how_many);

Cheers.
--Gennaro.