Rope 实施概述

SGI 的 STL 版本中包含的 Rope 容器类型大致基于施乐雪松环境中的 Rope 或 C “cord”，如 Boehm、Atkinson 和 Plass 在《Rope：字符串的替代方案》中描述的，Software Practice and Experience 25，12（1995 年 12 月），第 1315-1330 页。

Rope 表示为指向_Rope_RopeRep结构的指针，该结构表示一个树节点。每个树节点对应一段 Rope。虽然我们称之为“树节点”，但这样一段 Rope 可以在不同的 Rope 之间共享，如果相应的子串重复出现，甚至可以在同一个 Rope 中被重用。因此，Rope 实际上表示为有向无环图。尽管如此，我们仍将继续称其为树，因为它既是通常情况，也是更直观的理解方式。

每个树节点包含一个 size 字段，给出 Rope 段的长度，一个 depth 字段，指定以该节点为根的树的深度（或高度），一个布尔字段，表示子树是否已平衡，以及一个标签字段，表示_Rope_RopeRep的四个变体或子类中的哪一个用于表示列表（平衡位实际上仅对串联树节点有效，见下文）。

可以使用虚函数和/或 RTTI 来代替标签字段。我们选择不沿该途径进行，因为标签字段可以比 vtable 指针小得多，而且在这种情况下，基于标签的代码可能也更快。

的 4 个子类_Rope_RopeRep是

(_Rope_RopeLeaf）包含字符串字符的叶子。较短的 Rope 通常表示为这一个节点。在标准字符类型的情况下，实际的字符数组是NULL- 终止的，以允许快速生成等效的 C 字符串。
(_Rope_RopeConcatenation）串联节点。这些节点有两个子节点left 和right。它们表示由left 和right 子树表示的两个字符串的串联。较长的两个 Rope 的串联通常分配一个新串联节点，引用要串联的两个 Rope。
(_Rope_RopeFunction）函数节点。这些节点包含一个指向函数对象的指针，该函数对象可用于计算字符串的各个部分。此功能使得可以操纵懒惰计算的 Rope，即在需要这些部分时才计算出来。例如，可以将文件作为 Rope 来处理，而无需实际读入整个文件。因此，文本编辑器可以将甚至正在编辑的 100 MB 的文件表示为 Rope，使用标准 Rope 操作来更新它，同时仍然只占用极少量内存。
(_Rope_RopeSubstring) 子串节点。这些节点包含一个指向基本绳树节点的指针和该绳中一个起始位置。它们表示基本绳的子串。这些节点仅在表示昂贵至无法显式计算的绳子子串时才生成。基本字段永远不指向连接树节点。如果将子串操作应用于极其巨大的叶节点（可通过将非常长的 C 字符串转换为绳子构建）或表示很长字符串的功能节点，那么它将生成一个子串节点。子串节点还包含一个指向执行适当字符提取的功能对象的指针。它们是函数节点的子类，许多操作仅将它们视作函数节点。绝大部分使用绳子的情况都不会生成任何子串节点。然而，对于使用函数节点来延迟评估字符串的应用程序，它们必不可少。

只有连接节点才有非零的深度字段。由于我们对绳索深度强制规定了一个静态最大值，因此深度字段有保证能放入一个字节。

引用计数和同步

绳子实现可以用两种不同的方法编译。通常情况下，将不会定义 __GC 。在这种情况下，每个树节点也会包含一个引用计数字段。这会追踪引用该树节点的绳变量、连接节点或子串节点的数量。（我们稍后会看到，还会包括来自某些迭代器的引用。）当树节点的引用计数变为零时，树节点会被释放，并且任何子树的引用计数相应地递减。

在某些情况下，引用计数还会用于允许就地更新绳索。如果从绳索根节点 R 到持有特定字符的叶节点 L 的路径上的所有树节点的引用计数均为 1，那么 L 只在 R 中出现一次，不会出现在任何其他绳索中。因此，可以通过就地更新 L 来安全地更新 R。

如果通过已定义__GC编译绳子实现，它会假定存在一个底层垃圾回收器，且不可访问的树节点会自动回收。在这种情况下，必须使用合适的垃圾回收分配器对绳索进行实例化，并且不保留任何引用计数。因此，上述针对就地更新的优化也不会实现。由于即使非破坏性更新也只会复制绳子的一部分，并且由于许多绳子客户端将它们纯用作不可变字符串，所以这通常不会造成严重的损失。但对于某些应用程序而言可能并非如此。

本节的剩余部分假设未定义 __GC，且使用了引用计数。

由于不同线程可以并发地复制、更新或销毁不同绳索共享的绳索节点，因此必须以原子方式更新引用计数。这是实现执行的唯一显式同步，因为引用计数是潜在共享数据结构中唯一会被更新的部分。

引用计数更新所需的同步可能会占据绳索操作所需时间的很大一部分。无论何时可用原子添加操作，都应根据原子添加操作实现引用计数更新。很重要，引用计数递减操作不仅要以原子方式递减计数，还必须作为原子操作的一部分返回结果。如果在操作的原子部分之外执行零测试，那么相同的树节点可能会被释放两次。

在 Irix 和 win32 平台上，当前实现使用原子添加操作维护引用计数。还提供了基于 PThread 互斥的一个更通用的实现。但对于广泛使用绳索的应用程序，它不太可能提供最佳性能。

分配器使用

绳索实现可以使用标准一致的分配器（如果编译器允许）或 SGI 样式简化分配器。在前一种情况下，如果给定分配器类型的分配器实例是不同的，那么分配器实例将存储在每个绳索树节点以及绳索本身中。用不同分配器实例构建的绳索进行连接是非法的。

选择此表示法是因为它使实现相对干净，并且无实例的情况相当高效。在绳索中仅存储分配器实例的替代方案会为许多内部函数添加额外的分配器参数。对于没有不同实例的分配器类型来说，消除这种开销很困难。

基本算法和绳索平衡

连接通常通过分配一个新的连接节点并让它引用连接操作的两个参数来实现。因此，在大多数情况下，其执行时间与字符串长度无关。

将由单个叶组成的短绳连接到绳索右边的特殊情况得到特殊处理，该绳索要么是叶，要么是连接节点，其右子代是叶。在这种情况下，如果所讨论的叶足够短，我们可能会分配一个新叶来保存这两个叶的合并内容，或者在正确的情况下，甚至就地更新左操作数。为了允许破坏性更新，保存叶字符的实际数组以 8 为增量增长。

例如，绳索“abcedefghigklmnopqrstuvwxy”可能连接到“z”，如下图所示：

特殊处理此种情况确保了通过重复地将短字符串连接到右边创建的绳索将由最小大小的叶子构成，因此可以有效地进行储存和处理。对同一位置重复插入字符时会有类似的效果。

虽然连接操作非常有效，且与树的形状无关，但一些其他操作（例如获取第i个字符）如果表示绳索的树大约平衡，则会更有效。可以通过明确调用balance成员函数或者隐式作为连接操作的结果对绳索进行重新平衡。当深度有溢出危险时，或者绳索同时超过较小的深度阈值（当前为 20）并低于最小长度（当前为 1000），则会隐式重新平衡绳索。

重新平衡操作按上面引用的论文中描述的那样进行。该操作是非破坏性的；以前与其他绳索共享的重新平衡部分在该操作后不再共享。在对绳索进行平衡时，所有深度足够小以其长度而不会进行进一步平衡操作的连接节点中都会设置平衡位。带有已设置平衡位的树节点不会由进一步的平衡操作检查。因此，平衡操作倾向于不重新平衡同一子字符串。

尽管如此，重新平衡的最坏情况成本在字符串中是线性的。但是，观察到的行为是重新平衡通常仅消耗一小部分的运行时间。事实上，通过重复连接构建长度为N的绳索的所有自然方式都需要在 N 中线性总时间。违反此规则是可以的，但并不好用，设计连接顺序。

子字符串操作根据表示绳索根的树节点的不同而执行。该操作是递归的

对于叶子节点，我们返回一个带有子字符串的叶子节点，或者如果太长，我们返回一个下标节点。
对于连接节点，我们返回左和右子树的适当子字符串的连接。如果我们发现需要零长度的子字符串，我们就停止。类似地，当适当的时候，我们只需返回指向整个绳索的指针。
对于子字符串节点，我们返回一个短叶子节点或一个新的子字符串节点，参考从中获取原始子字符串的绳索。因此，我们不建立嵌套的子字符串节点。
任何其他函数节点基本上都作为叶子处理。

注意，此过程需要与绳索深度成正比的时间，并且不直接依赖于长度。该算法仅复制子字符串开头和结尾处的叶子节点部分，并沿着从根到子字符串任一末尾的路径建立新的连接节点。子字符串内部可以保持与原始绳索共享。

迭代器

正常生成的迭代器begin()和end()操作生成 const_iterators，即不允许更新基本绳索的迭代器。这样的迭代器基本上包含三类信息

关联迭代器的绳索根节点的指针。此指针未包含在参考计数中，如果修改或销毁基本绳索，Const_iterators 将变为无效。（在垃圾回收的情况下，它们将保持有效，并继续引用原始的修改前绳索。）
绳索内的位置。
用于加快访问接近当前位置的绳索部分的缓存信息。

我们维护迭代器中的两类缓存信息

保存包围当前字符位置的字符的连续存储块的限制以及该块中的当前偏移量。仅通过访问缓存的这部分即可解析大多数迭代器引用。引用的存储块可以是绳索表示中的叶子的一部分，也可以是对迭代器本身保留的小块字符。当迭代器引用由函数节点表示的绳索部分时，将使用后者。
迭代器当前引用的根节点到叶子节点或函数节点路径上的绳索底部几个节点。这用于跨节点边界快速增量或递减迭代器。我们不缓存整个路径，因为那样会使绳索迭代器变得非常大。

此实现与 C“cord”程序包中使用的实现有很大不同。我们不会在迭代器中为从根节点到当前节点的完整路径预留空间。此更改是为了适应假设小迭代器可以按值廉价传递的 STL 代码。我们尝试通过提供迭代器赋值操作进一步帮助此代码，除非初始化了迭代器赋值操作的缓存部分，否则此操作不会复制它。

迭代器中的字符缓冲区是必需的，因为没有其他地方可以缓存为函数节点的评估返回的字符。（使用垃圾回收器时，这是一个小问题，因为在函数对象中维护这样的缓存非常有效。如果没有垃圾回收器，这会要求对缓存访问使用锁，这通常是不可接受的。）

可变迭代器主要的优点在于，它们还包含指向绳本身的指针（即指向树节点指针的指针），因而可用于执行更新，并且，绳根指针包含在引用计数中。在这种情况下，绳根指针是多余的，但可以用它来检测绳中的变更，以便使迭代器中的缓存信息失效。当且仅当绳本身不再指向与迭代器中的绳根指针相同的节点时，绳才已改变。迭代器包含在引用计数中的事实确保了根节点不会被丢弃和重用。它还能够防止破坏性更新绳，而迭代器必须保持有效。