[Python-Dev] Proposal: add odict to collections

[Steven D'Aprano]

On Sun, 15 Jun 2008 02:59:51 pm David Wolever wrote:

> And, as far as questions about the definition of an ordered
> dictionary, is there any good reason not to simply treat the dict as
> a list?  Something like (with the obvious bits left out):

Yes. 

(1) If you implement the ordered dict as a list of key/value pairs, then 
you get order for free, but searching is slow, and so is deletion. If 
we wanted O(N) searches, we'd just use a list of tuples :)

(2) If you implement it as a hash table plus a list of keys in insertion 
order, then searching the dict is fast, but deletions are slow. Also 
you double (?) the amount of memory needed for the keys.


On the other hand... a tree-based implementation would require more 
work, and many more decisions (what kind of tree?), would lose the O(1) 
behaviour of the hash table, and may end up using just as much memory. 
So I wouldn't discount your suggestion.


-- 
Steven