在Swift 3中,Collection索引必须符合Comparable而不是Equatable.
全文可以在这里阅读swift-evolution/0065.
这是一个相关的引用:
一般的索引可以与一个或两个整数的是有效地从一个数据结构的根编码路径元件来表示.由于人们可以自由选择"路径"的编码,我们认为可以选择它以使指数具有廉价可比性.已经为所有执行标准库所需的索引,和其他几个人,同时研究这种变化我们调查的情况.
在我的自定义链表集合的实现中,节点(指向后继节点)是不透明的索引类型.但是,给定两个实例,不可能判断一个是否先于另一个实例,而不会冒着遍历链的重要部分的风险.
我很好奇,你如何实现Comparable具有O(1)复杂性的链表索引？
我目前唯一的想法是以某种方式计算步骤,同时推进索引,将其作为属性存储在索引类型中,然后比较这些值.
此解决方案的严重缺点是,在变更集合时,索引必须无效.虽然这对于数组来说似乎是合理的,但我不想打破链表有的巨大好处 - 它们不会使未更改节点的索引无效.
编辑: 它可以以两个额外的整数为代价来完成,作为集合属性,假设单个链表实现前插入,前删除和后添加.无论如何,任何干涉中间都会打破O(1)复杂性要求.
这是我的看法。
a) 我向我的自定义类型引入了一个私有整数类型属性Index：depth。
b) 我向集合引入了两个私有整数类型属性：startDepth和endDepth，对于空列表，这两个属性都默认为零。
startDepth.startDepth.endDepth.因此，所有指数startIndex..<endIndex都有一个反映整数范围startDepth..<endDepth。
startIndexc) 每当集合通过或提供索引时，endIndex它将从集合继承其相应的深度值。当要求集合通过调用来推进索引时，index(_ after:)我将简单地Index用递增的深度值（depth += 1）初始化一个新实例。
符合Comparable归结为将左侧深度值与右侧深度值进行比较。
请注意，因为我也从两侧扩展了整数范围，所以中间索引的所有深度值保持不变（因此不会失效）。
结论：
以内存占用量小幅增加以及很少的整数增量和减量为代价换取了O(1)索引比较的好处。我预计索引的生命周期会很短，并且集合的数量相对较少。
如果有人有更好的解决方案，我很乐意看看！
| 归档时间： |
|
| 查看次数： |
485 次 |
| 最近记录： |