Why are there no ordered dictionaries?

Magnus Lycka lycka at carmen.se
Wed Nov 23 13:57:01 CET 2005


Ganesan Rajagopal wrote:
>>>>>> bonono at gmail com <bonono at gmail.com> writes:  > what would be 
> 
> the definition of "sorted" and "ordered", before we can > go on ? Sorted 
> would be ordered by key comparison. Iterating over such a container will 
> give you the keys in sorted order. Java calls this a SortedMap. See 
> http://java.sun.com/j2se/1.4.2/docs/api/java/util/SortedMap.html C++ STL 
> map container is also a Sorted Associative container. See 
> http://www.sgi.com/tech/stl/Map.html  Ganesan

In Python it's simple to keep a list sorted using bisect.insort.

 >>> import bisect
 >>> l=[]
 >>> bisect.insort(l,4)
 >>> bisect.insort(l,3)
 >>> bisect.insort(l,5)
 >>> bisect.insort(l,1)
 >>> bisect.insort(l,6)
 >>> bisect.insort(l,2)
 >>> l
[1, 2, 3, 4, 5, 6]

Assuming a list with n tuples, where the first m elements in each
tuple is the key, we can also fetch elements through keys (interval
matches as well as exact matches) with O(log n) performance.

I guess those who thinks this isn't enough should push for placing
something like Zope's BTree classes in the standard library.

Fredrik already showed how simple and cheap it was to make a dict out
of a list. I think this is a superior solution to odicts as suggested,
but by all means, if people want odicts, make sure that there is a
good implementation available, use it, show that it's useful to
others, and maybe, some time in the future, it will be considered
for inclusion in the standard library.



More information about the Python-list mailing list