[Python-ideas] ordered dict
jcarlson at uci.edu
Sat Apr 21 04:46:17 CEST 2007
Mathias Panzenböck <grosser.meister.morti at gmx.net> wrote:
> Ok, now. Forget all I said. Just a short question:
> When you have to store values accosiated with keys and the
> keys have to be accessible in a sorted manner. What container
> type would you use? What data structure would you implement?
> (I just thought a AVL tree would have been a good choice.)
If you want to use only things that are available in base Python, use a
list and the bisect module.
If you need O(logn) insertion and removal, then an AVL/Red-Black/2-3
tree with the semantics you described would also work. (I think there is
both an AVL and Red-Black tree implementation in the Python package
If you only need to concern yourself with ordering every once in a while,
then x = dct.items();x.sort() works reasonably well.
Sometimes a "pair heap" can get you what you are looking for .
Data structure choices are tricky. It is usually better to describe the
problem and one's approach (why you choose to use a particular algorithm
and structure), rather than strictly asking "where can I find data
More information about the Python-ideas