游标失效

在 SortAO 中，游标失效 (Cursor Invalidation) 是一个核心概念。

作为数据结构库，为了性能起见，容器不会在发生变更时主动通知、修改现有的游标。

理解游标何时失效，以及如何安全地使用，是编写高性能且正确代码的前提。

两种失效情况

在使用 SortAO 游标的过程中，您会遇到两种失效情况。

物理失效：游标持有的物理指针（如内存块索引、树节点引用）已不再指向合法的分配空间。

• 现象：尝试访问 value 会明确返回 undefined，调用 refresh() 会明确返回 false。
• 原因：底层的内存块因扩容、收缩而发生结构变化，或节点被删除。

逻辑失效：物理指针依然“合法”，但由于突变操作，它所指向的内容已不再是最初那个元素。

• 现象：读取 value 可能会得到一个与 index 不匹配的元素。
• 原因：在数组型容器的游标位置附近插入或删除了元素，导致后续元素发生平移。

这些都是突变操作引起的游标失效情况。

规则

Block-Array 与 Sorted-Block-Array

使用了连续的内存区域，具有最严苛的失效规则。

1. 在尾部插入、删除时，不会 导致游标失效。
2. 在头部插入、删除时，会 导致所有游标失效。
3. 在中间插入、删除时，会 导致部分游标失效。
   当操作的 index 为 X 时，指向 X - B 以后的所有游标都会失效。
4. 保证 state === 2 (即 CursorState.rend ) 的游标从不失效。

Block-List 与 Sorted-Block-List

使用了连续的内存区域，具有最严苛的失效规则。

1. 在尾部插入、删除时，不会 导致游标失效。
2. 在头部插入、删除时，会 导致所有游标失效。
3. 在中间插入、删除时，会 导致部分游标失效。
   当操作的 index 为 X 时，指向 X - B 以后的所有游标都会失效。
4. 保证 state === 2 (即 CursorState.rend ) 的游标从不失效。

Block-Deque 与 Sorted-Block-Deque

使用了连续的内存区域，具有最严苛的失效规则。

1. 在尾部插入、删除时，不会 导致游标失效。
2. 在头部插入、删除时，不会 导致游标失效。
3. 在中间插入、删除时，会 导致所有游标失效。
4. 保证 state === 2 (即 CursorState.rend ) 的游标从不失效。

Splay-Tree

具有最宽松的失效规则。

1. 在任意位置插入时，不会 导致游标失效。
2. 在任意位置删除时，会 导致指向被删除位置的游标失效。
3. 在合并后，会 导致被合并的树的所有游标失效。
4. 保证 state === 2 (即 CursorState.rend ) 的游标从不失效。

指南

如果容器的失效规则较为严苛，请避免在迭代中使用突变操作，如

// ❌ 危险操作
while (cur.active) {
  if (cur.value === target) container.insert(0, "X"); // 可能导致 cur 逻辑失效
  cur.next();
}

如果无法确定游标是否能安全访问，请遵循这个最简单的原则：重新 seek 到您希望的逻辑位置。

如果您对效率有严苛的要求，请考虑不使用包装器，因为容器自身往往提供更多方法和访问方式。