title: Mapping std::map to Python
body: <p>Sometimes it makes sense to have a key-ordered dictionary. In C++, this is often implemented with a Red-black tree. But any self-balancing binary search tree will do (fwiw, Knuth is particularly clear on this subject). The best solution I've been able to come up with so far is to take <a href="http://sourceforge.net/projects/pyavl/" rel="noreferrer">R. McGraw's AVL-tree type</a> and create a wrapper class that basically implements the STL map interface (also counting on the handy ordering of pairs (two element tuples) in Python). Such a tuple basically corresponds to std::map::value_type.</p>
  
  <p>Yes, there's Python's bisect module, and while that is logarithmic at insertion time in the same way that self-balancing binary trees are logarithmic at insertion time (right?), frankly I just want an object. Called OrderedDict or something (and no, the Python 3.1 OrderedDict doesn't qualify -- that's for 'insertion-time' ordering -- and frankly what insertion-time ordering has to do with ordering is not quite obvious).</p>
  
  <p>Note, a key-ordered dictionary is highly useful in many industries (in finance for instance, it's ordinary to keep track of price books of data, which are basically ordered dictionaries of price -> quantity, aggregated order information, etc.). </p>
  
  <p>If anyone has any other ideas, that's great. All I know is I just got five million times smarter by Alex Martelli's 'answers' here. So I thought I'd ask.</p>