Python 排序容器

本文最后更新于：2024年1月14日晚上

Python 的标准库没有排序容器，这些内容在 sortedcontainers 包中有了实现。

sortedcontainers

Python 标准库没有实现排序容器，在 sortedcontainers 库中有了相关实现。

pip 包文档： https://pypi.org/project/sortedcontainers/
按照命令：

1	`pip install sortedcontainers`

官方文档：http://www.grantjenks.com/docs/sortedcontainers/
Sorted Containers ，主要包含三类排序容器。

List

SortedList

创建排序列表对象

1	`sortedcontainers.SortedList(iterable=None, key=None)`

from sortedcontainers import SortedList

sl = SortedList('fjbcghaeid')
print(sl)
top = sl.pop()
print(list(reversed(sl)))

-->
SortedList(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'])
['i', 'h', 'g', 'f', 'e', 'd', 'c', 'b', 'a']

SortedKeyList

SortedKeyList 是排序列表的子类型，根据应用于每个值的键函数的结果以比较顺序维护值。
SortedList 中可用的所有相同方法在 SortedKeyList 中也可用。
SortedKeyList 的额外方法：
参考代码

from sortedcontainers import SortedKeyList

data = [4, 8, -1, -7, 19]
sl = SortedKeyList(data, key=abs)
print(sl)

-->
SortedKeyList([-1, 4, -7, 8, 19], key=<built-in function abs>)

Dict

SortedDict

排序的字典键按排序顺序维护。 sorted dict 的设计很简单：sorted dict 继承自 dict 来存储项目，并维护一个有序的 key 列表。

排序的 dict 键必须是可散列的和可比较的。键的散列和总排序在存储在排序字典中时不得更改。

建立字典

1	`sortedcontainers.SortedDict(args, *kwargs)`

映射方法
- SortedDict.__getitem__() (继承自 dict)
- SortedDict.__setitem__()
- SortedDict.__delitem__()
- SortedDict.__iter__()
- SortedDict.__len__() (继承自 dict)
增加元素的方法
- SortedDict.setdefault()
- SortedDict.update()
删除元素的方法：
查看元素的方法：
- SortedDict.__contains__() (继承自 dict)
- SortedDict.get() (继承自 dict)
- SortedDict.peekitem()
视图方法：
其他方法：
- SortedDict.copy()
- SortedDict.fromkeys()
- SortedDict.__reversed__()
- SortedDict.__eq__() (继承自 dict)
- SortedDict.__ne__() (继承自 dict)
- SortedDict.__repr__()
- SortedDict._check()
可用的排序列表方法（适用于键）：
如果使用了键功能，则可以使用其他排序列表方法：
参考代码

from sortedcontainers import SortedDict

d = {'c': 8, 'd': 4, 'a': 1, 'b': 2}
e = SortedDict([('c', 8), ('d', 4), ('a', 1), ('b', 2)])
print(d == e)
print(e)

-->
True
SortedDict({'a': 1, 'b': 2, 'c': 8, 'd': 4})

SortedKeysView

sortedcontainers.SortedKeysView(mapping)

排序键视图是排序字典键的动态视图。
当排序后的 dict 的键发生变化时，视图会反映这些变化。
键视图实现集合和序列抽象基类。
参考代码

from sortedcontainers import SortedDict

e = SortedDict([('c', 8), ('d', 4), ('a', 1), ('b', 2)])
print(e.keys())
view = e.keys()
del view[0]
print(view)
del view[-1]
print(view)
del view[:]
print(view)

-->
SortedKeysView(SortedDict({'a': 1, 'b': 2, 'c': 8, 'd': 4}))
SortedKeysView(SortedDict({'b': 2, 'c': 8, 'd': 4}))
SortedKeysView(SortedDict({'b': 2, 'c': 8}))
SortedKeysView(SortedDict({}))

SortedItemsView

sortedcontainers.SortedItemsView(mapping)

排序项目视图是排序字典项目的动态视图。
当排序的 dict 的项目发生变化时，视图会反映这些变化。
项目视图实现集合和序列抽象基类。
参考代码：

from sortedcontainers import SortedDict

e = SortedDict([('c', 8), ('d', 4), ('a', 1), ('b', 2)])
siv = e.items()
print(siv)
print(siv[0])
print(siv[-1])

del siv[0]
print(siv[:])

-->
SortedItemsView(SortedDict({'a': 1, 'b': 2, 'c': 8, 'd': 4}))
('a', 1)
('d', 4)
[('b', 2), ('c', 8), ('d', 4)]

SortedValuesView

sortedcontainers.SortedValuesView(mapping)

排序值视图是排序字典值的动态视图。
当排序后的 dict 的值发生变化时，视图会反映这些变化。
值视图实现了序列抽象基类。
参考代码：

from sortedcontainers import SortedDict

e = SortedDict([('c', 8), ('d', 4), ('a', 1), ('b', 2)])
svv = e.values()

print(svv[0])
print(svv[-1])

del svv[0]
print(svv[:])
print(e)
pass

-->
1
4
[2, 8, 4]
SortedDict({'b': 2, 'c': 8, 'd': 4})

Set

Sorted Set

排序集是排序的可变集。
排序后的集合值按排序顺序维护。排序集的设计很简单：排序集使用集合进行集合操作并维护一个排序的值列表。
排序后的集合值必须是可散列的和可比较的。值的散列和总排序在存储在排序集中时不得更改。
可变的集合方法：
序列方法：
删除值的方法：
集合操作方法：
其他方法：
可用的排序列表方法：
如果使用了键功能，则可以使用其他排序列表方法：
参考代码：

from sortedcontainers import SortedSet

ss = SortedSet([-3, 1, 2, -5, 4])
print(ss)

qq = SortedSet(ss, key=abs)
print(qq)


-->
SortedSet([-5, -3, 1, 2, 4])
SortedSet([1, 2, -3, 4, -5], key=<built-in function abs>)