c++ - 无法在 C++ 中实现 "rope"数据结构

Question

我正在尝试制作 rope数据结构。它是一种二叉树，即递归数据结构。

绳索的目的是拆分和连接应该快速，这意味着您避免复制整个绳索。
因此，例如，用户应该能够说出 rope1 + rope2 并期望在~对数时间内得到结果。

但是，这带来了一个问题:
如果一个绳子被修改，它的父级也会被间接修改。
因为我的目标是让 rope 成为 string 的直接替代品，所以这是 Not Acceptable 。

我的解决方案是:每当绳索发生任何变化时，我都会创建一个新节点，其中轻微的变化，保留旧的不变。

理论上，我认为这会很有效。

但实际上，它涉及(几乎？)字符串的每次修改 的堆分配。
即使一个字符的更改也会导致一个新的堆对象，这不仅本身很慢，而且还会显着降低内存局部性，对性能产生非常负面的影响。

我应该如何解决这个问题？

Answer 1

传统的方法是写时复制:为此，您需要重新计算每个分配的节点。

如果修改后的节点的引用计数为 1(没有其他人引用它)，则不需要复制它。

这样做的实际问题是有效地分离变异操作和非变异操作:

    char& rope::operator[] (std::string::pos)

可能 改变引用的 char，但没有简单的方法来强制选择 const 重载，而它实际上不会。这意味着您要么必须假设会发生突变，并可能触发不必要的拷贝，要么返回一些重载 char 转换和赋值的代理。

这种方法曾在 std::string 的早期实现中尝试过(其中字符串相当于单节点绳索)iirc，但后来失宠了；部分原因是突变问题，部分原因是如果您不得不担心多线程，COW 和所需的重新计数变得越来越昂贵。

---

正如您所说，如果您的节点包含两种独立类型的状态，则绳索还有一个额外的问题:它自己的字符串和对其子节点的引用(因为这会导致引用计数/子引用突变向上传播树)。

如果相反，字符仅存储在叶节点上，并且您对非叶节点进行完整复制(因此每根绳子都有自己的“目录结构”)，您仍然可以避免复制字符和引用计数的共享状态要简单得多。

这是否得到您想要的对数时间串联？也许不是:

• 你必须复制所有的非叶子节点(并添加一个新的根)，这些节点的数量是叶子数量的log
• 你还必须递增叶引用计数，这是线性的

它是看起来更接近线性时间还是对数时间取决于增加引用计数与复制目录树的相对成本。

如果没有这个，您可以获得快速连接，但如果任意字符访问必须在树上传播 COW 操作，则它们可能(不可预测地)退化为对数时间。

我想，如果它适合您的用例，您可以实现移动串联:这可能会提供恒定时间加法，并且您仍然可以避免额外的 COW 复杂性。