c++ - 绳索数据结构和线

Question

我正在使用 Rope存储大量(GB)的文本。文本可以有数千万行长。
绳索本身在任何位置插入都非常快，并且在特定位置也可以快速获取角色。
但是，我如何获得特定行(在这种情况下为 \n)的开始位置？ 例如，我如何获得第 15 行开始的位置？我可以看到几个选项。

不要有任何额外的数据。每当你想说第 15 行时，你就遍历 Rope 中的所有字符。 ，找到换行符，当你到达第 15 个换行符时，你就停止了。

存储 start和 length vector 中的每一行。所以你会有你的 Rope包含所有字符的数据结构，然后是单独的 std::vector<line> . line结构将只包含 2 个字段； start和 length . Start 表示该行在 Rope 内的起始位置，长度是线的长度。要获得第 15 行开始的位置，只需执行 lines[14].start

问题 :
#1 是一种可怕的方式来做到这一点。它非常慢，因为您必须遍历所有角色。
#2 也不好。尽管获取一行开始的位置非常快( O(1) )，但每次插入一行时，您都必须移动它前面的所有行，即 O(N) .此外，存储这意味着对于您拥有的每一行，它会占用额外的 16 字节数据。 (假设 start 和 length 各为 8 个字节)。这意味着如果您有 13,000,000 行，它将占用 200MB 的额外内存。您可以使用链表，但这只会使访问速度变慢。
有没有更好更有效的方法来存储行位置以便快速访问和插入？ (最好是 O(log(n)) 用于插入和访问线路)
我正在考虑使用 BST ，更具体地说是 RB-Tree ，但我不完全确定这将如何工作。我看到了 VSCode做 this但有一个 PieceTable反而。
任何帮助将不胜感激。
编辑 :
@interjay 提供的答案似乎不错，但是如果 CR 和 LF 拆分为 2 个叶节点，我将如何处理 CRLF？
我也注意到 ropey ，这是 Rope 的 Rust 库.我想知道是否有类似的东西，但对于 C++ .

Answer 1

在每个绳节点(叶子节点和内部节点)中，除了保存该子树中的字符数外，还可以放置子树中包含的换行符总数。
然后查找特定的换行符与查找包含特定字符索引的节点的工作方式完全相同。您会查看“换行数”字段而不是“字符数”字段。
所有绳索操作的工作原理大致相同。创建新的内部节点时，您只需要添加其子节点的换行数。所有操作的复杂度都是一样的。