dependencies: [
    .package(url: "https://github.com/ChimeHQ/RelativeCollections", branch: "main")
]

这里的所有结构都存储相对数据。这意味着给定值与之前的值存在某种依赖关系。如果你的数据符合此模型，则可以帮助提高某些操作的效率。

这与 Rope 非常相似。虽然这些结构只是稍微更通用一些，但使用的术语是相似的。数据分为两个组成部分：Value 和 Weight。Value 是独立的数据。Weight 是每个元素的贡献。完整的元素通过结合所有先前元素的 Weight 以及其独立的 Value 来重建。

为了对 Weight 进行操作，这些集合需要用户定义的函数来执行加法、减法以及查找初始值。但是，如果 Weight 符合 AdditiveArithmetic 协议，则可以推断出所有这些操作。

让我们看一些这种结构的实际应用。考虑一个处理文本并需要存储文档中每行信息的应用程序。你可能只是将每行的范围记录为 (start, length)。这是一个相对数据的绝佳示例！length 是独立值。只要编辑不发生在行内，length 就不会受到编辑的影响。相对值是 start - 它定义为所有先前长度的总和。

下面的 Metrics 类型存储有关文本行的信息。你可以在这里放入各种内容，例如行的高度或它是否包含任何多字节 UTF-8 数据。我们只记录前导和尾随空格的偏移量。

这个 Metrics 类型将是我们的独立 Value。行长（表示为 Int）将构成相对 Weight。这样做是可行的，因为行的绝对起始位置是所有先前行长的总和。

struct Metrics {
    let leadingWhitespace: Int
    let trailingWhitespace: Int
    
    init(_ leading: Int, trailing: Int) {
        self.leadingWhitespace = leading
        self.trailingWhitespace = trailing
    }
}

为了使其工作，我们还需要在 Weight 上定义一些核心操作。你可以通过 Configuration 属性来做到这一点。

let config = RelativeArray<Metrics, Int>.Configuration(
    initial: 0,
    add: { lengthA, lengthB in lengthA + lengthB },
    subtract: { lengthA, lengthB in lengthA - lengthB }
)

所有这些仪式允许使用非常抽象的 Weight 类型。但是，对于实现 AdditiveArithmetic 的类型，我们可以做得更好，Int 就是其中之一！在这种情况下，Configuration 具有预定义的行为，可以自动执行正确的操作。使你自己的自定义类型符合 AdditiveArithmetic 将使其以相同的方式工作。

这允许我们定义一个带有默认初始化程序的配置。而且，这也设置为 RelativeArray 的默认值，因此在这种情况下，我们可以完全避免处理配置。

   abc   
  defghi
 jk

我们可以通过使用正确的类型创建数组并附加一些 WeightedValue 类型来做到这一点。

let array = RelativeArray<Metrics, Int>()

array.append(
    WeightedValue(value: Metrics(3, 3), weight: 9)
)

array.append(
    WeightedValue(value: Metrics(2, 0), weight: 8)
)

array.append(
    WeightedValue(value: Metrics(1, 0), weight: 3)
)

现在我们的数据已加载，我们可以读取值。稍作努力，我们就可以重建我们想要的值。

let record = array[2]

let start = record.dependency // 17 (9 + 8)
let length = record.weight    // 3
let metrics = record.value    // Metrics(1, 0)

`RelativeArray`

RelativeArray 是最简单的类型。它在普通数组中存储 Value 和 Weight。就其本身而言，这种类型对于许多应用程序可能很方便。但是，它也用作更复杂结构的构建块。

RelativeArray 符合 Sequence 和 RandomAccessCollection。它支持 CoW，就像其他 Swift 集合一样。

`RelativeList`

这是一种像数组一样的位置可寻址类型。但是，在内部，它将数据存储在 B+Tree 中。这使你获得对数级的插入和删除性能。

但是，这是一种引用类型，不支持 CoW。我开始更深入地研究它，但是仅仅让它工作就已经足够困难了。

你可能想知道为什么我没有为此使用红黑树。红黑树很棒！它们可能是已知的最简单的自平衡树结构。而且，它们完全可以在这种相对数据的上下文中使用。但是，它们确实做出了一些权衡。与 B 树之类的东西相比，它们需要更多的指针。这增加了内存开销，并且不利于引用的局部性。这基本上就是 B 树最初被发明的原因。对于小的 N，它们与数组相比也不占优势。正如他们所说，N 通常很小。B+Tree 解决了这两个限制，当然，它在内部也复杂得多。

有一段时间，我对尝试为此使用跳跃列表感到兴奋，因为跳跃列表很酷。我很难理解如何做到这一点，而跳跃列表只会让它更难。

通常，当面对这类问题时，你必须进行测量。仔细地。但是，不严谨的优化的诱惑是强大的，我屈服了。我不知道这种结构是否真的比 RBTree 或标准 B 树更快。但我学到了很多。我希望有一天 Swift Collections 会提供合适的 B+Tree 或 Rope。

我很乐意听到你的消息！问题或拉取请求都很棒。 Matrix 和 Discord 都可以提供实时帮助，但我强烈倾向于以文档的形式回答。

我更喜欢协作，并且很乐意在你有一个类似项目的情况下找到合作方式。

我更喜欢使用制表符进行缩进以提高可访问性。但是，我宁愿你使用你想要的系统并创建一个 PR，也不愿因为空格而犹豫不决。

RelativeCollections

集成

概念

用法

结构

`RelativeArray`

`RelativeList`

关于数据结构的注释

相关项目

贡献与协作