dbpokorny <at> gmail.com <dbpokorny <at> gmail.com> writes:
If you don't like the fact that your web application framework loses the order of its key:value pairs relative to the page, then you should bring it up with the developers.
Who will then point up that to retain that order while providing you with a dict-like API, they need to write some kind of ordered dict implementation. Then you'll complain that their implementation is sub-optimal and isn't 100% compatible with the original dict API, and post on python-dev to ask that a standard odict implementation is considered for the stdlib.
Ordered dicts, dicts that remember the chronological order of their insertion, don't sound generally useful.
They are generally useful in any case where you want to handle key-value pairs while not confusing a human operator by messing up the original order. Think e.g. configuration files. A common complaint against ConfigParser is that writing a configuration file does not preserve the order of the original file, which is harmless for the computer but very annoying for the human being who maintains that file.
As for sorted dicts with general O(log(n)) behaviour, you could try to combine the blist type (http://pypi.python.org/pypi/blist/) with the standard bisect module and see what that gives.