Python equivalent of std::set and std::multimap
c++, data-structures, dictionary, performance, python
Solution
For the sorted dictionary, you can (ab)use the stable nature of python's timsort: basically, keep the items partially sorted, append items at the end when needed, switching a "dirty" flag, and sort the remaining before iterating. See this entry for details and implementation (A Martelli's answer): Key-ordered dict in Python
Problem
I'm porting a C++ program to Python. There are some places where it uses `std::set` to store objects that define their own comparison operators. Since the Python standard library has no equivalent of `std::set` (a sorted key-value mapping data structure) I tried using a normal dictionary and then sorting it when iterating, like this: ``` def __iter__(self): items = self._data.items() items.sort() return iter(items) ``` However, profiling has shown that all the calls from `.sort()` to `__cmp__` 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. Bonus points if it supports multiple values per key, like the C++ `std::multimap`. Note that the `OrderedDict` class doesn't fit my needs, because it returns items in the order of insertion, whereas I need them sorted using their `__cmp__` methods.