为什么Python的标准库中没有排序容器？

Question

是否存在阻止将排序容器添加到 Python 的 Python 设计决策 (PEP)？

（

OrderedDict

不是排序容器，因为它是按插入顺序排序的。）

Answer 1

还有一个 python sortedcontainers 模块，可以实现排序列表、字典和集合类型。它与 blist 非常相似，但在pure-Python中实现，并且在大多数情况下更快。

>>> from sortedcontainers import SortedSet
>>> ss = SortedSet([3, 7, 2, 2])
>>> ss
SortedSet([2, 3, 7])

它还具有其他软件包不常见的功能：

>>> from sortedcontainers import SortedDict
>>> sd = SortedDict((num, num) for num in range(100000))
>>> sd.iloc[-5] # Lookup the fifth-to-last key.
99995

披露：我是sortedcontainers模块的作者。

Answer 2

这是 Guido 有意识的设计决定（他甚至对添加

collections

模块有些犹豫）。他的目标是在为应用程序选择数据类型时保留“一种明显的方法”。

基本概念是，如果用户足够成熟，认识到内置类型并不是解决他们问题的正确解决方案，那么他们也可以找到合适的第三方库。

考虑到 list+sorting、list+heapq 和 list+bisect 涵盖了许多原本依赖于固有排序数据结构的用例，并且存在像 blist 这样的包，因此没有巨大的动力来增加这个空间的复杂性到标准库。

在某些方面，这类似于标准库中没有多维数组，而是将这项任务交给了 NumPy 人员。

Answer 3

还有包含 sortedset 数据类型的 blist 模块：

sortedset(iterable=(), key=None)

>>> from blist import sortedset
>>> my_set = sortedset([3,7,2,2])
sortedset([2, 3, 7]

Answer 4

不完全是“排序容器”，但您可能对标准库的 bisect 模块感兴趣，该模块“提供对按排序顺序维护列表的支持，而无需在每次插入后对列表进行排序”。

Answer 5

标准库中有一个

heapq

，它没有完全排序，但有点排序。还有一个 blist 包，但它不在标准库中。

Answer 6

对于排序集的特定情况，我发现

Flag

有用，例如：

from enum import Flag
Color = Flag('Color', 'RED GREEN BLUE')

这可以像集合一样使用，

|

是并集，

&

是交集，

~

是逆集，例如：

set1 = Color.RED | Color.GREEN
set2 = Color.BLUE
union = set1 | set2
intersection = set1 & set2
inversion = ~set1
empty = Color(0)
universal = ~empty
print(universal)

哪个打印：

Color.RED|GREEN|BLUE

集合按照声明顺序自动排序（关于集合的讨论点），并且通用集合是封闭的（我喜欢）。

Answer 7

Python 列表是有序的。如果你对它们进行排序，它们就会保持原样。在 Python 2.7 中，添加了

OrderedDict

类型来维护显式排序的字典。

Python 也有 sets （一个集合，其中的成员必须是唯一的），但根据定义它们是无序的。对集合进行排序只会返回

list

。