[Python-3000] ordered dict for p3k collections?

[Mark Summerfield]

On 2007-09-26, skip at pobox.com wrote:
>     Mark> I have put a new version (incorporating another implementation
>     Mark> idea from Paul Hankin) on PyPI:
>
>     Mark> http://pypi.python.org/pypi/sorteddict
>
> From that:
>
>     The main benefit of sorteddicts is that you never have to explicitly
>     sort.
>
> Surely there must be something more than that.  Wrapping sorted() around a
> keys() or values() call is a pretty trivial operation.  I didn't see that
> the implementation saved anything.

Assuming you have a good sorteddict implementation (i.e., based on a
balanced tree or a skiplist, not the one I've put up which is just
showing the API) you can gain significant performance benefits.

For example, if you have a large dataset that you need to traverse quite
frequently in sorted order, calling sorted() each time will be expensive
compared to simply traversing an intrinsically sorted data structure.

When I program in C++/Qt I use QMap (a sorteddict) very often; the STL
equivalent is called map. Both the Qt and STL libraries have dict
equivalents (QHash and unordered_map), but my impression is that the
sorted data structures are used far more frequently than the unsorted
versions.

If you primarily program in Python, using dict + sorted() is very
natural because they are built into the language. But using a sorted
data structure and never sorting is a very common practice in other
languages.

-- 
Mark Summerfield, Qtrac Ltd., www.qtrac.eu