> As many will attest, it’s easy to live life without an ordered map in Python, but the moment you need one Python starts to suck really fucking hard. This should be built into the language somehow.
OrderedDict [0] was added with Python 3.1, and there's an equivalent (pure Python) class provided in the docs for backwards compatibility. Just in case the author reads this, it would make the code nicer to implement the appropriate "magic" method names that make it act like built-in containers [1].
OrderedDict tracks insertion order, not key order. Additionally it is not possible to start iteration from an arbitrary key.
The method and variable names here mostly reuse the names from the original skip lists paper, although in a real generic implementation, reusing the mapping protocol would be a nice touch. I posted this more due to the ridiculous simplicity of implementation: skip lists themselves are far more worthy of note than my horrid example code.
OrderedDict [0] was added with Python 3.1, and there's an equivalent (pure Python) class provided in the docs for backwards compatibility. Just in case the author reads this, it would make the code nicer to implement the appropriate "magic" method names that make it act like built-in containers [1].
0: http://docs.python.org/3.3/library/collections.html?highligh...
1: http://docs.python.org/3.3/reference/datamodel.html#emulatin...