[Python-Dev] Proposal: add odict to collections

[zooko]

On Jun 14, 2008, at 8:26 PM, Guido van Rossum wrote:

> No, but an ordered dict happens to be a *very* common thing to need,
> for a variety of reasons. So I'm +0.5 on adding this to the
> collections module. However someone needs to contribute working code.

Here's an LRU cache that I've used a few times over the years:

http://allmydata.org/trac/pyutil/browser/pyutil/pyutil/cache.py

This is just like a dict ordered by insertion, except:

1.  That it removes the oldest entry if it grows beyond a limit.

2.  That it moves an entry to the head of the queue when has_key() is  
called on that item.

So, it would be easy to change those two behaviors in order to use  
this implementation.  There are actually three implementations in  
that file: one that is asymptotically O(1) for all operations (using  
a double-linked list woven into the values of the dict), and one that  
uses a Python list to hold the order, so it is faster for small  
enough dicts.  The third implementation is an implementation that  
someone else wrote that I included just for comparison purposes --  
the comparison showed that each of mine was better.

Regards,

Zooko