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