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 -- http://mail.python.org/mailman/listinfo/python-list
