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

Question

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

(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 + 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模块感兴趣，它“支持按排序顺序维护列表，而不必在每次插入后对列表进行排序”。