Python 等效于 std::set 和 std::multimap

Question

我正在将 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 类不符合我的需要，因为它按插入顺序返回项目，而我需要使用它们的 __cmp__ 方法对它们进行排序。

原文由 EMP 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

对于排序字典，您可以（ab）使用python timsort 的稳定特性：基本上，保持项目部分排序，在需要时在末尾附加项目，切换“脏”标志，并在迭代之前对剩余的项目进行排序。有关详细信息和实现，请参阅此条目（A Martelli 的回答）： Python 中的 Key-ordered dict

原文由 LeMiz 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

您应该使用 sort(key=...) 。

您使用的关键功能将与您已经使用的 cmp 相关。优点是 key 函数被调用 n 次，而 cmp 被调用 nlog n 次，并且通常 key 完成 cmp 所做工作的一半

如果您可以包含您的 __cmp__() 我们可能会向您展示如何将其转换为关键功能

如果您在修改之间进行大量迭代，则应缓存已排序项目的值。

原文由 John La Rooy 发布，翻译遵循 CC BY-SA 2.5 许可协议