使链表符合 Collection 协议

Question

我正在查看来自 here, and it shows how the class conforms to the Collection protocol 的链表实现：

extension LinkedList: Collection {
    
    public typealias Index = LinkedListIndex<T>

    public var startIndex: Index {
        get {
            return LinkedListIndex<T>(node: head, tag: 0)
        }
    }
    
    public var endIndex: Index {
        get {
            if let h = self.head {
                return LinkedListIndex<T>(node: h, tag: count)
            } else {
                return LinkedListIndex<T>(node: nil, tag: startIndex.tag)
            }
        }
    }
    
    public subscript(position: Index) -> T {
        get {
            return position.node!.value
        }
    }
    
    public func index(after idx: Index) -> Index {
        return LinkedListIndex<T>(node: idx.node?.next, tag: idx.tag + 1)
    }
}

为了符合Collection协议，代码提供了三个东西：startIndex/endIndex，只读下标获取一个元素，index(after:).

为了使这成为可能，代码还提供了LinkedListIndex，它是相关链表的包装对象，以使其符合Comparable:

public struct LinkedListIndex<T>: Comparable {
    fileprivate let node: LinkedList<T>.LinkedListNode<T>?
    fileprivate let tag: Int
    
    public static func==<T>(lhs: LinkedListIndex<T>, rhs: LinkedListIndex<T>) -> Bool {
        return (lhs.tag == rhs.tag)
    }
    
    public static func< <T>(lhs: LinkedListIndex<T>, rhs: LinkedListIndex<T>) -> Bool {
        return (lhs.tag < rhs.tag)
    }
}

我有两个问题：

为什么元素必须符合Comparable？与 firstIndex(of:) 不同，后者要求元素为 Equatable，我似乎无法在 Apple 文档中找到任何关于需要符合 Comparable 甚至 Equatable 的内容，对于像 startIndex.
这些标签如何引用特定节点？我不太理解这个任意属性 tag 和 index.

测试

final class LinkListTest: XCTestCase {
    func test_linkedList() {
        let linkedList = LinkedList<Int>()
        for i in stride(from: 0, to: 100, by: 10) {
            linkedList.append(i)
        }
        
        let startIndex = linkedList.startIndex // startIndex has a tag of 0 because that's how it was instantiated
        let expectedStartIndex = LinkedListIndex<Int>(node: linkedList.head, tag: 0)
        XCTAssertEqual(startIndex, expectedStartIndex)
        
        let endIndex = linkedList.endIndex // endIndex also has a tag of the count because that's how it was instantiated
        let expectedEndIndex = LinkedListIndex<Int>(node: linkedList.last, tag: 10)
        XCTAssertEqual(endIndex, expectedEndIndex)
        
        let node = LinkedList.Node(value: 50)
        let testIndex = linkedList.index(after: LinkedListIndex<Int>(node: node, tag: 50))
        print("testIndex", testIndex) // LinkedListIndex<Int>(node: nil, tag: 51)
    }
}

没有迭代遍历每个节点并将其与 LinkedListIndex 关联，也就是说节点 C 的标签为 3，D 的标签为 4。index(after:) 如何知道哪个节点来了在 LinkedListIndex<Int>(node: node, tag: 50)?

之后

Answer 1

根据您显示的代码：

不是链表元素是Comparable，而是索引。 Collection 对其元素没有 Comparable 要求，但确实要求其索引具有可比性，以便它们可以合理排序：

public protocol Collection: Sequence {
  // FIXME: ideally this would be in MigrationSupport.swift, but it needs
  // to be on the protocol instead of as an extension
  @available(*, deprecated/*, obsoleted: 5.0*/, message: "all index distances are now of type Int")
  typealias IndexDistance = Int  

  // FIXME: Associated type inference requires this.
  override associatedtype Element

  /// A type that represents a position in the collection.
  ///
  /// Valid indices consist of the position of every element and a
  /// "past the end" position that's not valid for use as a subscript
  /// argument.
  associatedtype Index: Comparable

  // ...
}

对索引的这一要求使得一次遍历 Collection 一个索引成为可能，并且知道您相对于 startIndex 和 endIndex.

还要注意语法

public struct LinkedListIndex<T>: Comparable

不会使 LinkedList Comparable 本身，并且只声明 LinkedListIndex 是 Comparable。请注意，它不引用原始列表本身，而是保留一个节点以在 LinkedList 本身内进行恒定时间访问：但此实现细节与 Comparable 一致性无关，也与 Comparable 一致性无关它会影响它。

看来LinkedListIndex.tag表示元素在列表中的索引，像数组索引一样：第一个元素（startIndex）的标签为0，第二个元素的标签为1，依此类推； endIndex（索引一次过去列表中的最后一个元素）的索引为 count

您可以使用索引在列表中迭代 tag 次以访问特定元素。不过，这种迭代并不是绝对必要的，因为 LinkedListIndex 还包含指向它应该在列表中引用的节点的指针，作为快捷方式。

更新补充问题：

How does index(after:) know which node comes after LinkedListIndex(node: node, tag: 50)?

这是通过两件事实现的：

除了 tag，LinkedListIndex 值还包含指向它们在原始列表中引用的节点的指针：

public struct LinkedListIndex: Comparable { fileprivate 让节点：LinkedList.LinkedListNode？ fileprivate 让标签：Int }

这是在创建索引时设置的：
- LinkedList.startIndex
- LinkedList.endIndex
- LinkedList.index(after:)
LinkedList.index(after:) 的实现在其实现中使用了这个节点引用：
```
public func index(after idx: Index) -> Index {
    return LinkedListIndex<T>(node: idx.node?.next, tag: idx.tag + 1)
}
```
idx后面的索引是一个索引：
- 指向节点afteridx.node，and
- 有一个标签过去 idx.tag

节点和标签之间没有进一步的关联：

tag 似乎 排他性地 用于索引 Comparable 一致性，作为一种避免必须比较节点的方法（例如，LinkedListIndex 相信如果 idx1.tag < idx2.tag 那么可能 idx1.node 在列表中出现在 idx2.node 之前，即使事实并非如此！），而
node 是订阅和生成新索引时唯一真正参考的东西

因为节点和标签只是以这种方式非常松散地相关，所以这段代码在防止不匹配方面并不是非常健壮（例如，如果我编辑列表而你按住 index，索引的 tag 可能已过时，具体取决于我执行的操作！）。

使链表符合 Collection 协议

Conforming Linked List to the Collection protocol

linked-list

ios

data-structures

swift