Proposed implementation for an Ordered Dictionary

[bearophileHUGS at lycos.com]

Raymond Hettinger:
>Paul Rubin:
>>another (messy) approach would be to write a C
>>extension that uses a doubly linked list some day.
>
> That seems like an ideal implementation to me.

This was my Python implementation, where the delete too is O(1), but
it's slow:
http://code.activestate.com/recipes/498195/

I think the C extension with the doubly linked list is the best
approach.
Note that in modern CPUs caches are able to change the performance a
lot. So reducing the memory used is very important. So using the XOR
(or subtraction) trick to use only 1 pointer for each key-value may be
useful to keep performance not too much far from the normal python
dicts:
http://en.wikipedia.org/wiki/XOR_linked_list

Bye,
bearophile