Ordered dicts

[Duncan Booth]

bearophileHUGS at lycos.com wrote:

> Deleted keys from a dict/set aren't removed, they are tagged as
> deleted.
> My experience of CPython sources is tiny, I have just read few parts,
> so a person much more expert than me can comment the following lines.
> 
> During the printing of the set/dict I think such flags are just read
> and skipped one after the other.
> 
> So I think to keep the insertion order of the keys a simple chained
> list is enough, each inserted key has a pointer to the successive one
> (even deleted keys).

Not quite. Dictionary slots containing deleted keys are available for re-
use. In an ordinary dictionary you just overwrite the deleted flag with the 
new value, but for your ordered dictionary if you did that you would have 
to fix up the linked list.

Probably the simplest solution for an odict would be to keep the key in the 
dictionary after deletion but mark it as deleted (by setting the value to 
null). Then if you reinsert the deleted value it goes back in at its 
original order.

The catch of course is that keys then never get released, but you can 
always compact an odict by copying it:

  d = odict(d)

which should preserve the order but release the deleted keys (assuming no 
other references to the original copy).

> The simple linked list has to be managed (tail insertions only), and
> scanned from the listHead inside iterating methods like iteritems,
> items, values, etc.

You would also need to make sure that internal iterations also go through 
the linked list order. e.g. resizing a dict currently just goes through 
each entry inserting it into the new dict.

> If such solution is possibile, then how much difficult is such
> implementation?

It sounds easy enough, just a copy of the existing dict code with a few 
minor tweaks.