[Python-ideas] ordered dict

[Josiah Carlson]

Mathias Panzenböck <grosser.meister.morti at gmx.net> wrote:
> 
> Josiah Carlson schrieb:
> > 
> > However, the problem with choosing to use an AVL (Red-Black, 2-3, etc.)
> > tree is deciding semantics.  Do you allow duplicate keys? 
> 
> Does dict? no. so no.
> 
> > Do you allow
> > insertion and removal by position?
> 
> Does dict? no. so no.
> 
> > Do you allow the fetching of the
> > key/value at position X?
> 
> Does dict? no. so no.
> 
> > Do you allow the fetching of the position for
> > key X?
> 
> Does dict? no. so no.
> 
> > Insertion before/after (bisect_left, bisect_right equivalents).
> > Etcetera.
> > 
> 
> Why should all this be relevant?

Very few use-cases of trees involve an ordered key/value dictionary. In
90% of the cases where I have needed (and implemented) trees involved
one of the following use-cases; sorted keys (but no values), no but fast
insertion of value based on position, sorted keys indexed by position or
key with (and without) values, etc.

Please also understand that the semantics of Python's dictionary is a
function of its implementation as an open-addressed hash table.  It's
useful for 95% of use-cases, but among the remaining 5% (which includes
the use-case you have in mind for the structure), there is a huge
variety of just as significant uses that shouldn't be discounted.


> > In many cases, using a sorted list gets you what you want, is almost as
> > fast, and has the benefit of using less memory.
> > 
> 
> AFAIK does a doubled link list use the same amount of memory as a
> (very) simple AVL tree:

Python lists aren't linked lists.  If you didn't know this, then you
don't know enough about the underlying implementation to make comments
about what should or should not be available in the base language.

 - Josiah