Re: [swift-dev] Dictionary Collision Resolution Guarantees

2016-10-14 Thread Dave Abrahams via swift-dev
on Fri Oct 14 2016, Ole Begemann 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

Re: [swift-dev] Dictionary Collision Resolution Guarantees

2016-10-13 Thread Dave Abrahams via swift-dev
on Thu Oct 13 2016, Alexis wrote: >>> This is effectively assuming that the open-addressing scheme being >>> used is first-come-first-serve (FCFS). That is, any element being >>> inserted can *only* be inserted into vacant buckets, rather than >>> displacing existing elements. This is currently

Re: [swift-dev] Dictionary Collision Resolution Guarantees

2016-10-13 Thread Alexis via swift-dev
> On Oct 13, 2016, at 6:09 PM, Dave Abrahams via swift-dev > wrote: > > > on Thu Oct 13 2016, Alexis > wrote: > >> I’m currently cleaning up the docs on Dictionary to reflect the new indexing >> model, and I stumbled >> across the note

Re: [swift-dev] Dictionary Collision Resolution Guarantees

2016-10-13 Thread Dave Abrahams via swift-dev
on Thu Oct 13 2016, Alexis wrote: > I’m currently cleaning up the docs on Dictionary to reflect the new indexing > model, and I stumbled > across the note that the following code should work assuming no reallocations > occur: > > // > // var (i, found) = d.find(k) // i is associated with