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

Question

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

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

Answer 1

还有一个 python sortedcontainers 模块，它实现排序列表、字典和集合类型。它与 blist 非常相似，但在纯 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

还有 blist 模块，其中包含 sortedset 数据类型：

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)

Which prints:

Color.RED|GREEN|BLUE

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

Answer 7

Python 列表是有序的。如果你对它们进行排序，它们就会保持原样。在 Python 2.7 中，添加了 OrderedDict 类型维护一个显式排序的字典。

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