D vs C++

[spir]

On Sat, 25 Dec 2010 11:46:43 -0600
Andrei Alexandrescu <SeeWebsiteForEmail at erdani.org> wrote:

> On 12/25/10 10:08 AM, bearophile wrote:
> > Andrei:
> >
> >> What is a pure hash map?
> >
> > I meant that to implement the dict protocol in Python you just need to implement an equality and an __hash__ methods, because the collisions are not managed with a tree as in D. With pure hash map I meant that it doesn't contain trees and it doesn't need less-than comparisons.
> 
> This behavior has been changed since a few releases ago to use 
> singly-linked lists for solving collisions.

Did not know that. This change certainly simplifies implementation.
Then, with a slight change, it would probably be possible to implement an ordered AA, like in Ruby: http://www.igvita.com/2009/02/04/ruby-19-internals-ordered-hash/. The change is to add a // series of 'next' pointers to keep inserton order (for iteration only). The cost in time is neglectable (and happens only at insertion time); the cost in space is one pointer per node.
(I guess it was not possible in Python because their dict 'buckets' are not linked lists).

denis
-- -- -- -- -- -- --
vit esse estrany ☣

spir.wikidot.com