数据结构、抽象类型与不变量
本节目标
从“要支持哪些操作”而不是“记住多少容器”开始：区分数据、抽象数据类型（Abstract Data Type, ADT）、具体表示和算法，并用不变量证明一次更新后结构仍然有效。
四个层次不要混用
| 层次 | 回答的问题 | 任务调度示例 |
|---|---|---|
| 数据元素 | 保存什么？ | 任务 ID、优先级、依赖 ID |
| ADT / 接口 | 允许做什么？ | 加入任务、取得下一个就绪任务、查询状态 |
| 数据结构 / 表示 | 数据怎样组织？ | dict 索引、set 依赖、heapq 就绪堆 |
| 算法 | 怎样完成某次操作？ | 拓扑推进、堆压入/弹出、环检测 |
队列 ADT 规定“入队”和“按先进先出取出”；它可以由 collections.deque、持久化消息系统或其他结构实现。接口是需求，表示是方案。先写接口和约束，才知道该比较哪些操作成本。
用操作画像选择结构
选择前写出：
- 数据规模和增长方式；
- 最频繁的读、写、删除和遍历；
- 是否保序、允许重复、需要按键或优先级访问；
- 是否允许原地修改，谁拥有对象；
- 容量、持久化、并发和失败要求；
- 结果是否必须确定性、可重放。
同一批消息：若主要按顺序追加与整体遍历，list 很自然；若只关心最近 100 条，用 deque(maxlen=100)；若频繁按消息 ID 查找，增加 dict 索引。没有脱离操作的“最佳数据结构”。
不变量是始终成立的规则
**不变量（invariant）**是在结构建立后、每次公开操作完成后都必须为真的条件。例如工具注册表：
- 每个工具名唯一且非空；
- 字典键与工具对象中的
name一致； - 所有写工具都有明确审批级别；
- 删除后不能残留在按风险分组的辅助索引中。
如果同时维护列表和集合：
class OrderedUniqueIds:
def __init__(self) -> None:
self._items: list[str] = []
self._seen: set[str] = set()
def add(self, item: str) -> bool:
if item in self._seen:
return False
self._seen.add(item)
self._items.append(item)
return True
def snapshot(self) -> tuple[str, ...]:
assert len(self._items) == len(self._seen)
assert set(self._items) == self._seen
return tuple(self._items)这里由一个方法同步更新两个结构，避免调用方只改其中之一。示例中的 assert 用来表达开发期内部不变量；不可信输入仍需正常校验与异常，不能依赖 assert，因为优化模式可移除它。
前置条件、后置条件与所有权
- 前置条件：调用前必须满足，例如任务 ID 已通过格式校验；
- 后置条件：成功后保证，例如新任务可按 ID 查到；
- 所有权：谁可以修改对象，函数是否复制输入；
- 失败原子性：操作失败时结构是保持原样，还是可能部分更新。
add_task(task)
前置：task.id 非空；依赖格式合法
成功后：任务数 +1；by_id[id] 指向该任务；未进入 ready 前不执行
失败后：所有索引保持调用前状态这比“内部用了字典所以快”更接近可验证工程契约。
抽象不等于过度封装
一个小脚本可以直接使用 dict 和 set。只有当多处代码必须共同维护不变量、需要替换实现或要限制副作用时，才建立类/模块边界。不要为每个列表创建包装类，也不要让调用方随意修改多个公开容器。
练习：ADT 卡片
为“Agent 工具注册表”写一张卡片：
- 列出
register、get、remove、list_by_risk四个操作； - 为每个操作写前置、成功后置和失败行为；
- 写至少 3 条全局不变量；
- 比较只用列表、只用字典、字典 + 分组索引三种表示；
- 说明哪种操作会决定最终选择。
自测
- 队列 ADT 与
deque是同一个概念吗？ - 为什么先列操作，再比较复杂度？
- 列表 + 集合同时维护时最容易破坏什么不变量？
assert为什么不能承担不可信输入校验？- 失败原子性要回答什么？
下一步与相关概念
- 下一节：复杂度、资源成本与实测。
- Python 函数、异常和测试边界见 Python基础。
参考资料
获取日期：2026-07-14。