Hi Edward and Matt! Thank you for your replies. Let me comment them both in one (maybe, overly long) message. Edward Diener wrote:
Are you suggesting that the <,>,<=, and >= operators always return 'false' if the sizes do not match, rather than assert ?
Definitely, no. I'm suggesting to discuss the rules of meaningful and
useful comparison for dynamic bitsets of different lengths. Returning
'false' each time sizes are different would make 'operator <' not only
inappropriate for std::set or std::map, but will force many STL
algorithms to treat these objects as equivalent, since equivalence is
defined is the standard library as:
equiv(a, b) = !(a Shouldn't BOOST_ASSERT be used instead of the one from assert.h? Possibly. I think the intention was always to assert, whereas
BOOST_ASSERT lets the assertion be overridden. I do agree with you
that the current way dynamic_bitset works with the assertion should
have been documented. I think, these assertions should be eliminated, not documented. We can
get rid of them without breaking even a bit of backward-compatibility.
Would you feel happy if an innocent-looking code like
std::string("c++") < "boost"
call std::terminate just because the class authors don't want to
handle all possible inputs for some reason? Less-comparison must
either be completely and safely defined, or not defined at all. That's
how the math works.
If we cannot reliably define total ordering, we can, probably, return
std::optional<bool> or even boost::tribool from 'operator <', or, at
the very bad, put an exception to the throw()-list. Terminating the
whole application immediately is *the worst possible* option, since it
is not the expected behavior for the comparison operator.
Matt Calabrese wrote: I agree that such comparisons should be valid. We should represent a
total order, just like standard containers do (assuming their
elements do, of course). I'm actually rather surprised that this
isn't already supported. At the time, I can see two completely different, mutually exclusive
total-order generalizations:
1. Mimic lexicographic string comparison: compare a[0] with b[0], if
they're equal, compare a[1] with b[1], etc. This is also the
way how std::vector<T> works if T is less-comparable (including
the special case for std::vector<bool>).
2. Mimic little-endian (or big-endian) numeric comparison.
-bit-: (9) (0)
a: 0000001101
b: 0001101
c: 00010000
a I'm not sure, though I agree that it's definitely worth
investigating with further discussion on the list and some example
use-cases. I intuitively suspect it's a reasonable generalization to
act as though implicit 0s were present for the shorter operand,
based on an interpretation as a binary value. The side on which to
pad should be consistent with the lexicographical ordering. Even
this generalization is somewhat debatable though, since extraneous
0s contribute to value in a dynamic bitset. If we continue thinking about dynamic_bitset as a bitstring (or, more
generally, bitlist), it would be consistent to define bitwise
operators in terms of 'zip' function, commonly found in a number of
functional programming languages (some pseudo-Haskell code follows):
(&) :: [Bit] -> [Bit] -> [Bit]
a & b = zipWith (&) a b
Usually, 'zip' combines lists until one of them is over (see [1]
and [2], though). Hence, applying 'operator &' to bitsets of
different size should create a new bitset with the length of the
shorter. The great feature of this definition is that it naturally
obeys the De Morghan's laws:
(~a & ~b) == ~(a | b)
(~b | ~b) == ~(a & b)
I also tried different padding schemes and had no luck keeping them
consistent to De Morghan laws. It anyone interested, I can post my
generalization attempts on the list.
With best wishes and hope that my suboptimal language
skills won't totally ruin my arguments,
――― Pavel K.
[1]: https://softwareengineering.stackexchange.com/q/274983
(Why does 'zip' ignore the dangling tail of the collection?)
[2]: http://stackoverflow.com/a/8513803
(TLDR: Boost's zip_iterator doesn't behave like Haskell's zip).