Python 3.0, rich comparisons and sorting order

[Phil Frost]

On Tue, Sep 21, 2004 at 05:42:35PM +0000, Steven Bethard wrote:
> Phil Frost <indigo <at> bitglue.com> writes:
> > On Tue, Sep 21, 2004 at 05:24:48PM +0000, I wrote:
> > > Could you give an example of a list that you'd like to do this to?  I'm 
> > > still having trouble imagining a list of disparate types that I call sort 
> > > on...
> > What about binary trees? Currently it's possible to implement a binary
> > tree that is as general as a dict, but restricting comparisons to like
> > types would make that impossible.
> 
> Is there a good use case for binary trees with incompatible types at the nodes?
> 
> I'm not sure I follow your comparison here anyway, since you can't sort a 
> dict...  Could you clarify?
> 
> Thanks,
> 
> STeve

That's the point. Dicts can't be sorted, but binary trees *must* be.
There are at least two good reasons to use a binary tree:

- you need a mapping that is sorted by key
- the worst case O(n) complexity of a hash table is not acceptable

The right question here is, "is there a reason for mappings with
heterogeneous key types?" It's not something that I do often, but it's
something that's important to have. Dynamic typing is a good thing.