python的有序容器：sortedcontainers（第三方模块）

sortedcontainers 库

https://leetcode.cn/circle/article/uNRLWK/

C++中标准容器中不仅提供了常用的vector, set, map等容器，还提供了有序容器，如set等。
同样， Python 也提供了有序容器：SortedList， SortedKeyList， SortedDict， SortedSet。
这些容器不常用，我总是学了就忘，特写这篇文档，系统地再复习下。

SortedList

SortedList维护一个升序的列表。

• 添加元素:
  add() 添加一个元素，按照顺序排列进去
  update() 添加一列元素，按照顺序排列进去

• 删除元素：
  remove(value) 删除值为value的元素，要是列表中没有这个值，会报错
  discard（value） 删除值为value的元素，如果列表中没有这个值，不会报错（内置列表没有这个方法）
  pop(index) 删除索引为index的元素
  del list_name[index] 删除索引为index的元素
  clear() 清空整个列表

• 查找元素：
  index(value) 查找列表中value第一次出现的索引位置
  count(value) 返回value在列表中的个数
  bisect_left(value) 若向列表中插入value时，value所处的位置（如果有相同的，则返回最左边的位置）
  bisect_right(value) 若向列表中插入value时，value所处的位置（如果有相同的，则返回最右边的位置）

同时，SortedList还支持几乎内置列表的所有功能，如切片，操作符 in， + ， * 等，功能十分强大
SortedList尚未支持的功能：append(), extend()，insert(), reverse() 和直接赋值。 原因很好理解：SortedList是一个有序的列表，这些方法会打破列表的有序性。

SortedKeyList

SortedKeyList是SortedList的一个子类，支持SortedList的大部分方法。但支持自定义排序方法:

my_list = SortedKeyList(key = lambda x: -x)
1

额外操作:

bisect_left变为了bisect_key_left, bisect_right变为了bisect_key_right。

SortedDict

SortedDict维护一个升序字典，可自定义比较函数。

• 添加元素:

​ update() 添加若干键值

​ my_dict[key] = value 直接赋值

​ setdefault()

• 删除元素：

​ del my_dict[key] 删除键

​ pop(key) 删除键

​ popitem(index = -1) 删除索引为indx的键，默认为-1， 并返回(键，值)

​ clear() 清空字典

• 查找元素：

​ my_dict[key] 按键求值

​ peekitem(index = -1) 返回元组，求索引为index的(键， 值)，默认为-1

​ get(key) 求键为key的值，可设置默认返回值

​ index(key) 求key对应的索引

SortedSet

SortedSet维护一个升序集合，可自定义比较函数。

• 添加元素:

  add(), 添加一个元素

  update() 添加一些元素

• 删除元素：

  remove(value) 删除值为value的元素，如果集合中没有这个值，会报错
  discard（value） 删除值为value的元素，如果集合中没有这个值，不会报错
  pop(index) 删除索引为index的元素
  del my_set[index] 删除索引为index的元素

• 查找元素：
  bisect(value) 返回value的索引
  index(value) 返回value的索引
  my_set[index] 按键索引

总结：
因为是有序容器，所有在删改容器的时候，使用的是二分法，时间复杂度大多是O(nlogn), 合理地运用这些容器，可以提高算法的时间复杂度。

问：如果说是严格升序, 那么能用某种意义上的链表或者堆也能实现的吧？

答：但特殊情况下，用这个更方便，比如23. 合并 K 个升序链表，如果要求不能新建节点或要求空间复杂度的话。 你用heapq.heappush就无法自定key参数。 你得在链表里添加比较函数(cmp)，很麻烦。 你用SortedKeyList就方便一点。 而且从另一个角度，SortedList支持常数级的索引， heap类似的方法是求n_largest/n_smallest，时间复杂度logn。

答：谢谢, 这个是比较醍醐灌顶的, 我觉得能够自带扩容+排序逻辑的结构, 面向并行请求表格类的数据以及索引去做接纳, 是相当友好的存在了, 也确实是觉得不管是c的还是Java的cmp函数要另外传指针有一点冗余(即能先排列好数据再去进行别的操作)。不能不想到ConcurrentHashMap这种的扩容和树链互换。看来我还是对特殊类型树的节点翻转和合并要再学学

• 底层原理

  https://www.zhihu.com/question/593450942/answer/2966795898

  py中sortedcontainers下的有序集合，比如SortedList,SortedDict，这些集合的排序功能的时间复杂度是O（logn）的，但是它不像其他语言那样使用的是红黑树排序的，而是纯粹靠python的有序列表外加一些优化手段，没有使用到红黑树。

  先说结论，全靠有序列表外加一些优化手段，没有用红黑树，也没有AVL树。

  sortedcontainers主要实现了这四个容器类：SortedList、SortedKeyList、SortedSet和SortedDict。阅读源码得知，SortedKeyList、SortedSet和SortedDict都是基于SortedList实现的，所以直接分析SortedList就好了。

  实现基于：

  • 首先，Python 的列表很快，非常快。列表对于内存管理和随机访问具有很大的特性。
  • 第二个是bisect.insort速度很快，关键点：不太长的list上做insert之类的操作非常快。这有点违反直觉，因为它涉及移动列表中的一系列项目。但现代处理器在这方面做得非常好。我们花费了大量的时间来优化硬件和软件方面的类似内存复制/内存移动的操作。

  底层设计：

  • 底层维护三个内部变量： _lists、 _maxes和 _index。第一个只是列表的列表，每个成员都是元素的排序子列表。第二个包含每个子列表中的最大元素，这用于快速二分搜索。最后一个维护着列表长度的成对总和的树。
    • 首先，_lists使用的列表的列表的结构，类似于[[1, 2, 3], [4, 5], [6, 7, 8, 9], [10, 11, 12, 13, 14]]的东西，它里面的每个元素都是一个有序列表，_lists摊平之后就是实际的有序列表。
    • 其次，_maxes，存储_lists中每个列表的最大值，以上述例子为例就是[3, 5, 9, 14]
    • 最后，_index的构建有点复杂，看上面链接

  如果我们自己来实现的话，好像只需维护一个有序列表就可以了，但是这样插入和删除元素时复杂度是O(n)，SortedList的巧妙之处就在于将整个有序列表划分为若干个有序的子列表，这样可以把元素改动限定在局部范围内，从而减少改动元素的时间。

官方给出的实现细节

sortedcontainers类似于C++20新出的flat_map、flat_set之类的容器，用数组代替树实现有序容器，空间局部性更好。

传统的基于树的设计具有更好的大 O 表示法，但这忽略了当今软件和硬件的现实。如需更深入的分析，请阅读 大规模性能。