[Python-ideas] ordered dict

[Josiah Carlson]

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
index [1])

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 [2].


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
structure X".


 - Josiah

[1] http://www.python.org/pypi/
[2] http://mail.python.org/pipermail/python-dev/2006-November/069845.html