[boost] Re: New dynamic_bitset

From: Gennaro Prota (gennaro_prota_at_[hidden])
Date: 2004-04-13 04:17:41

On Sat, 10 Apr 2004 10:34:49 -0400, David Abrahams
<dave_at_[hidden]> wrote:

>Gennaro Prota <gennaro_prota_at_[hidden]> writes:
>
>> Hi everybody,
>>
>> as I have mentioned in some post here, a new version of
>> dynamic_bitset is in the sandbox.
>
>Neat!  I just noticed that the old one is missing an empty() member
>function.

Yes. I noticed that but was not sure whether adding it or not (just to
avoid cluttering the interface with too many "utility" functions).
I've added it now, with tests (wow :)).

>> I've finished everything 4/5 days ago (including new and more tests)
>> and thought to move it to the main repository, as Jeremy asked too.
>
>What does your change do?

Hmm. Here's an extremely condensed (not exhaustive) summary of
changes, future directions and open issues. Sorry if it's terse and
incomplete, but I don't have time right now. Don't be afraid for the
number of changes though; the tests pass with at least 7 compilers,
and there are more tests than before, so we shouldn't have big
problems/regressions.

 Exception Safety
 
 All exception safety guarantees are now documented (I haven't
 committed the docs yet, but the important functions have a
 comment that says what guarantee they offer - the html file is
 almost done). Where possible, such as for append(begin, end),
 the strong guarantee is provided.
 
 Implementation
 
 Everything is now implemented in terms of std::vector<>.
 This has quite simplified the code, and made more
 evident, from reading, the exception guarantees of each
 member function, as they immediately follow from the
 corresponding std::vector<>'s ones.

 Most functions have been rewritten, either to fix
 errors or to improve efficiency; or to satisfy
 exception guarantees.
 
 The nested class reference has been reimplemented.
 Formerly it stored an index and a pointer to the bitset:
 besides being inefficient, that meant that swapping
 bitsets either made references invalid or changed the
 element they were referring to. Both problems are now
 solved by storing a reference into a block and a
 pre-computed mask. I've also added a namespace scope
 swap (It's in namespace boost. Ok?)
 
 NOTE: for now a reference to a bit remains valid if an
 exception is thrown by a strong-guarantee operation and,
 as said, it is stable after a swap(). However rules
 for invalidation are not documented. If I document them
 I would go for rules modeled after std::deque, rather
 than std::vector, so that we leave open the door to
 implement everything in terms of std::deque. Anyway, I
 see this more as a future issue: if Jeremy's new iterator
 categories will get into the standard dynamic_bitset could
 have iterators; for now, instead, I don't feel the need
 to have precise invalidation rules for references to bits.
  
 The function count() is completely portable, including
 to platforms that have padding bits in built-in integer types.
  
 Conversions from and to string (i.e.: from_string, to_string
 a constructor, and the undocumented dump_to_string) are
 internationalized (but see below).
 
 A missing parameter in the constructor from basic_string has
 been added (however see below)
 
 Stream operators are internationalized and take into account
 exception masks on the stream. That's exercised by the tests,
 in dyn_bitset_unit_tests4. They don't use std::basic_string
 as an intermediary. (The special versions for old libstdc++
 also don't use string as intermediary, but of course they
 don't know about exception masks etc.)
 
  
 The functions to_block_range and from_block_range have been
 fixed (but see below)
 
 
 Tests

 There are much more tests. I can't post a detailed list
 now. Will do as soon as possible.
 
  
 (Some) Future directions
 
 - deprecating conversions from and to string

 Conversions to and from string are a design error of std::bitset
 that we have transposed into boost. dynamic_bitset has nothing
 to do with strings. If one needs a "textual" representation of
 the data stored in a bitset object there are the stream operators,
 which are the standard C++ convention for formatting data. By
 using << and >> you have a neat separation of concerns between the
 class that stores the data (dynamic_bitset in this case) and the one
 that stores their textual representation (basic_string), a generic
 name, operator>> or operator <<, for the free function that connects
 them (which is important for template programming) and none of the
 two classes encumbered with knowledge of the other. Also, you can
 easily deal with locale-related issues.
 
 
 - making reference private (and inhibit copying?)

 
 (Some) Open Issues:
 
 - Semantics of from_block_range should be clarified for the
   case where distance(first, last) == b.numblocks() *but*
    b.size() < (bits_per_block * b.num_blocks()). Example:
    say bits_per_block = 8, b.size() = 9 and you copy two
    blocks into b; should the bitset size become 16 or not?
    
    I think there are three possibilities:
     - make this case undefined behavior
     - enlarging the bitset as needed:
        
     // UNTESTED!
    from_block_range(BlockIterator first, BlockIterator last,
                     dynamic_bitset<B, A>& result)
    {
      // PRE: distance(first, last) <= numblocks()
      //
      if ( m_bits.end() ==
           std::copy (first, last, result.m_bits.begin())
         )
         m_num_bits = bits_per_block * b.num_blocks();
    }

    - ignoring additional bits
    
      ...
       std::copy (first, last, result.m_bits.begin());
       result.m_zero_unused_bits();
       
    My doubt with this last case concerns input iterators,
    because once you have consumed the last element it could be
    lost for ever (not sure if this is a problem or not)
    
 - the copy assignment operator currently provides the strong
guarantee:
 
    operator=(const dynamic_bitset<Block, Allocator>& b)
    {
        dynamic_bitset<Block, Allocator> tmp(b);
        this->swap(tmp);
        return *this;
    }
    
    Should it? I lean towards 'no'.

 - Should reserve() and capacity() be added? I think not,
   because std::deque doesn't have them. So if you add them
   to the dynamic_bitset interface then you can't implement
   it in terms of deque (that's why I have removed the two
   functions, after having initially implemented them)

- should std::swap be specialized/overloaded for dynamic_bitsets?
    
- The implementation of operator <, > and all comparison operators
  require the compared bitsets to have the same size, but that's
  not documented. The docs simply say that the lexicographical order
  is considered, and that suggests, for instance, that 10 is < 101.
  
- The docs for to_block_range say:

   "The type BlockOutputIterator must be a model of Output Iterator
   and its value_type must be the same type as Block."
   But output iterators have no notion of "value type".
   
   iterator_traits<OutputIterator>::value_type is defined as void.

- Imitating std::bitset, the function to_ulong checks whether
  there's any 1 bit beyond the positions representable in an
  unsigned long, eventually throwing an overflow_error. That
  goes against the "don't pay for what you don't use" principle
  (think for instance if your bitset has 20 000 elements and you
  are sure that only the first 8 can be set). It's also the only
  place where we still check "preconditions" with exceptions and
  the only reason why dynamic_bitset.hpp still needs to include
  <stdexcept>.

Genny.