6.9 游标简介

5 分钟阅读

原文链接: https://rust-unofficial.github.io/too-many-lists/sixth-cursors-intro.html

好！！！我们现在有个和 std 1.0 实现同水平的 LinkedList！当然意味着我们的 LinkedList 仍然完全没用。我们承受了用链表实现 Deque 的巨大性能代价，却没有让它真正有用的 API。

和链表「杀手级应用」比一比：

🚫 做 weird intrusive stuff
🚫 做 weird lockfree stuff
🚫 存 Dynamically Sized Types
🌟 O(1) push/pop 且无需摊还（若你愿意相信 malloc 是 O(1)）
🚫 O(1) 链表分裂
🚫 O(1) 链表拼接

嗯…… 6 项里 1 项……比没有强！懂我为什么想把它从 std 里撕下来了吧？

我们不会让链表支持「weird」东西，那些都 adhoc、领域特定。但分裂和拼接，这个我们能做！

但问题是：到达 LinkedList 第 k 个元素要 O(k)，怎么可能 O(1) 任意 split/merge？诀窍是：没有 split_at(index) 这种 API——让用户有状态地迭代到某位置，在那 O(1) 修改！

嘿，我们已有迭代器！能用吗？Kind of……但其中一个 super-power 碍事。你可能记得 by-ref 迭代器的 lifetime 写法意味着返回的引用不绑在迭代器上。这样能反复 next 并持有元素：

1
2
3
4
5
6
let mut list = ...;
let iter = list.iter_mut();
let elem1 = list.next();
let elem2 = list.next();

if elem1 == elem2 { ... }

若返回的引用借用迭代器，这代码根本不行，第二次 next 编译器就抱怨！这种灵活性 great，但给我们 implicit 约束：

By-Mutable-Ref 迭代器不能后退再产出元素，否则用户能对同一元素拿两个 &mut，破坏语言 fundamental 规则。
By-Ref 迭代器不能有会以 invalidate 已产出引用的方式修改底层集合的额外方法。

不幸的是，这两样正是我们 LinkedList API 想要的！所以不能只用迭代器，需要新东西：Cursor。

Cursor 就像电脑上编辑文本时闪烁的 |。是序列（文本）里的位置，可以移动（方向键），输入时编辑发生在该点。

看，我若

按

回车

整段

文本

就劈成两半。

抱歉你站我身后看我打字对吧？那 totally 说得通吧？对吧。

若不幸有带 Insert 键的键盘还按过，你知道 cursor technically 有两种解释：在元素（字符）之间，或在元素上。我 pretty sure 没人故意按过 Insert，它 purely 是 Suffering Button，所以 obviously 哪个 Better and Right：cursor 在元素之间！

Pretty rock-solid logic，我觉得没人能 disagree。

抱歉什么？2018 年有个 RFC 要给 Rust LinkedList 加 Cursor？

With a Cursor one can seek back and forth through a list and get the current element. With a CursorMut One can seek back and forth and get mutable references to elements, and it can insert and delete elements before and behind the current element (along with performing several list operations such as splitting and splicing).

Current element？这 cursor 是在元素上，不是之间！不敢相信他们没接受我 totally rock-solid 的论点！所以你可以去用 std 的 Cursor……等等，2022 年 Rust 1.60 里 Cursor 还标 unstable？

嘿等等：

Cursors always rest between two elements in the list, and index in a logically circular way. To accommodate this, there is a “ghost” non-element that yields None between the head and tail of the list.

嘿等等。这和 RFC 说的相反？？？但方法文档还 refer to “current” elements……等等 hold on，这 ghost 我在哪见过。哦等等，不是我 2015 年 old linked-list fork 里 prototype 的吗？

Cursors always rest between two elements in the list, and index in a logically circular way. To accomadate this, there is a “ghost” non-element that yields None between the head and tail of the List.

Hold up what the fuck。这不是 gag，我真在 Read The Docs。std 是不是 RFC 了和我 2015 提案不同的设计，然后 copy-paste 我 prototype 的 docs？？？std 在 meta-shitpost 我写 hate LinkedList 的书吗？？？对，我建 prototype 是为了 demo 概念让人加进 std 让 LinkedList 不 useless，但 qu’est-ce que le fuck??????????????

Ok you know what，clearly std 在 bless 我的设计为 objectively superior，我们就做我的设计。也好，整章 literally 是从 scratch 重写那个库，不改 API sounds Good To Me！

这是我写的完整顶层文档：

A Cursor is like an iterator, except that it can freely seek back-and-forth, and can safely mutate the list during iteration. This is because the lifetime of its yielded references are tied to its own lifetime, instead of just the underlying list. This means cursors cannot yield multiple elements at once.
Cursors always rest between two elements in the list, and index in a logically circular way. To accomadate this, there is a “ghost” non-element that yields None between the head and tail of the List.
When created, cursors start between the ghost and the front of the list. That is, next will yield the front of the list, and prev will yield None. Calling prev again will yield the tail.

Cute，虽然我们 concluded sentinel-node more trouble than worth，语义仍会「假装」有 sentinel，让 cursor wrap 到链表另一侧。

Skims over my old APIs some more

1
fn splice(&mut self, other: &mut LinkedList<T>)

Inserts the entire list’s contents right after the cursor.

Oh yeah，想起来了。写这时 really mad about combinatoric explosion，想每种操作只一份 copy。Unfortunately 这…… semantically problematic。用户 splice 一个链表进另一个，可能希望 cursor 在 splice 前或后。插入链表可以 arbitrarily 大，只允许一种并 expect 用户 walk 整个插入链表是 genuine issue！

After all 得 ground up 重做设计。Cursor 需要什么？

指向两元素「之间」
作为 nice feature，跟踪 next 的「index」
更新链表本身以改 front/back/len。

怎么指向两元素之间？Well，不。只指向「next」元素。所以 yeah 虽然暴露「cursor 在之间」语义，实现上是「cursor 在」上，假装一切发生在该点 before/after。

但有 reason！splice 用例要让用户选 splice 后 before 还是 after，用 std API 表达这…… horribly complicated！他们有 splice_after 和 splice_before，但都不改 cursor 位置，所以 really 需要 splice_after_before 和 splice_after_after……

Wait no I’m being silly。std API 可以选想 end up 的 node，再用 splice_after/before appropriately。

squints

Wait std API actually good。

skims through the code

Ok std API actually good。

算了，我们直接实现该 RFC。至少有趣的部分。

我对 std 部分 terminology 有 quibble，但 cursor always 有点 brain-melty：iter().next_back() 得到 back()，good，但 subsequent next_back() actually 靠近 front，indeed 每条 pointer 都是「front」pointer！想这 seeming-paradox 太多 brain hurts，所以 respect 用不同 terminology 避免。

std API 说 before「before」（towards front）和 after（towards back）的操作，不用 next/next_back，而……叫 move_next 和 move_prev。HRM。Ok 有点 iterator terminology，至少 next 不 evoke front/back，帮助 orient 相对迭代器的行为。

We can work with this.

最后修改 August 23, 2026: 更新 (499855b16)