Ordered dicts

[bearophileHUGS at lycos.com]

I have found that in certain situations ordered dicts are useful. I use
an Odict class written in Python by ROwen that I have improved and
updated some for personal use.

So I'm thinking about a possible C version of Odict (maybe fit for the
collections module).

On a 32 bit Win Python 2.5 requires about:
28.2 bytes/element for set(int)
36.2 bytes/element for dict(int:None)

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). So theoretically an Odict of (int:None) can
require just 40.2 bytes/element :-)  (Python Odicts require much more
memory, because they ).
(I don't know if some extra memory for the garbage collector is
necessary, I don't think so.)

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

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

Bye,
bearophile