[swift-dev] Dictionary Collision Resolution Guarantees

Dave Abrahams dabrahams at apple.com
Fri Oct 14 10:55:47 CDT 2016


on Fri Oct 14 2016, Ole Begemann <ole-AT-oleb.net> wrote:

> On 14/10/2016 02:46, Dave Abrahams wrote:
>
>>> OK cool, is there any reason it’s even written down? I don’t see any code
>>> that’s obviously relying on it. (seems fine to delete it?)
>>
>> It's written down because we've never formalized our index invalidation
>> rules.  I didn't realize that this comment was related to index
>> invalidation.  The guarantee mentioned is one we might want to give, at
>> least under some circumstances.  We'll have to think about that more
>> carefully.  In any case, it's not time to delete it yet.
>
> For what it's worth, this rule is also explicitly mentioned in
> docs/IndexInvalidation.rst
> (https://github.com/apple/swift/blob/master/docs/IndexInvalidation.rst):
>
> "Insertion into a Dictionary invalidates indexes only on a rehash. If
> a Dictionary has enough free buckets (guaranteed by calling an
> initializer or reserving space), then inserting elements does not
> invalidate indexes.
>
> Note: unlike C++'s std::unordered_map, removing elements from a
> Dictionary invalidates indexes."
>
> (I realize the stuff in /docs is not necessarily official
> documentation (right?), I just wanted to mention it.)

Thanks for pointing that out; that's important.

-- 
-Dave


More information about the swift-dev mailing list