Ordered dicts

[Steve Holden]

bearophileHUGS at lycos.com wrote:
> 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?

FYI there was a *long* discussion around the need for Speed sprint about 
implementing ordered dicts. As the discussion started by your thread has 
started to reveal, everyone has just-ever-so-slightly-different 
requirements. IIRC the goal was dropped because it wasn't possible to 
agree on a specification.

regards
  Steve
-- 
Steve Holden       +44 150 684 7255  +1 800 494 3119
Holden Web LLC/Ltd          http://www.holdenweb.com
Skype: holdenweb       http://holdenweb.blogspot.com
Recent Ramblings     http://del.icio.us/steve.holden