python - 将 std::map 映射到 Python

Question

有时有一个按键排序的字典是有意义的。在 C++ 中，这通常使用红黑树来实现。但是任何自平衡二叉搜索树都可以(顺便说一句，Knuth 在这个问题上特别清楚)。到目前为止，我能想到的最好的解决方案是采用 R. McGraw's AVL-tree type并创建一个基本上实现 STL 映射接口(interface)的包装类(还指望 Python 中方便的对(两个元素元组)排序)。这样的元组基本对应std::map::value_type。

是的，有 Python 的 bisect 模块，虽然它在插入时是对数的，就像自平衡二叉树在插入时是对数的一样(对吗？)，但坦率地说，我只想要一个对象。称为 OrderedDict 或其他名称(不，Python 3.1 OrderedDict 不符合条件——这是针对“插入时”排序的——坦率地说，插入时排序与排序的关系并不十分明显)。

请注意，按键排序的字典在许多行业中非常有用(例如，在金融领域，通常跟踪数据的价格手册，这些基本上是价格 -> 数量、聚合订单信息等的排序字典。 ).

如果有人有任何其他想法，那很好。我所知道的是，Alex Martelli 在这里的“答案”让我聪明了 500 万倍。所以我想我会问。

Answer 1

我得到了完全相同的需求，Alex Martelli 的回答完全说服了我:最好是保留字典和部分排序的键列表，然后在需要时排序。这是有效的，因为 python 的排序算法(又名 Timsort)的行为非常特殊。 Key-ordered dict in Python

我测试了他的实现和我的，他的是最好的(因为他没有插入到列表的中间)

(我强烈建议您阅读 AM 关于 timsort 的评论中链接的论文，这是一颗明珠)。