Swift 枚举器：如何实现空集合？

Question

我正在为我的数据模型实现一些自定义枚举器，例如

struct Land {
  // …
  let council: Council
  let size: Int
}

extension Collection<MyModel> {
  func lands(in council: Council, above size: Int) -> [Land] {
    guard isEmpty == false else {
      return []
    }
    filter { $0.council == council && $0.size > size }
  }
}

然后我想如果内置枚举器也通过检查集合是否为空来走捷径，那么我就不必这样做了。这不仅限于

filter

，而是所有一般的枚举器。例如，

find(where:)

的文档说它的复杂度为 O(n)，这意味着如果集合为空，则复杂度为 O(0)，但这到底意味着什么，它是跳过循环还是仍然启动循环但从一开始就完成？在调用枚举器之前防止空集合有什么好处吗？

Answer 1

任何

Collection

实现都可以按照自己喜欢的方式实现这些方法，只要它们正确。

您可以前往 Swift GitHub 存储库 查看每个内置集合的实现方式。

我将重点关注本答案中

Collection

和

Sequence

（

Collection

继承的）方法的默认实现。请参阅 CollectionAlgorithms.swift 和 SequenceAlgorithms.swift。

没有涉及迭代检查的默认实现

isEmpty

。在

Collection

方法中，迭代一般是这样实现的：

var i = self.startIndex
while i != self.endIndex {
  ...
  self.formIndex(after: &i)
}

如果集合为空，

startIndex

将等于

endIndex

。因此，循环不会运行。

对于

Sequence

方法，迭代

Sequence

的唯一方法是

makeIterator

并重复调用

next

。它总是某种形式：

var it = makeIterator()
while let e = it.next() {
  ...
}

请注意，

for

循环基本上是上述内容的语法糖。

next

隐式检查是否为空。如果没有元素，则返回 nil。因此，循环不会运行。另请注意，

Sequence

不需要

isEmpty

方法，因此这些方法不能以这种方式检查空性。

您是否将其归类为“跳过循环”或“仍然开始循环但从头开始完成”取决于您。就我而言，这些描述是等效的。