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:
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.