[dynamic_bitset] Comparison operators without assertions

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
26 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
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.
>> b) If the bitset with the larger bit size has any 1 bit outside the
>> bits comprising the common length, the smaller bit size is always <
>> the larger bit size.
>> c) Else do a bit-by-bit comparison for the bits comprising the common
>> length going from the higher order bit to the lower order bit of just
>> those bits.
>
> Could also add
>
> 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.

Agreed.


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On 16 May 2017 at 20:01, Edward Diener via Boost <[hidden email]>
wrote:

There is no other way to do it. BTW uong is 64-bits on any 64-bit OS.
>

This remark by a seasoned expert shows how dangerous the use of the type
long realy is.

degski
--
"*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend,
Schmerzen aus Schwäche stillend.*" - Novalis 1798

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On 17 May 2017 at 07:01, Edward Diener via Boost <[hidden email]>
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.

degski
--
"*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend,
Schmerzen aus Schwäche stillend.*" - Novalis 1798

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list


> On 17 May 2017, at 07:54, degski via Boost <[hidden email]> wrote:
>
> On 17 May 2017 at 07:01, Edward Diener via Boost <[hidden email]>
> 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...

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
On 17 May 2017 at 10:07, Pete Bartlett via Boost <[hidden email]>
wrote:

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

Well... consider:

    std::cout << ( std::string ( "0001" ) > std::string ( "000" ) ) << '\n';
    std::cout << ( std::string ( "1110" ) > std::string ( "111" ) ) << '\n';

    std::cout << ( std::string ( "0101" ) > std::string ( "000" ) ) << '\n';
    std::cout << ( std::string ( "1010" ) < std::string ( "111" ) ) << '\n';

    std::cout << ( std::string ( "000111" ) < std::string ( "111" ) ) <<
'\n';
    std::cout << ( std::string ( "111000" ) > std::string ( "111" ) ) <<
'\n';

But I guess, problem solved:
http://en.cppreference.com/w/cpp/algorithm/lexicographical_compare and
comparison of boost::dynamic_bitsets<> should neither throw or assert.

degski
--
"*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend,
Schmerzen aus Schwäche stillend.*" - Novalis 1798

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On 5/17/2017 3:07 AM, Pete Bartlett via Boost wrote:

>
>
>> On 17 May 2017, at 07:54, degski via Boost <[hidden email]> wrote:
>>
>> On 17 May 2017 at 07:01, Edward Diener via Boost <[hidden email]>
>> 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...!

I implemented it with a lexicographic compare and pushed it to develop
after testing it. I also added a more tests.

I honestly still do not see the value of having ordering for bitsets,
and I do not know the initial reasoning why it was implemented. But
since it was there might as well be ordering for bitsets of different sizes.

>
> 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...

I did not take a look at any this.


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
12