[boost] Re: Dynamic Bitset formal review

From: Ed Brey (brey_at_[hidden])
Date: 2002-06-16 23:23:27

This is my review of the dyn_bitset library.  It is based on the vault content on 6/15.  Following are items where I see potential for improvment.

Design:

- The premis of making the a dynamic version of std::bitset is too limiting.  Rather, this class should take opportunity to take the best from std::bitset and std::vector<bool> and then add any additional improvments possible based on what has been lerned since standardization.

- Iterators, as well as the parallels with the members from std::vector that use them, should be provided.  There is no need to have standard-conformant iterators; instead a restricted, but still useful, iterator concept should be used instead.

- Invalidation of references and iterators should be defined.  To allow resizing without always triggering an invalidation, it would be useful to have a capacity concept like that in std::vector.  Likewise, guaranteed capacity is useful for guaranteeing nothrow and for giving the use control over minimizing heap allocations when reusing the bitset.

- There should be a constant reference.  This is useful for reading a given bit multiple times in a type-safe (ie. const) manner.  For example:

void fn() {
  dyn_bitset<> bits;
  Init(bits);
  dyn_bitset<>::const_reference const r = bits[5];
  while (r)
    Do_something(bits); // Updates the bitset.
}

The current reference class doesn't cut it, since it requires that the reference and the bitset be non-constant.  Given a good optimizing compiler, this gives you everything that returning bool does, and doesn't leave a hole in the interface.  I realize that std::bitset chose to return bool, but I'm not sure that applies today.  Are their a signficant number of modern compilers remaining that won't optimize away the proxy object?  This may be a case where a compromise due to pre-standardization compiler technology can now be removed.

Interface:

- dyn_bitset: bit_vector would be a better name; "dyn" is too cryptic to be readily understood.

- to_string should be a member function. The rationale explains an advantage of passing the string by reference rather than returning it; however, there isn't any reason the reference can't be passed to a member function instead of a free function.

Documentation:

- The specified mail application of the library of representing a subset may instill a mindset that can limit the vision of the library.  It would be better to remove this limitation and let the class stand on its own as a resizeable array of bits.

- The truth tables are overkill. It would be better to keep the documentation lean and just cross-reference the semantics of the C++ operators (&, |, and ^).

- Example 1 refers to "The operator<< for dyn_bitset". This should be clarified as the standard I/O output operator, since there are more than one conceptual operator<< overloads.

- All exceptions should be documented. For example, functions like push_back and resize should indicate when they may throw and when they are guaranteed to succeed.

Implementation:

- The reference would be more efficient in most cases if it kept a reference to the word it was referencing and then a bit-offset into that word.  This way, indexing to the right word would only be done once at reference creation time, rather than each time a reference is accessed.

My review is based on a reading of the documentation and a cursorary inspection of the implementation.  My vote for inclusion is a conditional yes.  The condition is the defining and documenting of invalidation and exceptions.  Beyond that, I see the addition of iterators as very important, but not a requirement for my vote.  However, so long as the feature is not provided, I would classify the library as ripe for being improved, or if necessary superceded.

I'd like to state, too, that there is much that I like about the library, which is impractical to list specifically in this review, and I thank Chuck Allison and Jeremy Siek for all their effort.

Ed Brey