4

我正在使用绳索来存储大量（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++.

4

1 回答 1

2

在每个rope节点（包括叶子节点和内部节点）中，除了保存该子树中的字符数外，还可以放入子树中包含的换行符的总数。

然后查找特定的换行符与查找包含特定字符索引的节点的工作方式完全相同。您将查看“换行数”字段而不是“字符数”字段。

所有绳索操作的工作方式基本相同。创建新的内部节点时，您只需添加其子节点的换行符数。所有操作的复杂性是相同的。

于 2021-03-31T22:12:47.933 回答