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
>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
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
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.
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
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)
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:
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());
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
operator=(const dynamic_bitset<Block, Allocator>& b)
dynamic_bitset<Block, Allocator> tmp(b);
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk