Re: [boost] Dynamic Bitset Formal Review June 8-17

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-06-12 20:21:42

On Wed, 12 Jun 2002, Chuck Allison wrote:
cda>
cda> > However if dyn_bitset is not meant to be a migration path from
cda> > vector<bool> I think the argument is moot.
cda> > I'm guessing that C++0X will entertain the idea of deprecating
cda> > vector<bool>.  I'm also guessing that said movement will be more likely
cda> > to be successful if there is also a proposed bitvector for vector<bool>
cda> > clients to migrate to.  dyn_bitset does not have to be that class though.
cda>
cda> I think this is a good argument in favor of dyn_bitset, and for providing
cda> iterators. I haven't looked at it closely, but can we provide an iterator
cda> for dyn_bitset that meets all the requirements for STL iterators?

That's the catch. Many people consider vector<bool> a failure, and it has
caused people headaches, because it pretends to be a real Container with
real iterators, but it is not. A dyn_bitset with iterators would be in a
similar boat. It's iterators could meet the requirements for input
iterator and output iterator, but not forward iterator, bidirectional, or
random access because the thing returned by operator* is a proxy, and
therefore not an lvalue (which is required by Table 74 of the C++
standard). Similarly, the requirements for containers say that the
reference type must be an lvalue of the value_type (Table 65 of the C++
standard), which can't be satisfied by a proxy. This issue bites people in
practice in several ways. One example is that people will pass the bit
iterator into a standard algorithm such as std::search, expecting it to
work.  However, depending on the STL implementation it may or may not work
because the iterator does not meet the requirements for the algorithm.

By not including iterators, I was trying to avoid having people think of
dyn_bitset as a Container.

Cheers,
Jeremy

P.S. With my new iterator categories many of the problems would go away.
So, if everyone agrees to give my new iterator categories lots and lots of
support :) then I'd be willing to put in the bitset iterators :)

----------------------------------------------------------------------
 Jeremy Siek                          http://php.indiana.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------