Ordered dicts

[bearophileHUGS at lycos.com]

Thank to Neil Cerutti and Duncan Booth for the answers. I have not
tried that C AVL implementation yet.

Duncan Booth:

> but for your ordered dictionary if you did that you would have
> to fix up the linked list.

To fix the list in constant time you probably need a doubly-linked
list, this requires more memory (or the bad xor trick) and more code
complexity.


> Then if you reinsert the deleted value it goes back in at its original order.

Uhm, this doesn't sound good. Thank you, I missed this detail :-)
Then the doubly-linked list, and the links fixing seem necessary...

Bear hugs,
bearophile