I submitted my container library to code.dlang.org

[w0rp via Digitalmars-d]

On Friday, 3 April 2015 at 16:12:00 UTC, w0rp wrote:
> On Wednesday, 1 April 2015 at 06:31:28 UTC, thedeemon wrote:
>> On Tuesday, 31 March 2015 at 21:17:04 UTC, Martin Nowak wrote:
>>
>>> Robin Hood sounds like a good idea, but it really isn't. Keep 
>>> your load factor reasonable and distribute values evenly, 
>>> then you don't need a LRU lookup.
>>
>> Is there a D version of a hash table with open addressing and 
>> quadratic probing? It would be interesting to compare speeds.
>> I like Robin Hood for cache-friendliness, and it works quite 
>> well for many combinations of key-value types.
>
> Now there is. I just changed the hashmap in my container 
> library to use open addressing and quadratic probing. There's a 
> benchmark program in the library for testing it in comparison 
> to the standard associative array. I tested using 2.066 with 
> optimisations on, and it seems to be about the same.
>
> https://github.com/w0rp/dstruct/blob/master/source/dstruct/map.d
>
> Now, I am not the most fantastic Computer Science guy in the 
> world, and I probably got a few things wrong. If anyone would 
> like to look at my code and point out mistakes, please do. I 
> will add any improvements suggested.

Also, I changed the API slightly.

1. I removed setDefault for the standard associative array type. 
Now it's only there for my type. The module now only deals with 
the added library type.
2. I changed my range functions to match the names for range 
functions in 2.067, so they are now named byKey, byValue, and 
byKeyValue. I left out 'keys' and 'values', which I think are 
mistakes, when you can do byKey.array yourself, etc.
3. I renamed ItemRange to KeyValueRange. (My ranges for the 
hashmaps are all named, which is supposed to make it easier to 
build higher order ranges from them.)
4. I added a constructor for the hashmaps which lets you maybe 
avoid some allocations by providing a minimum size, where the 
hashmap will probably use a size larger than the one you provide.
5. I started using prime sizes for the hashmaps, because 
quadratic probing doesn't seem to work without primes.

I think that's the bigger changes at least.