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

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2002-06-10 22:42:14

On Saturday, June 8, 2002, at 01:45  PM, Mat Marcus wrote:

> The formal review of Dynamic Bitset by Chuck Alison and Jeremy Siek
> will commence today Saturday June 8th and run through Monday, June 17th.

By coincidence I'm revamping the Metrowerks vector<bool> implementation 
and so have this type of class at the top of my brain at the moment.

>     // The following 2 classes make sure that the bitset
>     // gets allocated in an exception safe manner

While this is a very good design pattern, it is not clear to me how it 
is helping in this application.  But also it does no harm ... except:

> class dyn_bitset : public detail::dyn_bitset_base<Block, Allocator>

Why the public derivation?  This seems to unnecessarily expose 
dyn_bitset to casting to a private implementation base class.  In effect 
detail::dyn_bitset_base<Block, Allocator> has become part of the public 
interface.  Is that intended?

> template <typename Block, typename Allocator>

I'm not seeing the motivation for the Block template parameter.  Would 
not the implementation know the best type for Block?  Are there choices 
for Block the user might make which may not be appropriate?  Signed 
types come to mind pretty quickly.  Not sure if they would mess up the 
implementation, but I'm guessing they will.   Why not leave this 
decision to the implementor?

No iterators!

Part of the motivation for dyn_bitset (imho) is to give clients of 
vector<bool> a place to migrate to so that we can deprecate 
vector<bool>.  Therefore dyn_bitset must support the vector<bool> 
interface at least to a large extent, if not completely.  Having it also 
support the bitset interface is a good thing too.  I think both could 
use iterators, begin, end, rbegin, rend, etc.  dyn_bitset could also use 
the rest of the vector interface: insert, erase, front, back, etc.  I 
would drop append (neither bitset nor vector).  In short, I would start 
with the interface of std::vector<bool> and add to it as appropriate 
from std::bitset.

References should remain stable after swap (still valid, just points to 
the other container).  That means that dyn_bitset::reference can't hold 
a pointer to the dyn_bitset it is referencing.

Namespace scope swap seems to be missing.

> reference(); // intentionally not implemented

?  I don't understand.  reference already has a constructor.  If you 
want to disable default construction of references (I agree a good 
thing), just don't declare it.

Try out boost::compressed_pair to get rid of the storage for the 
allocator.  On those systems that implement empty base class 
optimization you reduce your overhead from 4 words to 3 (25%) for the 
common case of a stateless allocator.  This can be significant in 
vector<dyn_bitset<> >.

append:  Although should be replace by insert, should also be redesigned 
w.r.t. optimizing on iterator type.  Current design instantiates code 
for input iterators and forward iterators.  This decision can be made at 
compile time and instantiate one algorithm or the other instead of both.

Btw, I kind of like the name bitvector better than dyn_bitset (thinking 
bitvector/bitset).

Just my .02, hope it helps.

-Howard