以排序的顺序在字典中添加键

Question

假设我有一个字典

{1:5, 2:5, 4:5}

有没有一种数据结构，可以让我在添加键值对 3:5 时，自动把它放进字典里，并且保持键的顺序是排好序的？也就是说，

{1:5, 2:5, 3:5, 4:5}

我知道有 collections.OrderedDict()，但这个只会保持键按照添加的顺序排列（这对我来说不够用）。

我不想用普通字典 dic = {}，然后再用 sorted(dic)[0] 来获取最小的键。我更希望能有 sorted_dict[0] 这样的功能。
这样做的原因是，如果我用普通字典，我就得多次调用排序，因为我会不断地往字典里添加键值对。

补充说明：我应该提到，不仅仅是最小和最大键我关心，我还需要定期打印这个字典……

Answer 1

虽然我来得有点晚，但我想推荐一个叫做 sortedcontainers 的模块。这个模块和 blist 还有 bintrees 类似，它提供了一种叫 SortedDict 的数据类型，可以保持键的顺序是排好序的。跟那些模块不同的是，它是用纯 Python 写的，而且速度更快。SortedDict 还支持索引，查找最小值和最大值的速度是 O(1)，也就是非常快。

因为它是纯 Python 的，所以用 pip 安装起来非常简单：

pip install sortedcontainers

然后你可以直接导入 SortedDict。

In [1]: from sortedcontainers import SortedDict

In [2]: d = SortedDict({1:5, 2:5, 4:5})

In [3]: d
Out[3]: SortedDict({1: 5, 2: 5, 4: 5})

In [4]: d[3] = 5

In [5]: d
Out[5]: SortedDict({1: 5, 2: 5, 3: 5, 4: 5})

如果你在用 pip 安装时遇到困难，或者不能复制需要编译的文件，你也可以直接从仓库里拿 sortedlist.py 和 sorteddict.py 这两个文件。所有的代码都是 开源的，可以在 github 上找到。

sortedcontainers 模块还提供了一个 性能比较，可以看到它和其他流行的选择之间的对比。

Answer 2

试试这个方法 — http://code.activestate.com/recipes/576998-sorted-dictionary/

它使用标准库中的 bisect 模块来保持键的排序。

Answer 3

如果你打算不断地往字典里添加和删除键，那你真的需要一个合适的数据结构来解决这个问题。不是哈希表（或者像SortedOrderedDict那样的哈希表加列表），而是平衡树（或者类似的，比如跳表）。

如果你在PyPI上看看，会发现有很多选择。我推荐的是blist。虽然它的数据结构可能没有其他一些更优（因为B+树比二叉树宽得多），但对于你可能遇到的几乎所有使用场景来说，它应该足够好了。而且它有一个完整且经过良好测试的接口，包括经过测试的性能保证。其他一些严肃的项目也经常使用它。

如果你碰到的情况比较少见，树的性能真的很重要，那你可能需要看看各种红黑树、伸展树、跳表等实现。我之前用过bintrees，它的接口很好（比如，你可以通过索引访问键和值，甚至可以对树进行切片，还能像使用dict一样使用它，作者也考虑到了所有可能的歧义），但我没有认真测试过它的性能。

另外，如果你的键和值都是比较小的整数，你可以考虑用Cython把C++的map<int, int>封装成一个Python风格的接口。（虽然不可能提供一个完整的接口在C++的map之上，但通常你也不需要那样。）或者，修改像bintrees.FastRBTree这样的实现，来存储和比较long而不是PyObject*。

另一方面，如果你只是想一次性创建字典然后使用它，那就简单多了。把它排序，然后放进OrderedDict里。这样你就不需要任何标准库以外的东西了。

sorted_dict = collections.OrderedDict(sorted(d.iteritems()))

---

在另一个回答的评论中，你说“我没有权限安装新模块……”

首先，确保这是真的。你可能是有权限在用户的site-packages目录中安装模块。或者，如果安装了virtualenv，或者你在使用3.3版本的内置venv，那就更好了，你可能有权限创建一个虚拟环境并在里面安装模块。

但如果是这样，你需要做的是把blist/bintrees/等等的文件复制到你的项目中。

你可能会遇到的问题是，这些包大多数包含C扩展模块，这意味着你必须能够构建它们（也就是运行build_ext -i）。如果你的系统没有安装Python开发文件和编译工具链，你就无法做到这一点。在这种情况下，你需要寻找最好的纯Python解决方案。bintrees提供了一个纯Python的实现，和正常的C扩展实现是一样的，只是速度慢一些。当然，它的时间复杂度仍然是O(log N)，只是常数因子高得多。如果N足够大，这仍然是一个巨大的优势；如果不够大，可能就不一定了。

如果这些内容听起来合理，但你需要帮助来设置用户的site-packages或虚拟环境，或者把模块复制到你的项目中，或者在本地构建扩展等等，你可能应该搜索一下现有的问题，如果找不到，就问一个新问题（至少因为那些在安装问题上是专家的人不一定是数据结构方面的专家，甚至可能根本没有看到这个问题）。