On Sat, 10 Apr 2004 10:34:49 -0400, David Abrahams <dave@boost-consulting.com> wrote:
Gennaro Prota <gennaro_prota@yahoo.com> 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.