An ordered dictionary for the Python library?

Carl Banks pavlovevidence at gmail.com
Wed Sep 12 18:06:27 CEST 2007


On Sep 12, 10:04 am, Michele Simionato <michele.simion... at gmail.com>
wrote:
> On Sep 12, 3:54 pm, Mark Summerfield <m.n.summerfi... at googlemail.com>
> wrote:
>
>
>
> > On 12 Sep, 13:46, Michele Simionato <michele.simion... at gmail.com>
>
> > Actually I meant by key order, so insertion order doesn't matter at
> > all. If you need a dictionary-like data structure that respects
> > insertion order you could use a list of (key, value) tuples.
>
> > Another respondent asked about use cases.
>
> > I have found time and again that I needed (key, value) pairs where the
> > key is some string that provides a representation for human readers
> > and the value is some internal key (e.g., database ID) that the system
> > uses internally. In these cases I often need to present the user with
> > a list of items from which to choose and want to present them in
> > sorted order. Naturally, I could use an ordinary dict and then do
> > this:
>
> > for string in sorted(d.keys()):
> >     process(string)
>
> > But what happens when I need to do this a *lot* and when the number of
> > items is hundreds or a few thousands? I'm having to sort again and
> > again, since it is often the case that the items in the list changes
> > during the runtime of the application. So my solution in C++ is to use
> > an ordered dictionary (a map in C++ jargon), which in Python means I
> > can simply write:
>
> > for string in od.keys():
> >     process(string)
>
> For your use case I would wrap a list [(key, value)] with a dict-like
> object and I would use the bisect module in the standard library to
> keep
> the inner list ordered.

That would make insertion and deletion would be quite expensive.
Which might be ok for the OP, but it's often better to go with a
btree.

Which, you know, would be a reasonable candidate for collections
module.


Carl Banks




More information about the Python-list mailing list