我正在尝试制作一个绳索数据结构。它是一种二叉树，即递归数据结构。
绳索的目的是分裂和连接应该很快，这意味着您避免复制整个绳索。
因此，例如，用户应该能够rope1 + rope2在〜对数时间内说出并期待结果。
但是，这会带来一个问题：
如果修改了一条绳索，它的父项也会间接修改。
因为我的目标是直接rope替换string，这是不可接受的。
我对此的解决方案是：每当对 a 进行任何更改时rope，我都会创建一个新节点，稍作更改，而旧节点保持不变。
从理论上讲，我认为这会很好。
但是，在实践中，它涉及（几乎？）字符串的每次修改的堆分配。
即使是一个字符的更改也会导致一个新的堆对象，这不仅本身很慢，而且还会显着降低内存局部性，对性能产生非常负面的影响。
我应该如何解决这个问题？
传统的方法是写时复制：为此，您需要重新计算每个分配的节点。
如果修改后的节点的引用计数为 1（没有其他人引用它），则不需要复制它。
这样做的实际问题是有用地将变异与非变异操作分开：
char& rope::operator[] (std::string::pos)
可能会改变引用的字符，但没有简单的方法可以强制选择 const 重载，而实际上它不会。这意味着您要么必须假设会发生突变，并可能触发不必要的复制，要么返回一些重载 char 转换和分配的代理。
这种方法被尝试用于 iirc 的早期实现std::string（其中字符串相当于单节点绳索），但失宠了；部分原因是变异问题，部分原因是如果您不得不担心多线程，COW 和所需的引用计数会变得越来越昂贵。
正如您所说，如果您的节点包含两种独立类型的状态，则绳索还有一个问题：它自己的字符串和对其子节点的引用（因为这会导致 refcount/child 引用突变传播到树上）。
相反，如果字符仅存储在叶节点上，并且您对非叶节点进行了完整复制（因此每个绳索都有自己的“目录结构”），您仍然避免复制字符，并且引用的共享状态很多更简单。
这会得到你想要的对数时间连接吗？也许不是：
它看起来更接近线性时间还是对数时间取决于增加引用计数与复制目录树的相对成本。
但是，如果没有这个，您将获得快速连接，但如果必须将 COW 操作向上传播到树上，任意字符访问可能（不可预测地）退化为对数时间。
我想，如果它适合您的用例，您可以实现移动连接：这可能会给出恒定时间的加法，并且您仍然可以避免额外的 COW 复杂性。
但是，在实践中，它涉及（几乎？）字符串的每次修改的堆分配。
如果你想避免频繁的堆分配性能问题，那么我建议为你的类使用一个内存池来分配一块内存，并且只需要在它已满时从操作系统请求新的分配，这应该很少发生. 然后，您可以优化对内存池的访问以分配小块数据类型char，例如 等。
Andrei Alexandrescu 在他的“Modern C++ Design”一书中有一个小块内存分配器的很好的例子。