深入解析Python 中的 sortedcontainers 库：高效的排序数据结构

在日常的 Python 编程中，列表（list）、集合（set）和字典（dict）是常用的数据结构。然而，在某些特定的场景下，我们需要对数据进行排序，并且希望在插入、删除或访问元素时能够保持有序。在标准库中，虽然我们可以通过 list.sort() 或者 sorted() 函数对列表进行排序，但这些操作每次都需要 O(n log n) 的复杂度，这对一些高频操作来说效率并不理想。

sortedcontainers 是一个高效的 Python 库，它为开发者提供了三种主要的容器数据结构，分别是 SortedList、SortedDict 和 SortedSet，能够在 O(log n) 的时间复杂度下完成插入、删除和访问操作，并且自动保持元素的有序性。在本文中，我们将详细介绍 sortedcontainers 库的核心功能，展示如何利用它的高效数据结构解决一些常见的编程问题。

❓ 为什么选择 sortedcontainers？

sortedcontainers 是一个轻量级且高效的库，提供了自动排序的数据结构，能够替代 Python 标准库中的 list、set 和 dict 等常用容器。该库的特点包括：

1. 高效性：所有操作的时间复杂度均为 O(log n)，远优于每次插入后再进行排序的 O(n log n)。
2. 简单易用：API 设计与标准库类似，上手非常容易，开发者只需要稍微修改代码就能替换掉标准容器。
3. 自动排序：在插入和删除元素时，容器会自动保持有序，无需额外的手动排序操作。
4. 纯 Python 实现：该库无需依赖 C 扩展，因此可以轻松在各种平台上使用。

安装

在开始之前，你需要通过 pip 安装 sortedcontainers 库：

pip install sortedcontainers

安装完成后，你就可以在你的项目中使用它了。

🔴 SortedList - 有序列表

SortedList 是 sortedcontainers 中的一个有序列表实现，它在元素插入、删除时会保持有序，同时能够提供快速的索引访问。

基本操作

from sortedcontainers import SortedList# 创建一个 SortedList
sl = SortedList([3, 1, 4, 1, 5, 9, 2, 6])# 自动排序后输出
print(sl)  # 输出: SortedList([1, 1, 2, 3, 4, 5, 6, 9])# 插入元素
sl.add(7)
print(sl)  # 输出: SortedList([1, 1, 2, 3, 4, 5, 6, 7, 9])# 删除元素
sl.remove(3)
print(sl)  # 输出: SortedList([1, 1, 2, 4, 5, 6, 7, 9])# 访问元素（支持索引操作）
print(sl[0])  # 输出: 1# 使用 bisect 方法查找元素的位置
index = sl.bisect_left(5)
print(index)  # 输出: 4（5 应该在索引 4 处插入）

SortedList 的主要特性

• 自动排序：元素插入和删除后，列表会自动排序。
• 索引访问：你可以像操作普通列表一样，通过索引访问元素。
• 二分查找：SortedList 提供了 bisect_left 和 bisect_right 等方法，方便进行二分查找操作。
• 支持切片：可以直接对 SortedList 进行切片操作。

应用场景：排行榜

假设你需要实现一个游戏排行榜，玩家的得分会不断变化，我们可以使用 SortedList 来保持得分有序，快速插入和删除玩家。

players = SortedList([("Alice", 1200), ("Bob", 900), ("Charlie", 1350)])# 添加一个新玩家
players.add(("David", 1100))# 让 Bob 的得分提高
players.remove(("Bob", 900))
players.add(("Bob", 950))# 输出排名
for rank, player in enumerate(players, 1):print(f"Rank {rank}: {player[0]} with score {player[1]}")

🔴 SortedDict - 有序字典

SortedDict 是一个保持键有序的字典。当你在标准库的 dict 中插入新键时，顺序取决于插入的顺序，而 SortedDict 始终按键的顺序存储。

基本操作

from sortedcontainers import SortedDict# 创建一个 SortedDict
sd = SortedDict({"b": 2, "a": 1, "c": 3})# 打印有序字典
print(sd)  # 输出: SortedDict({'a': 1, 'b': 2, 'c': 3})# 插入新元素
sd["d"] = 4
print(sd)  # 输出: SortedDict({'a': 1, 'b': 2, 'c': 3, 'd': 4})# 删除元素
del sd["b"]
print(sd)  # 输出: SortedDict({'a': 1, 'c': 3, 'd': 4})# 访问元素
print(sd["c"])  # 输出: 3

SortedDict 的主要特性

• 按键排序：无论键的插入顺序如何，SortedDict 始终按键的大小进行排序。
• 类似标准字典：操作方式与 Python 内置的 dict 非常相似，支持增删改查等操作。
• 键的二分查找：可以像 SortedList 一样，对键进行二分查找。

应用场景：事件调度

假设你在开发一款模拟城市建设的游戏，玩家可以安排各种建筑的建造时间，我们可以用 SortedDict 来管理按时间顺序排列的事件。

events = SortedDict()# 添加建筑事件
events[5] = "建造房屋"
events[1] = "建造道路"
events[10] = "建造公园"# 输出按时间顺序安排的事件
for time, event in events.items():print(f"时间 {time}: {event}")

🔴 SortedSet - 有序集合

SortedSet 是 sortedcontainers 提供的一个有序集合实现，类似于 Python 的 set，但会保持集合中的元素有序。

基本操作

from sortedcontainers import SortedSet# 创建一个 SortedSet
ss = SortedSet([3, 1, 4, 1, 5, 9, 2, 6])# 自动排序后输出
print(ss)  # 输出: SortedSet([1, 2, 3, 4, 5, 6, 9])# 插入新元素
ss.add(7)
print(ss)  # 输出: SortedSet([1, 2, 3, 4, 5, 6, 7, 9])# 删除元素
ss.remove(5)
print(ss)  # 输出: SortedSet([1, 2, 3, 4, 6, 7, 9])# 判断元素是否存在
print(4 in ss)  # 输出: True

SortedSet 的主要特性

• 自动去重：与标准 set 一样，SortedSet 保证集合内没有重复元素。
• 自动排序：集合中的元素始终保持有序。
• 高效查找：SortedSet 也提供了类似于 SortedList 的查找功能。

应用场景：独特元素的排序管理

假设你正在开发一个电子商务平台，用户可能会多次浏览同一产品。为了防止重复记录用户浏览过的产品并保持浏览记录的有序性，我们可以使用 SortedSet。

viewed_products = SortedSet()# 用户浏览了多个产品
viewed_products.update([101, 203, 101, 302, 203, 404])# 输出用户浏览的产品，按产品 ID 排序
print("用户浏览过的产品:", viewed_products)

🥇 性能与应用

sortedcontainers 使用纯 Python 实现，但由于其内部采用了基于分块数组的高效算法，能够在实际应用中表现出与 C 实现的类似性能。常见的用法包括：

1. 动态保持有序数据结构：当你需要一个容器时刻保持有序时，sortedcontainers 提供了高效的替代方案，避免了频繁的手动排序。
2. **

事件调度与优先级队列**：SortedList 和 SortedDict 非常适合管理按时间或优先级排序的任务或事件。
3. 快速查找和访问：二分查找、插入、删除操作的时间复杂度为 O(log n)，在需要频繁操作有序数据的场景下，比使用标准容器更高效。

📥 下载地址

sortedcontainers 最新版 下载地址

💬 结语

sortedcontainers 是一个功能强大、灵活且高效的 Python 库，它为开发者提供了 SortedList、SortedDict 和 SortedSet 三种有序容器。在需要有序数据结构的场景中，sortedcontainers 能够显著简化代码逻辑并提高运行效率。它的 API 设计与标准容器相似，易于上手，并且能够在许多实际项目中替代 Python 的标准数据结构，尤其是在需要频繁插入、删除和查找的有序数据场景中。

📒 参考文献

• sortedcontainers GitHub仓库

通过本文的介绍和代码示例，你现在应该对如何使用 sortedcontainers 来处理有序数据有了更深入的理解，并能够在你的项目中应用这些高效的数据结构来解决各种排序和优先级问题。