有序容器（Sorted Containers）

sortedcontainers 是 Pythonic 的有序容器的实现，其速度不亚于 C 扩展实现。

概括：

• 官方文档：http://www.grantjenks.com/docs/sortedcontainers/
• 授权协议：Apache2

sortedcontainers 的源代码是包含了全部的文档，你可以使用 help() 获取这些类或函数的全部信息。在使用 IDE 编写时，你也可以看到类型提示时包含了复杂度信息，例如，插入的复杂度是 $\mathcal{O}(\log n)$。

sortedcontainers 与内置的 collections.Counter 和 collections.defaultdict 不兼容，但是内置的类型总是兼容的。例如 defaultdict(int) | Counter() 总是返回一个 defaultdict，并支持 Counter 的原有结构。

sortedcontainers 不支持泛型，因此你不能使用 SortedList[int]() 来创建对象。同样，IDE 也得不到类型提示，这一点可能会在以后得到支持。

1. 安装

不需要 C/C++ 编译器，这是纯 Python 实现的：

pip install sortedcontainers

2. 示例

2.1 SortedList 类

from sortedcontainers import SortedList

sl = SortedList(['e', 'a', 'c', 'd', 'b'])
print(sl)
# SortedList(['a', 'b', 'c', 'd', 'e'])

sl *= 10_000_000
print(sl.count('c'))
# 10000000

print(sl[-3:])
# ['e', 'e', 'e']

上述的操作速度都快于 $\mathcal{O}(n)$ 的速度，但需要巨大的内存空间（ $1000$ 万个 "a", "e", "c" 等的引用）。即使这样，每个引用也只需要 8 个字节，这比典型的二叉树实现（红黑树、AVL-树、AA-树、伸展树或堆树）要节省 $66\%$ 的内存，因为那样还要储存两个指针。

2.2 SortedDict 类

from sortedcontainers import SortedDict

sd = SortedDict({'c': 3, 'a': 1, 'b': 2})
print(sd)
# SortedDict({'a': 1, 'b': 2, 'c': 3})

print(sd.popitem(index=-1))
# ('c', 3)

2.3 SortedSet 类

from sortedcontainers import SortedSet

ss = SortedSet('abracadabra')
print(ss)
# SortedSet(['a', 'b', 'c', 'd', 'r'])

print(ss.bisect_left('c'))
# 2

3. API 参考

3.1 SortedList

class sortedcontainers.SortedList(iterable=None, key=None)

• 继承自 collections.abc.MutableSequence

如果初始化的时候使用了 key=func，那么它将自动转换为 SortedKeyList 对象，这样比较的时候将 func 应用到每一个元素。

SortedKeyList 是 SortedList 类的子类。

Methods for adding values:

SortedList.add()

SortedList.update()

SortedList.__add__()

SortedList.__iadd__()

SortedList.__mul__()

SortedList.__imul__()

Methods for removing values:

SortedList.clear()

SortedList.discard()

SortedList.remove()

SortedList.pop()

SortedList.__delitem__()

Methods for looking up values:

SortedList.bisect_left()

SortedList.bisect_right()

SortedList.count()

SortedList.index()

SortedList.__contains__()

SortedList.__getitem__()

Methods for iterating values:

SortedList.irange()

SortedList.islice()

SortedList.__iter__()

SortedList.__reversed__()

Methods for miscellany:

SortedList.copy()

SortedList.__len__()

SortedList.__repr__()

SortedList._check()

SortedList._reset()

3.1.1 SortedKeyList

Additional methods provided:

SortedKeyList.key()

SortedKeyList.bisect_key_left()

SortedKeyList.bisect_key_right()

SortedKeyList.irange_key()

3.2 SortedDict

class sortedcontainers.SortedDict(*args, **kwargs)

• 继承自 dict

Mutable mapping methods:

SortedDict.__getitem__() (inherited from dict)

SortedDict.__setitem__()

SortedDict.__delitem__()

SortedDict.__iter__()

SortedDict.__len__() (inherited from dict)

Methods for adding items:

SortedDict.setdefault()

SortedDict.update()

Methods for removing items:

SortedDict.clear()

SortedDict.pop()

SortedDict.popitem()

Methods for looking up items:

SortedDict.__contains__() (inherited from dict)

SortedDict.get() (inherited from dict)

SortedDict.peekitem()

Methods for views:

SortedDict.keys()

SortedDict.items()

SortedDict.values()

Methods for miscellany:

SortedDict.copy()

SortedDict.fromkeys()

SortedDict.__reversed__()

SortedDict.__eq__() (inherited from dict)

SortedDict.__ne__() (inherited from dict)

SortedDict.__repr__()

SortedDict._check()

Sorted list methods available (applies to keys):

SortedDict.bisect_left()

SortedDict.bisect_right()

SortedDict.count()

SortedDict.index()

SortedDict.irange()

SortedDict.islice()

SortedDict._reset()

Additional sorted list methods available, if key-function used:

SortedDict.bisect_key_left()

SortedDict.bisect_key_right()

SortedDict.irange_key()

3.2.2 视图 SortedKeysView

class sortedcontainers.SortedKeysView(mapping)

• 继承自 collections.abc.KeysView
• 继承自 collections.abc.Sequence

__getitem__(index)

__delitem__(index)

3.2.3 视图 SortedItemsView

class sortedcontainers.SortedItemsView(mapping)

• 继承自 collections.abc.ItemsView
• 继承自 collections.abc.Sequence

__getitem__(index)

3.2.4 视图 SortedValuesView

class sortedcontainers.SortedValuesView(mapping)

• 继承自 collections.abc.ValuesView
• 继承自 collections.abc.Sequence

__getitem__(index)

3.3 SortedSet

Mutable set methods:

SortedSet.__contains__()

SortedSet.__iter__()

SortedSet.__len__()

SortedSet.add()

SortedSet.discard()

Sequence methods:

SortedSet.__getitem__()

SortedSet.__delitem__()

SortedSet.__reversed__()

Methods for removing values:

SortedSet.clear()

SortedSet.pop()

SortedSet.remove()

Set-operation methods:

SortedSet.difference()

SortedSet.difference_update()

SortedSet.intersection()

SortedSet.intersection_update()

SortedSet.symmetric_difference()

SortedSet.symmetric_difference_update()

SortedSet.union()

SortedSet.update()

Methods for miscellany:

SortedSet.copy()

SortedSet.count()

SortedSet.__repr__()

SortedSet._check()

Sorted list methods available:

SortedSet.bisect_left()

SortedSet.bisect_right()

SortedSet.index()

SortedSet.irange()

SortedSet.islice()

SortedSet._reset()

Additional sorted list methods available, if key-function used:

SortedSet.bisect_key_left()

SortedSet.bisect_key_right()

SortedSet.irange_key()

4. 底层实现

相对于传统树实现的优势

• 大多数插入/删除不需要分配或释放内存。这可能是一个巨大的胜利，因为它给垃圾收集器和内存系统带来了很大的压力
• 指向元素的指针密集地打包。传统的基于树的实现需要两个指向子节点的指针（左/右）。列表没有这样的开销。这有利于硬件的内存架构，并更有效地利用缓存
• 每个项目的内存开销实际上是指向该项目的指针。二叉树实现必须为每个项目添加至少两个指针
• 迭代速度非常快，因为按顺序索引列表是现代处理器的优势

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

使用负载因子保持列表的平衡。如果子列表的长度超过负载的两倍，则将其一分为二。同样，在负载的一半下，它与邻居结合。默认情况下，此因子为 1000，对于长达 1000 万的长度，似乎很有效。高于该长度的建议载荷系数是平均长度的平方根到立方根。

网站还提供了 负载系数性能比较。