Boost logo

Boost :

Subject: Re: [boost] [dynamic_bitset] Comparison operators without assertions
From: Pete Bartlett (pete_at_[hidden])
Date: 2017-05-17 07:07:12


> On 17 May 2017, at 07:54, degski via Boost <boost_at_[hidden]> wrote:
>
> On 17 May 2017 at 07:01, Edward Diener via Boost <boost_at_[hidden]>
> wrote:
>
>>> On 5/16/2017 8:46 PM, Peter Dimov via Boost wrote:
>>>
>>> Edward Diener wrote:
>>>
>>>> An alternative algorithm I have been considering is when the bit sizes
>>>> are unequal is:
>>>>
>>>> a) The bits comprising the common length are the low order bits.
>>>>
>>>
> The fact that bits are part of the common length does not mean that these
> bits have anything in common (semantically). It seems (what Edward D.
> seemed to think originally) non-sensical to me (not to say overly
> expensive).
>
> d) if still equal, the larger bit size > the smaller bit size.
>>>
>>> This makes 000111 > 111 instead of equal, so that equality (which I
>>> presume checks sizes) and equivalence match.
>>>
>>
> This means you can just as well start with the length comparison first.
> The Algorithm:
>
> 1. Compare length: shorter < longer.
> 2. If equal lengths, compare bitwise (in some way, f.e. memcmp()), but ALL
> the bits.
>
> Any use of ulong() as suggested, or f.e. hashing, will not result in a
> strict weak ordering, i.e. it's useless.
>
>

The documentation already states that the ordering is lexicographic - there's no fuss or choice to be had here. The ordering MUST be the same as for std::string except the alphabet is now two characters (0/1) instead of 256 chars.

I hope no one thinks it is hard to compare std::strings of non-equal lengths...!

Nb there are other member functions that might be affected by this issue (the is_subset_of group). Do they demand equal sizes too? The docs don't impose a pre-condition that they do...


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk