[Python-Dev] Proposal: add odict to collections

[Armin Ronacher]

Hi,

I noticed lately that quite a few projects are implementing their own
subclasses of `dict` that retain the order of the key/value pairs.
However half of the implementations I came across are not implementing
the whole dict interface which leads to weird bugs, also the performance
of a Python implementation is not that great.

To fight that problem I want to proposed a new class in "collections"
called odict which is a dict that keeps the items sorted, similar to
a PHP array.

The interface would be fully compatible with dict and implemented as
dict subclass.  Updates to existing keys does not change the order of
a key but new keys are inserted at the end.

Additionally it would support slicing where a list of key, value tuples
is returned and sort/reverse/index methods that work like their list
equivalents.  Index based lookup could work via odict.byindex().

An implementation of that exists as part of the ordereddict implementation
which however goes beyond that and is pretty much a fork of the python
dict[1].

Some reasons why ordered dicts are a useful feature:

  - in XML/HTML processing it's often desired to keep the attributes of
    an tag ordered during processing.  So that input ordering is the
    same as the output ordering.

  - Form data transmitted via HTTP is usually ordered by the position
    of the input/textarea/select field in the HTML document.  That
    information is currently lost in most Python web applications /
    frameworks.

  - Eaiser transition of code from Ruby/PHP which have sorted
    associative arrays / hashmaps.

  - Having an ordered dict in the standard library would allow other
    libraries support them.  For example a PHP serializer could return
    odicts rather then dicts which drops the ordering information.
    XML libraries such as etree could add support for it when creating
    elements or return attribute dicts.

Regards,
Armin


[1]: http://www.xs4all.nl/~anthon/Python/ordereddict/