Gap Buffer 是什么？为什么文本编辑器可以用数组高效插入字符？
简化版
Gap Buffer 是一种带“空洞”的数组结构，把光标附近预留一段空位。光标处连续插入字符时，只需要填空洞，不必每次移动后面所有字符。
详细版
普通数组在中间插入元素要移动后缀，文本编辑器频繁在光标处插入字符，如果每次都移动会很慢。Gap Buffer 用一个连续数组保存文本，并维护一个 gap。
- gap 表示数组中暂时不用的一段空间。
- 光标通常位于 gap 的边界。
- 插入字符时填入 gap，O(1) 摊还。
- 光标远距离移动时，需要移动 gap，成本和移动距离有关。
- 适合局部编辑密集的场景，不适合所有文本结构需求。
完整版教学
一、为什么普通数组不适合频繁中间插入
数组中间插入需要把插入点后的元素整体右移。如果用户在文本开头连续输入 1000 个字符，朴素数组每次都移动后面所有文本，成本会很高。文本编辑器的访问模式有一个特点：用户通常在光标附近连续输入。Gap Buffer 正是利用这个局部性，把光标附近提前留出空位，让连续插入变便宜。
普通数组插入:
[H e l l o]
在中间插入 X -> 后缀整体右移记忆钩子：Gap Buffer 像在光标处预留一段空白稿纸，连续写字不用每次挪整篇文章。
二、Gap Buffer 的内存布局
Gap Buffer 底层仍是一段数组，只是中间有一段 gap 不存有效字符。有效文本由 gap 左边和右边拼起来。光标通常位于 gap 的左边界或右边界，插入字符就是把字符写进 gap，并缩小 gap。删除字符可以扩大 gap。这个结构看起来不像链表，但利用数组连续内存，缓存也比较友好。
数组内容:
[H e l _ _ _ _ l o]
^gap
显示文本: "Hello"三、插入为什么快
只要 gap 还有空间，在光标处插入字符就是写数组位置并移动 gap 边界，通常 O(1)。如果 gap 用完了，就需要扩容或重新开更大的 gap，这类似动态数组扩容，是偶发成本。摊还来看，连续插入可以很快。它把每次插入移动后缀的成本，变成偶尔扩 gap 的成本。
gap: [_ _ _]
输入 a -> [a _ _]
输入 b -> [a b _]
输入 c -> [a b c]四、移动光标为什么有成本
Gap Buffer 的弱点是光标远距离移动。为了让插入仍发生在 gap 处，需要把 gap 移动到新光标位置。移动 gap 本质上是把跨过的字符从 gap 一侧搬到另一侧，成本和移动距离成正比。如果用户总是在文档两端来回跳，Gap Buffer 就不如局部连续编辑那么舒服。
| 操作 | 成本特点 |
|---|---|
| 光标处连续插入 | 很快，摊还 O(1) |
| 删除光标附近字符 | 很快 |
| 光标远距离跳转 | O(移动距离) |
| 随机多点编辑 | 不一定合适 |
五、带数字看局部性收益
假设一篇文本有 10 万字符，用户在第 5 万位置连续输入 1000 个字符。朴素数组每次插入可能移动约 5 万字符，总移动量约 5000 万。Gap Buffer 如果 gap 足够大，1000 次插入主要是 1000 次写入。差距来自用户编辑的局部性：连续输入都发生在同一个光标附近。
朴素数组：1000 × 50000 = 50,000,000 次字符移动
Gap Buffer：约 1000 次写入，外加可能的一次扩 gap六、和链表、Rope 的对比
链表中间插入看似 O(1)，但定位光标、缓存局部性和按行渲染都可能不友好。Rope 适合非常大的文本和复杂拼接，用树结构管理字符串片段，但实现更复杂。Gap Buffer 实现简单、局部编辑快，所以很多编辑器或编辑组件会采用类似思想。数据结构选择仍然取决于文本规模和操作模式。
Gap Buffer：简单，局部编辑快
链表：插入快但定位和缓存差
Rope：适合大文本和复杂拼接，实现复杂七、常见误区与追问
- 误区：Gap Buffer 不是数组。 它底层仍然是数组，只是中间维护一段空洞。
- 误区：所有插入都是严格 O(1)。 gap 用完要扩容，光标远移也要搬动字符。
- 误区：链表一定更适合编辑器。 链表定位和缓存局部性较差，不一定比 Gap Buffer 好。
- 追问：gap 在哪里？ 通常在光标附近，方便连续插入和删除。
- 追问：适合什么编辑模式？ 适合局部连续编辑，不适合大量随机多点编辑。
八、加强记忆
Gap Buffer 可以记成“数组里留一段空洞给光标”。输入字符时填洞，删除时扩大洞，移动光标时搬洞。面试回答时先讲普通数组中间插入慢，再讲 gap 的布局和局部性收益，最后补上远距离移动的代价，就能把这个低频但很有味道的数据结构讲清楚。