ios – Swift 3和索引的自定义链接列表集合类型

在 Swift 3 Collection中,索引必须符合Comparable而不是Equable.

全文可以在这里阅读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)的复杂性要求.