Python 排序容器

本文最后更新于:2022年8月5日 晚上

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

sortedcontainers

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

1
pip install sortedcontainers

List

SortedList

  • 创建排序列表对象
1
sortedcontainers.SortedList(iterable=None, key=None)
1
2
3
4
5
6
7
8
9
10
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

1
2
3
4
5
6
7
8
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
2
3
4
5
6
7
8
9
10
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 的键发生变化时,视图会反映这些变化。
  • 键视图实现集合和序列抽象基类。
  • 参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 的项目发生变化时,视图会反映这些变化。
  • 项目视图实现集合和序列抽象基类。
  • 参考代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 的值发生变化时,视图会反映这些变化。
  • 值视图实现了序列抽象基类。
  • 参考代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

1
2
3
4
5
6
7
8
9
10
11
12
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>)

参考资料


Python 排序容器
https://www.zywvvd.com/notes/coding/python/python-sorted-container/python-sorted-container/
作者
Yiwei Zhang
发布于
2022年5月15日
许可协议