[Python-ideas] ordered dict

[BJörn Lindqvist]

On 4/26/07, Josiah Carlson <jcarlson at uci.edu> wrote:
> > Similar fuck ups are possible when using dicts. In practice this is
> > not a problem. An ordered dict doesn't need any more safeguards than
> > Python's already existing data structures. Using the natural order of
> > its items are just fine and when you need something more fancy,
> > override the __eq__ method or give the collections sort method a
> > comparator function argument.
>
> Except this series of posts is about a "sorted dict", with a key,value
> mapping in which the equivalent .items() are sorted() as an ordering
> (rather than more or less dependant on hash value as in a standard
> dictionary).  But as I, and others have stated before, which you should
> read once again because you don't seem to get it:
> THE EXISTANCE OF A TOTAL ORDERING ON VALUES IN PYTHON TODAY IS A LIE.
> IN FUTURE PYTHONS WE ARE REMOVING THE LIE BECAUSE IT DOESN'T HELP ANYONE.
> IF YOU DON'T LIKE IT; TOUGH COOKIES.  STANDARD PYTHON DICTIONARIES
> WILL WORK THE WAY THEY ALWAYS HAVE.  ONLY PEOPLE WHO BELIEVE THAT
> INCOMPATIBLE TYPES SHOULD BE ORDERED IN A PARTICULAR WAY IN THINGS LIKE
> lst.sort() WILL BE AFFECTED.
>
> If you want an actual reference, please see PEP 3100 which says,
> "Comparisons other than == and != between disparate types will raise an
> exception unless explicitly supported by the type"
> ... and references:
>     http://mail.python.org/pipermail/python-dev/2004-June/045111.html
>
> If you don't understand this, please ask again without profanity or
> accusing the Python developers of removing the "consenting adults"
> requirement.  Python is getting smarter.  Maybe you just don't
> understand why this is the case.

I really do not understand what you are talking about. Maybe you have
misunderstood something?

Lets talk about Java for a moment. Java contains a class called
TreeMap which has all the features that the original poster asked
for. The Python equivalent to TreeMap would be a "sorted dictionary."

Java, just like Python 3k will, forbids comparisions between disparate
Comparable types. It follows that Java does not enforce any "total
ordering" on disparate types either. The absence of a total ordering
does not mean that Java's TreeMap class' constructor needs to be
supplied with a list of "allowed key types" as you and Terry Reedy
suggested that Python's hypothetical sorted dictionary would need.

Try the following Java code:

TreeMap tm = new TreeMap();
tm.put(new Integer(3), "moo");
tm.put(new Double(7), "moo");

Java is definitely not designed according to the "we are all
consenting adults" philosophy, but it has no problem whatsoever
accepting this code. Note that you did NOT have to specify the
"allowed key types" and that Integer and Double are incomparable. But
when you run it:

Exception in thread "main" java.lang.ClassCastException
        at java.lang.Double.compareTo(Double.java:642)
        at java.util.TreeMap.compare(TreeMap.java:1085)
        at java.util.TreeMap.put(TreeMap.java:463)
        at comp.main(comp.java:9)

Which is exactly how I am suggesting that the hypothetical sorted dict
class should work too (in py3k). You can read more about these Java
classes and interfaces here
http://java.sun.com/j2se/1.4.2/docs/api/java/util/TreeMap.html and
here http://java.sun.com/j2se/1.4.2/docs/api/java/util/SortedMap.html.

I hope you understand now why having to specify or restrict the
allowed "key types" is superfluous and why a sorted dict "doesn't need
any more safeguards than Python's already existing data structures."

-- 
mvh Björn