[Python-ideas] What would you call such an object (was: ordered dict)

Josiah Carlson jcarlson at uci.edu
Thu Apr 26 18:22:27 CEST 2007


"LD 'Gus' Landis" <ldlandis at gmail.com> wrote:
> Hi,
> 
>   I am wondering if in y'alls opinion the following is "just a dictionary" or
>   is it a different kind of object that has some of the characteristics of a
>   dictionary, and has order.
> 
>   If y'all think that it is "just a dictionary", then how does one override the
>   notion of a "hash" for the key in a dictionary and make it some other
>   ordered structure (e.g. a B-Tree, AVL, etc).  (Please no flame toss to
>   some other list -- this is a "use" of an ordered "ordered dict")

This is easily implemented as a variant of a treap, in which rather than
choosing a new sub-node based on different characters in a string, you
choose a new sub-node based on different values in a tuple.  There is
one small problem with the structure as you have described it; in order
to be able to choose a (sorted) ordering on the portion of a key as you
show here...

>      key = object.order(key)       -> 3
>      key = object.order(key)       -> "abc"

...it won't make any sense in future Pythons.  3 < "abc" will return an
exception.


 - Josiah




More information about the Python-ideas mailing list