使鏈表符合集合協議

我正在查看此處的鏈接串列實作，它顯示了該類如何符合集合協議：

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)
    }
}

我有兩個問題：

1. 為什么元素必須符合Comparable？不同于firstIndex（作者：），這需要的要素是Equatable，我似乎無法找到蘋果檔案任何事情需要符合Comparable，甚至Equatable，對于像startIndex。
2. 這些標簽如何參考特定節點？我不太了解這個任意屬性tag和索引之間的關聯。

測驗

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)？

uj5u.com熱心網友回復：

根據您顯示的代碼：

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一致性無關，也不影響它。

2. 看起來LinkedListIndex.tag代表了串列中元素的索引，就像一個陣列索引：第一個元素（startIndex）的標簽為0，第二個元素的標簽為1，以此類推；endIndex（一旦超過串列中最后一個元素的索引）的索引為count

   您可以使用索引來遍歷tag串列以訪問特定元素。不過，這種迭代并不是絕對必要的，因為 aLinkedListIndex 還包含一個指向它應該在串列中參考的節點的指標，作為快捷方式。

更新附加問題：

index(after:) 如何知道 LinkedListIndex(node: node, tag: 50) 之后是哪個節點？

這是通過兩件事實作的：

1. 除了tag, LinkedListIndexvalues 還包含一個指向它們在原始串列中參考的節點的指標：

   public struct LinkedListIndex: Comparable { fileprivate let node: LinkedList.LinkedListNode? fileprivate let 標簽：Int }

   這是在創建索引時設定的：

   • LinkedList.startIndex
   • LinkedList.endIndex
   • LinkedList.index(after:)

2. 的實作LinkedList.index(after:)在其實作中使用此節點參考：

   public func index(after idx: Index) -> Index {
       return LinkedListIndex<T>(node: idx.node?.next, tag: idx.tag   1)
   }
   

   后面idx的索引是一個索引，它：

   • 點到節點后 idx.node，和
   • 有一個過去的標簽 idx.tag

節點和標簽之間沒有進一步的關聯：

• 在tag似乎是用來專門用于Comparable一致性的指標，以此來避免比較節點（例如，LinkedListIndex 信托，如果idx1.tag < idx2.tag再假定idx1.node來之前idx2.node在串列中，即使這是不是這樣的！），而
• node在下標和生成新索引時，這是唯一真正參考的內容

因為節點和標簽只是以這種方式非常松散地相關聯，所以此代碼對于不匹配并不是非常健壯（例如，如果我在按住 的同時編輯串列index，則索引tag可能已過時，具體取決于我執行的操作！）。

標籤：ios 迅速 数据结构 链表

上一篇：Swift/Alamofire5ResponseSerializer通用結構解碼

下一篇：如何使用類似于numpy切片的tf.gather