Python-äquivalent zu std::set und std::multimap

Ich bin Portierung eines C++ - Programms zu Python. Es gibt einige Orte, wo es verwendet std::set um Objekte zu speichern, dass Sie Ihre eigenen Vergleichs-Operatoren. Da die Python-standard-Bibliothek hat keine Entsprechung der std::set (einer sortierten key-value-mapping-Daten-Struktur), und ich habe versucht, mit einem normalen Wörterbuch und Sortieren dann, wenn die Iteration, wie diese:

def __iter__(self):
    items = self._data.items()
    items.sort()
    return iter(items)

Jedoch profiling gezeigt hat, dass alle Anrufe von .sort() zu __cmp__ sind ein Engpass. Ich brauche eine bessere Daten-Struktur - im wesentlichen ein sortiertes Wörterbuch. Kennt jemand eine bestehende Anwendung? Gelingt das nicht, irgendwelche Empfehlungen, wie ich diese umsetzen? Lese-performance ist wichtiger als schreiben, Leistung und Zeit ist wichtiger als Speicher.

Bonus-Punkte, wenn es unterstützt mehrere Werte pro Schlüssel, wie die C++ std::multimap.

Beachten Sie, dass die OrderedDict - Klasse passt nicht zu meinen Bedürfnissen, denn es gibt Elemente in der Reihenfolge einfügen, in der Erwägung, dass ich Sie brauche sortiert mit Ihren __cmp__ Methoden.