title: Python equivalent of std::set and std::multimap
body: <p>I'm porting a C++ program to Python. There are some places where it uses <code>std::set</code> to store objects that define their own comparison operators. Since the Python standard library has no equivalent of <code>std::set</code> (a sorted key-value mapping data structure) I tried using a normal dictionary and then sorting it when iterating, like this:</p>
  
  <pre><code>def __iter__(self):
      items = self._data.items()
      items.sort()
      return iter(items)
  </code></pre>
  
  <p>However, profiling has shown that all the calls from <code>.sort()</code> to <code>__cmp__</code> are a serious bottleneck. I need a better data structure - essentially a sorted dictionary. Does anyone know of an existing implementation? Failing that, any recommendations on how I should implement this? Read performance is more important than write performance and time is more important than memory.</p>
  
  <p>Bonus points if it supports multiple values per key, like the C++ <code>std::multimap</code>.</p>
  
  <p>Note that the <code>OrderedDict</code> class doesn't fit my needs, because it returns items in the order of insertion, whereas I need them sorted using their <code>__cmp__</code> methods.</p>