问题标签 [ropes]

我正在阅读如何从头开始制作文本编辑器。我遇到了各种不同的数据结构，例如间隙缓冲区、块表和绳索。我可以理解其他人在实践中的工作方式，并且我了解绳索的好处以及它在后勤方面的工作方式。但是，我不明白编辑器如何实际使用绳索。让我解释。

假设我有一个新文件并输入“Hello world！”。我会想象每次按键编辑都会处理每个字符。但是，从程序逻辑方面来看，我看不到处理每个新字符的明显方法。据我了解，rope 很有用，因为树结构允许相对低成本的搜索、插入、追加和删除。但是，如果我正在逐个字符地处理输入，我应该有：

1. 每个节点都是一个字符
2. 让每个节点保存 X 个字符
3. 每个节点都是一个完整的单词，节点以空格分隔
4. 每 X 次输入的每个字符都进入一个节点
5. 我还没有想到的东西

第一个选项虽然很容易实现，但似乎没有多大意义，我不认为最好地利用绳索结构。第二个选项似乎只是通过附加到节点内的字符串直到它达到 X 长度来使用一半的绳索。第三个选项与第二个选项有相同的问题，但至少不会在某个设定长度处破坏字符串。选项 4 将给出与我在大多数绳索示例图中看到的结果相似的结果，但在实施级别似乎是一场噩梦。

TL;DR：在文本编辑器中使用绳索时，理想情况下应该在按下一个键和该字符出现在树中之间发生什么？伪代码或只是高级解释在这里就足够了。

我知道 Notepad++ 使用 Gap Buffer，而 XI 编辑器使用 Rope。但我不知道 Visual Studio Code 背后的数据结构。

你知道 Visual Studio Code 中使用了哪种数据结构吗？

我正在使用绳索来存储大量（GB）的文本。文本可以长达数千万行。

绳索本身在任何位置插入都非常快，并且在特定位置也可以快速获取角色。

但是，我将如何获得特定行（\n对于这种情况）的开始位置？例如，我如何获得第 15 行的开始位置？我可以看到几个选项。

1. 没有任何额外的数据。每当你想说第 15 行时，你遍历 中的所有字符Rope，找到换行符，当你到达第 15 行时，你就停下来。
2. 将每行的start和存储在向量中。length因此，您将拥有Rope包含所有字符的数据结构，然后是一个单独的std::vector<line>. 该line结构将仅包含 2 个字段；start和length。Start 表示行在 内的起始位置Rope，length 是行的长度。要获得第 15 行的开始位置，只需执行lines[14].start

问题：

＃1是一种可怕的方式。它非常慢，因为您必须遍历所有角色。

#2 也不好。虽然找到一行的开始位置非常O(1)快O(N)（此外，存储这意味着对于您拥有的每一行，它会占用额外的 16 个字节的数据。（假设start和length每个是 8 个字节）。这意味着如果您有 13,000,000 行，它将占用 200MB 的额外内存。您可以使用链表，但这只会使访问变慢。

有没有更好、更有效的方法来存储行位置以便快速访问和插入？（最好O(log(n))用于插入和访问行）

我正在考虑使用RB-Tree ，BST更具体地说是RB-Tree，但我不完全确定这将如何工作。我看到了这样VSCode做，但是用 a代替。PieceTable

任何帮助将不胜感激。

编辑：

@interjay 提供的答案似乎不错，但是如果 CR 和 LF 在 2 个叶节点之间拆分，我将如何处理 CRLF？

我还注意到了ropey，它是一个 rust 库Rope。我想知道是否有类似的东西，但对于C++.

我一直在尝试使B+ Tree每个键都是相应子键的总和。然后叶子将包含一个字符串，其键将是字符串长度。我基本上是在尝试制作B+ Tree 绳索。

这就是我的意思（这棵树的顺序为 4）：

我可以看到的 1 个直接问题是键没有排序，我认为这是对B+ trees. （5、7、10 是，但这只是巧合）。但是，我不确定如何制作它以便对键进行排序，同时保持它的Rope类似性质（未排序）。

或者我什至需要对每个节点键进行排序？树的结构是否像这样有效，插入和搜索的最坏情况时间复杂度是否仍然是常规的B+ Tree？

我的另一个问题是关于插入。如果我在索引 11 处插入一个新的文本块“abc”，就在“n”之后（假设我没有realloc“n”缓冲区），那么我要做的就是：

0. 检测溢出
1. 将 3 和 2 带入另一个节点。（第一个节点中的 m / 2 个节点）
2. 将 1（即“n”）向上移动到根中。
3. 第二个节点将仅包含 3 (abc) 和 1 (g)（第二个节点中的 m / 2 个节点）

我感到困惑的部分是＃2。由于我无法将实际数据移动到非叶节点中，我该怎么办？

另外，我注意到我使用的树最多有 4 个键，最多也有 4 个孩子。但是，在常规B+ Tree中，您最多只能有 3 个键。这会影响什么吗？

任何帮助将不胜感激。