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

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-06-12 11:18:57

Hello Dan'l Miller,

I would appreciate it if you refrained from using Stepanov's name to back
up your arguments, unless you have in fact talked with him about
boost::dyn_bitset and can quote him.

I'm glad that you are concerned about new libraries conforming to the "STL
vision". I agree that when considering new libraries we should take a
serious look at how well they interact with the STL, and whether they make
use of generic programming when appropriate. I feel that I have a fairly
good grasp of what is the "STL vision". I worked for Alex Stepanov at SGI,
in the C++ compiler and libraries group, and Alex was a big supporter of
my master's thesis work, the Matrix Template Library. Further, he recently
endorsed my book about the Boost Graph Library by writing the foreward.

But enough of that. In the following I'll try to address the technical
aspects of your concerns.

On Tue, 11 Jun 2002, Dan'l Miller wrote:
optiko>
optiko>   [ DEFECT #1: design which diverges against SGI STL's bit_vector ]
optiko>
optiko>   This boost::dyn_bitset class should not exist outside of a
optiko> private-implementation Boost detail directory because it reinvents
optiko> the wheel needlessly in compilers which do not support partial
optiko> explicit specialization.  Instead use Alexander Stepanov's SGI
optiko> STL's bit_vector if such a class template is desired.
optiko>
optiko>   from http://www.sgi.com/tech/stl/bit_vector.html
optiko>   "A bit_vector is essentially a vector<bool>: it is a Sequence
optiko> that has the same interface as vector. The main difference is that
optiko> bit_vector is optimized for space efficiency. A vector always
optiko> requires at least one byte per element, but a bit_vector only
optiko> requires one bit per element."
optiko> [...]
optiko>   from http://www.sgi.com/tech/stl/bitset.html "Bitset is very
optiko> similar to vector<bool> (also known as bit_vector): it contains a
optiko> collection of bits, and provides constant-time access to each bit.
optiko> There are two main differences between bitset and vector<bool>."
optiko>
optiko>   These quotations together form a clear statement from the
optiko> progenitors of STL that the intended run-time-sized
optiko> efficiently-packed alternative to STL's bitset is SGI STL's
optiko> explicit specialization of vector<bool>.

Sorry, but I don't draw the same conclusion. For example, the quote above
from bitset.html continues:

"Second, bitset is not a Sequence; in fact, it is not an STL Container at
all. It does not have iterators, for example, or begin() and end() member
functions. Instead, bitset's interface resembles that of unsigned
integers. It defines bitwise arithmetic operators such as &=, |=, and ^=."

So I'd draw rather the opposite conclusion from the SGI STL docs, bitset
and bit_vector are rather different creatures, so bit_vector is *not* the
run-time sized alternative to bitset.

optiko>   [ DEFECT #2: design which diverges against SGI STL's
optiko> vector<bool> explicit specialization ]

The boost::dyn_bitset is not meant to replace, or be at all similar to,
the std::vector<bool>. It is not a Container, it is an efficient
representation for finite sets.

optiko>   [ DEFECT #3: omission in design & vision ]
optiko>
optiko>   The implication of expecting an explicit specialization of
optiko> vector<bool> to satisfy the expectations of the concept of a
optiko> run-time-sized bitset is that vector<bool> omits the bitwise
optiko> arithmetic operators such as &=, |=, and ^=.  The divergent
optiko> boost::dyn_bitset does not correct this deficiency of
optiko> vector<bool>.  Instead of (re)inventing a whole new class named

It sounds like you would like to see a class that has both iterators and
arithmetic operators. I am open to adding iterators (Howard Hinnant also
made this suggestions), however I have reservations. As I posted
previously, I think iterators over bits are a bad idea because they are
inherently slow. If the user wants to iterate, then vector<char> is a
better choice.

optiko>   [ DEFECT #4: omission in documentation ]
optiko>
optiko>   The libs/dyn_bitset/dyn_bitset.html file does not contain any
optiko> explanation regarding why the SGI STL explicit specialization of
optiko> vector<bool> was rejected.  Furthermore, it does not even mention
optiko> anything whatsoever about vector<bool>, in either its
optiko> automatic/naive specialization or its explicit specialization.
optiko> There is a passing see-also reference to vector which does not
optiko> quench my thirst.

I will add a rationale/design section to the documentation.

optiko>   [ DEFECT #5: lack of vision ]

No technical aspects to this defect.

Regards,
Jeremy

----------------------------------------------------------------------
 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]
----------------------------------------------------------------------