Python中是否有类似C++ STL map的结构？

Question

在 Python 里，有没有一种结构可以做和 C++ STL map 类似的操作，而且这些操作的复杂度也和 C++ STL map 一样呢？

Answer 1

我觉得标准的 Python 类型 dict() 在大多数情况下都能满足需求。它和 C++ 的 std::map 的不同之处在于，dict 是用哈希表实现的，而 C++ 的 map 是基于树的。

Answer 2

Python中的SortedDict类似于C++的STL map。你可以在这里或这里了解更多信息。

SortedDict是一个存储键值对的容器，它会根据键之间的顺序关系来排列这些键。就像Python自带的字典（dict）一样，SortedDict也支持快速的插入、删除和通过键查找数据。

Answer 3

dict（字典）通常已经足够用了，你想要它做什么而它做不到呢？

如果你的答案是“提供顺序”，那么其实用 for k in sorted(d.keys()) 也能解决这个问题啊。是不是觉得这样占用内存太多了？如果你需要频繁地遍历有序的内容，还要插入新的数据，那我明白了，你确实需要用树结构。

其实，dict 是一种哈希表，而不是 b-tree（平衡树）。不过，map 也并不是专门定义为 b-tree，所以它不能让你像分离子树那样创建新的 map，它的性能复杂度是一样的。我们真正需要担心的就是当哈希碰撞（多个数据被映射到同一个位置）很多时，dict 会发生什么，但在使用 Python 的时候，想要非常严格的最坏情况性能保证的情况应该是比较少见的。