全文可以在这里阅读swift-evolution/0065.
这是一个相关报价：
Usually an index can be represented with one or two Ints that
efficiently encode the path to the element from the root of a data
structure. Since one is free to choose the encoding of the “path”,we
think it is possible to choose it in such a way that indices are
cheaply comparable. That has been the case for all of the indices
required to implement the standard library,and a few others we
investigated while researching this change.
在我实现一个自定义链表集合中,一个节点(指向后继)是不透明的索引类型.然而,给定两个实例,不可能判断一个是否在另一个之前,而不会冒险遍历链的重要部分.
我很好奇,你将如何为具有O(1)复杂性的链表索引实现Comparable？
我目前唯一的想法是在推进索引时以某种方式计数步骤,将其作为属性存储在索引类型中,然后比较这些值.
解决方案的严重缺点是,当变体收集时,索引必须无效.虽然这对于数组来说似乎是合理的,但我不想破坏链接列表的巨大好处 – 它们不会使未更改的节点的索引无效.
编辑：
假设单链表实现前插入,前删除和后附加,可以以两个额外的整数代替收集属性来完成.无论如何,中间的任何干扰都会打破O(1)的复杂性要求.
解决方法
a)我引入了一个私有整数类型属性到我的自定义索引类型：depth.
b)我向集合引入了两个私有整数类型的属性：startDepth和endDepth,它们都为空列表默认为零.
>每个前插入减少startDepth.
>每个前端删除增加startDepth.
>每个后附加递增endDepth.
因此所有索引startIndex ..< endIndex具有反射整数范围startDepth ..< endDepth. c)每当收集通过startIndex或endIndex引发索引时,它将从集合继承其相应的深度值.当通过调用索引(_ after :)要求收集提前索引时,我将简单地使用递增的深度值(depth = 1)初始化一个新的Index实例. 符合可比性,将左侧的深度值与右侧的比较进行比较. 请注意,因为我扩展了双方的整数范围,所以中间索引的所有深度值都保持不变(因此不会失效). 结论： O(1)指数比较的交易收益是以内存占用量小幅增加和少量整数增量和减量为代价的.我期望指数寿命短,收藏数量相对较少. 如果有人有更好的解决方案,我很乐意看看它！
