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

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2002-06-11 08:21:14

On Tuesday, June 11, 2002, at 12:27  AM, Jeremy Siek wrote:

> On Mon, 10 Jun 2002, Howard Hinnant wrote:
>>>     // 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:
>
> Why, is there a simpler way in this case to ensure the exception safety?

I may have skimmed the constructors too fast.  I was thinking there was 
only one throw point in the body of the constructors.  If it throws 
there should be nothing for the base class to do.  If it doesn't, 
nothing else will.  But I could be mistaken, I probably should've 
crawled into the constructor code a little more thoroughly before making 
that comment.

>>> 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?
>
> My thinking was that as a boost library, it will be used on many 
> different
> platforms. For some it may be better to have 64 bit blocks, others 32 
> bit
> blocks. As a codewarrior library it would probably make more sense to 
> not
> have this parameter, since you know what platform it will be going on.

It sounds like the decision should be made by the boost::lib author 
instead of the boost::lib client.  And if the boost::lib author chose 
unsigned int, I'll bet that would go a long way towards meeting your 
optimization goals (64 bit / 32 bit).  dyn_bitset<long> just seems like 
a very easy mistake to make.  Of course you could compile-time assert on 
signed types if that is a problem...

>> 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.
>
> The problem with iterators over bits is that they are slow. It seems to 
> me
> like putting iterators in the bitset is just tempting users to actually
> use them, when in most situations they shouldn't. If the user wants to
> iterator over stuff, they probably should look to vector<char> or
> something similar instead.

I can't tell if you're describing iterators over bits or 
deque::iterator! ;-)  Ok, maybe two wrongs don't make a right. :-)

Fwiw, algorithms such as copy could be optimized for such an iterator.

On Tuesday, June 11, 2002, at 01:32  AM, Chuck Allison wrote:

> But isn't it still an issue that you can't fulfill all of the iterator 
> requirements because a bit is not addressable? In other words, 
> iterators must allow:
>  
> T* p = &*v.begin();

Actually I was hoping Jeremy would fix this in his iterator paper:

http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2001/n1297.html

Jeremy, where's the proxy iterator concept? :-)

My main concern with the iterator thing is that vector<bool> clients are 
(probably) using iterators.  It will be more difficult for them to 
migrate to dyn_bitset if the interface is radically different.

>> append:  Although should be replace by insert, should also be 
>> redesigned
>
> What's the rationale for replacing by insert? More flexibility?

vector<bool> compatibility / migration.  I can't support vector<bool> 
deprecation unless there is a fairly painless migration path to the 
replaced functionality.

>> Btw, I kind of like the name bitvector better than dyn_bitset (thinking
>> bitvector/bitset).
>
> With iterators I would agree that bitvector is better, but without
> iterators I still prefer bitset, since the primary focus is on
> representing a set.

Agreed.  If it doesn't have iterators (which I think it should) 
dyn_bitset is a better name.

-Howard