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.
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.
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk