swift - 泛型类型之间的循环依赖(例如 CollectionType 及其索引/生成器)

Question

给定一个 struct基于泛型 CollectionType ……

struct MyCollection<Element>: CollectionType, MyProtocol {
    typealias Index = MyIndex<MyCollection>

    subscript(i: Index) -> Element { … }

    func generate() -> IndexingGenerator<MyCollection> {
        return IndexingGenerator(self)
    }
}

…如何定义 Index为它……

struct MyIndex<Collection: MyProtocol>: BidirectionalIndexType {

    func predecessor() -> MyIndex { … }
    func successor() -> MyIndex { … }
}

…没有引入死亡依赖循环？

MyIndex 的通用性质是必要的，因为:

1. 它应该适用于任何类型的 MyProtocol .
2. MyProtocol引用文献 Self因此只能用作类型约束。

如果有前向声明(在 Objective-C 中)，我将只是^{[原文如此!]}为MyIndex<MyCollection> 添加一个到我的MyCollection<…> .唉，没有这样的事情。

---

一个可能的具体用例是二叉树，例如:

indirect enum BinaryTree<Element>: CollectionType, BinaryTreeType {
    typealias Index = BinaryTreeIndex<BinaryTree>

    case Nil
    case Node(BinaryTree, Element, BinaryTree)

    subscript(i: Index) -> Element { … }
}

这需要基于堆栈的 Index :

struct BinaryTreeIndex<BinaryTree: BinaryTreeType>: BidirectionalIndexType {
    let stack: [BinaryTree]

    func predecessor() -> BinaryTreeIndex { … }
    func successor() -> BinaryTreeIndex { … }
}

---

一个人不能(还？)嵌套 struct s inside generic struct Swift 中的 s。
否则我就移动BinaryTreeIndex<…>里面BinaryTree<…> .

此外，我更希望有一个通用的 BinaryTreeIndex ,
然后可以与任何类型的 BinaryTreeType 一起使用.

Answer 1

您不能在结构中嵌套结构，因为它们是值类型。它们不是指向对象的指针，而是将它们的属性保存在变量中。想想如果一个结构包含自己，它的内存布局会是什么样子？

前向声明在 Objective-C 中有效，因为它们随后被用作指针。这就是将 indirect 关键字添加到枚举的原因 - 它告诉编译器通过指针添加一个间接级别。

理论上可以将相同的关键字添加到结构中，但这没有多大意义。不过，您可以使用类框代替手动执行 indirect 的操作:

// turns any type T into a reference type
final class Box<T> {
    let unbox: T
    init(_ x: T) { unbox = x }
}

你可以使用它来封装一个结构来创建，例如，一个链表:

struct ListNode<T> {
    var box: Box<(element: T, next: ListNode<T>)>?

    func cons(x: T) -> ListNode<T> {
        return ListNode(node: Box(element: x, next: self))
    }

    init() { box = nil }
    init(node: Box<(element: T, next: ListNode<T>)>?)
    { box = node }
}

let nodes = ListNode().cons(1).cons(2).cons(3)
nodes.box?.unbox.element // first element
nodes.box?.unbox.next.box?.unbox.element // second element

您可以将此节点直接转变为一个集合，方法是使其符合ForwardIndexType 和CollectionType，但这不是一个好办法主意。

例如，他们需要非常不同的==实现:

• 索引需要知道同一列表中的两个索引是否在同一位置。它不需要元素符合 Equatable。

• 集合需要比较两个不同的集合，看它们是否持有相同的元素。它确实需要元素符合 Equatable 即:

  func == <T where T: Equatable>(lhs: List<T>, rhs: List<T>) -> Bool {
      // once the List conforms to at least SequenceType:
      return lhs.elementsEqual(rhs)
  }
  

最好将其包装在两种特定类型中。这是“免费的”——包装器没有开销，只是帮助您更轻松地构建正确的行为:

struct ListIndex<T>: ForwardIndexType {
    let node: ListNode<T>

    func successor() -> ListIndex<T> {
        guard let next = node.box?.unbox.next
            else { fatalError("attempt to advance past end") }
        return ListIndex(node: next)
    }
}

func == <T>(lhs: ListIndex<T>, rhs: ListIndex<T>) -> Bool {
    switch (lhs.node.box, rhs.node.box) {
    case (nil,nil): return true
    case (_?,nil),(nil,_?): return false
    case let (x,y): return x === y
    }
}

struct List<T>: CollectionType {
    typealias Index = ListIndex<T>
    var startIndex: Index
    var endIndex: Index { return ListIndex(node: ListNode()) }
    subscript(idx: Index) -> T {
        guard let element = idx.node.box?.unbox.element
            else { fatalError("index out of bounds") }
        return element
    }
}

(无需实现generate()——在 2.0 中通过实现CollectionType 即可“免费”获得索引生成器)

您现在拥有一个功能齐全的集合:

// in practice you would add methods to List such as
// conforming to ArrayLiteralConvertible or init from 
// another sequence
let list = List(startIndex: ListIndex(node: nodes))

list.first  // 3
for x in list { print(x) }  // prints 3 2 1

现在所有这些代码看起来都非常恶心，原因有二。

一个是因为 box 挡住了路，而 indirect 更好，因为编译器会在后台为您整理好所有内容。但它正在做类似的事情。

另一个是结构不是解决这个问题的好方法。枚举要好得多。事实上，代码真的使用了一个枚举——这就是 Optional 的含义。只是代替 nil(即 Optional.None)，链表末尾有一个 End 情况会更好。这就是我们使用它的目的。

有关更多此类内容，您可以查看 these posts .