Re: [boost] [optional] operator<(optional<T>, T) -- is it wrong?

Subject: Re: [boost] [optional] operator<(optional<T>, T) -- is it wrong?
From: Gottlob Frege (gottlobfrege_at_[hidden])
Date: 2014-12-01 13:56:22

On Mon, Dec 1, 2014 at 1:48 PM, Olaf van der Spek <ml_at_[hidden]> wrote:
> On Mon, Dec 1, 2014 at 7:45 PM, Gottlob Frege <gottlobfrege_at_[hidden]> wrote:
>> On Sun, Nov 30, 2014 at 6:20 PM, Gavin Lambert <gavinl_at_[hidden]> wrote:
>>> On 29/11/2014 08:01, Gottlob Frege wrote:
>>>>
>>>> There are still reasons to use std::map over unordered_map.  Lack of a
>>>> cryptographically safe hash is one of them.  There are others (that
>>>> I've forgotten, but I've asked the same question to committee members
>>>> before, and there were a few reasons that sounded valid to me.)
>>>
>>>
>>> Why should the lack of a cryptographically safe hash matter when you are not
>>> doing cryptography?
>>>
>>> It doesn't really matter what hash is used in internal data structures.
>>> (Although obviously there are desirable properties such as having uniform
>>> spread to minimise bucket collisions and improve lookup speed.)
>>>
>>
>> Denial of Service attack - I carefully force the input data such that
>> the hashes collide and you get worse-case hash-table performance.
>> This is a real attack.  Python and a few other languages have already
>> fixed their hashes, we have not.
>
> True, but maps suffer from the same problem don't they?
> Is a fix even available for maps?
>

I'm not an expert here; I thought map was "safe" due to its self-balancing.

from overflow:

map, set, multimap, and multiset

Insertion: O(log n)
Lookup: O(log n)
Deletion: O(log n)

hash_map, hash_set, hash_multimap, and hash_multiset

Insertion: O(1) expected, O(n) worst case
Lookup: O(1) expected, O(n) worst case
Deletion: O(1) expected, O(n) worst case

ie map is still logN even in worst case.

> --
> Olaf
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost