title: Key-ordered dict in Python
body: <p>I am looking for a solid implementation of an ordered associative array, that is, an ordered dictionary.  I want the ordering in terms of keys, not of insertion order.</p>
  
  <p>More precisely, I am looking for a space-efficent implementation of a int-to-float (or string-to-float for another use case) mapping structure for which:</p>
  
  <ul>
  <li>Ordered iteration is O(n)</li>
  <li>Random access is O(1)</li>
  </ul>
  
  <p>The best I came up with was gluing a dict and a list of keys, keeping the last one ordered with bisect and insert.</p>
  
  <p>Any better ideas?</p>