如何在常量時間內返回下標？

Question

作爲每Swift Documentation符合Collection協議時：

類型符合類別預期提供startIndex和endIndex的屬性和下標獲得的元件O（1）的操作。

下標如何在常量時間內返回？它不需要遍歷集合，直到正確的索引，然後返回該值嗎？

這是我使用符合Collection LinkedList的：

indirect enum LinkedList<T> { 
    case value(element: T, next: LinkedList<T>) 
    case end 
} 

extension LinkedList: Sequence { 
    func makeIterator() -> LinkedListIterator<T> { 
     return LinkedListIterator(current: self) 
    } 
    var underestimatedCount: Int { 
     var count = 0 
     for _ in self { 
      count += 1 
     } 
     return count 
    } 
} 

struct LinkedListIterator<T>: IteratorProtocol { 
    var current: LinkedList<T> 
    mutating func next() -> T? { 
     switch current { 
     case let .value(element, next): 
      current = next 
      return element 
     case .end: 
      return nil 
     } 
    } 
} 

這裏是這是我真正符合協議：

extension LinkedList: Collection { 

    typealias Index = Int 
    typealias Element = T 

    var startIndex: Index { 
     return 0 
    } 
    var endIndex: Index { 
     return underestimatedCount 
    } 
    func index(after i: Index) -> Index { 
     return (i < endIndex) ? i + 1 : endIndex 
    } 
    subscript (position: Index) -> Element { 
     precondition(position < endIndex && position >= startIndex) 
     var iterator = makeIterator() 
     for i in 0 ..< position { 
      iterator.next() 
      if i + 1 == position { 
       return iterator.next()! 
      } 
     } 
     var zero = makeIterator() 
     return zero.next()! 
    } 

} 

let test = LinkedList<Int>.value(element: 2, next: LinkedList<Int>.value(element: 4, next: LinkedList<Int>.value(element: 7, next: LinkedList<Int>.value(element: 9, next: LinkedList<Int>.end)))) 

Answer 1

收集的Index不必須是Int。一種可能的方法 是使用具有參考到相應的 元素的定製索引類型。但是，這要求列表節點是類的實例。

這是我想出來的東西。它可能可以改進， 但希望證明這個想法。

class ListNode存儲 的元件和一個指針到下一個節點，另外，越來越 整數ordinal，其被用來製作struct ListIndex 採用Comparable協議。

struct ListIndex包含對列表節點的引用，或nil 對於endIndex。

struct LinkedListCollection<T>: Collection { 

    class ListNode { 
     let element: T 
     let next: ListNode? 
     let ordinal: Int 

     init(element: T, next: ListNode?, ordinal: Int) { 
      self.element = element 
      self.next = next 
      self.ordinal = ordinal 
     } 

     // Create ListNode as the head of a linked list with elements from an iterator. 
     convenience init?<I: IteratorProtocol>(it: inout I, ordinal: Int = 0) where I.Element == T { 
      if let el = it.next() { 
       self.init(element: el, next: ListNode(it: &it, ordinal: ordinal + 1), ordinal: ordinal) 
      } else { 
       return nil 
      } 
     } 
    } 

    struct ListIndex: Comparable { 
     let node: ListNode? 

     static func <(lhs: ListIndex, rhs: ListIndex) -> Bool { 
      // Compare indices according to the ordinal of the referenced 
      // node. `nil` (corresponding to `endIndex`) is ordered last. 

      switch (lhs.node?.ordinal, rhs.node?.ordinal) { 
      case let (r?, l?): 
       return r < l 
      case (_?, nil): 
       return true 
      default: 
       return false 
      } 
     } 

     static func ==(lhs: ListIndex, rhs: ListIndex) -> Bool { 
      return lhs.node?.ordinal == rhs.node?.ordinal 
     } 
    } 

    let startIndex: ListIndex 
    let endIndex: ListIndex 

    // Create collection as a linked list from the given elements. 
    init<S: Sequence>(elements: S) where S.Iterator.Element == T { 
     var it = elements.makeIterator() 
     startIndex = ListIndex(node: ListNode(it: &it)) 
     endIndex = ListIndex(node: nil) 
    } 

    func index(after i: ListIndex) -> ListIndex { 
     guard let next = i.node?.next else { 
      return endIndex 
     } 
     return ListIndex(node: next) 
    } 

    subscript (position: ListIndex) -> T { 
     guard let node = position.node else { 
      fatalError("index out of bounds") 
     } 
     return node.element 
    } 
} 

用法示例：

let coll = LinkedListCollection(elements: [1, 1, 2, 3, 5, 8, 13]) 
for idx in coll.indices { 
    print(coll[idx]) 
}