Suggestion: Operator `in` for slices

Ola Fosheim Grøstad ola.fosheim.grostad at
Wed Dec 22 04:46:27 UTC 2021

On Tuesday, 21 December 2021 at 17:02:22 UTC, Steven 
Schveighoffer wrote:
> On 12/19/21 2:34 PM, Ola Fosheim Grøstad wrote:
>> On Sunday, 19 December 2021 at 18:36:12 UTC, Steven 
>> Schveighoffer wrote:
>>> That is what we claim (and what hash algorithms in general 
>>> claim). amortized O(1) lookups and inserts.
>> Yes, if you don't shrink.
>> You need to prove that the claim holds for all possible 
>> orderings of inserts, deletions and lookups.
>> So you need to prove that you always do O(N) operations 
>> between rehashing, so you get O(N) operations of complexity 
>> O(1) + one rehash of complexity O(N) = O(N).
> Please see existing research, this is not a new concept.

What do you mean by research, this is a trivial topic. In order 
to get O(1) amortised you have to delay shrinkage, you must prove 
that any possible sequence does not reallocate more frequently 
than N operations.

More information about the Digitalmars-d mailing list