我正在将一个C ++程序移植到Python。它有一些使用的地方 std::set 存储定义自己的比较运算符的对象。由于Python标准库没有相应的 std::set （一个排序的键值映射数据结构）我尝试使用普通字典，然后在迭代时对其进行排序，如下所示：
def __iter__(self):
items = self._data.items()
items.sort()
return iter(items)
但是，分析显示所有来自的调用 .sort() 至 __cmp__ 是一个严重的瓶颈。我需要一个更好的数据结构 - 本质上是一个排序字典。有谁知道现有的实施？如果不这样做，关于我应该如何实现这一点的任何建议？读取性能比写入性能更重要，时间比内存更重要。
如果它支持每个键的多个值，例如C ++，则会获得奖励积分 std::multimap。
请注意 OrderedDict class不符合我的需要，因为它按插入顺序返回项目，而我需要使用它们对它们进行排序 __cmp__ 方法。
对于排序字典，您可以（ab）使用python的timsort的稳定特性：基本上，保持项目部分排序，在需要时在末尾附加项目，切换“脏”标志，并在迭代之前对剩余项进行排序。有关详细信息和实施，请参阅此条目（A Martelli的回答）： Python中按键排序的dict
你应该用 sort(key=...)。
您使用的关键功能将与您已使用的cmp相关。优点是关键函数被调用n次，而cmp被称为nlog n次，并且通常key是cmp执行的一半工作
如果你能包括你的 __cmp__() 我们可以向您展示如何将其转换为关键功能
如果在修改之间进行大量迭代，则应缓存已排序项的值。
对于排序字典，您可以（ab）使用python的timsort的稳定特性：基本上，保持项目部分排序，在需要时在末尾附加项目，切换“脏”标志，并在迭代之前对剩余项进行排序。有关详细信息和实施，请参阅此条目（A Martelli的回答）： Python中按键排序的dict
你应该用 sort(key=...)。
您使用的关键功能将与您已使用的cmp相关。优点是关键函数被调用n次，而cmp被称为nlog n次，并且通常key是cmp执行的一半工作
如果你能包括你的 __cmp__() 我们可以向您展示如何将其转换为关键功能
如果在修改之间进行大量迭代，则应缓存已排序项的值。
Python没有内置的数据结构，尽管如此 bisect 模块提供了使用适当有效的算法保持排序列表的功能。
如果你有一个排序键列表，你可以将它与一个 collections.defaultdict(list) 提供类似多图的功能。
在他的书中“用Python编程3“，Mark Summerfield介绍了一个排序的字典类。源代码可用于 这个zip档案 - 寻找SortedDict.py。在书中详细描述了SortedDict类（我非常推荐）。它支持用于比较的任意键和每个键的多个值（Python中的任何字典都可以，因此我认为这不是什么大问题）。