[Python-ideas] ordered dict

[Mathias Panzenböck]

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? It just has to be some kind of
relation between a key and a value, and the keys should be accessible
in a sorted way (and you should not to have to sort them every time).
So it would be possible to slice such a container.

> 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:

struct tree_node {
	struct tree_node left;
	struct tree_node right;
	void * data;
};

struct list_node {
	struct list_node prev;
	struct list_node next;
	void * data;
};

> 
>  - Josiah
>