Swift enumerators: how is it implemented for empty collection?

Question

I'm implementing a few custom enumerators for my data model, e.g.

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

Then I thought if the built-in enumerators also takes a shortcut by checking if the collection is empty, then I don't have to do it. And this isn't limited to filter, but all the enumerators in general. For example, the doc for find(where:) says it has complexity of O(n), which mean O(0) if the collection is empty, but what does that mean exactly, does it skip the loop or still start the loop but finish at the very beginning? Is there any benefit for guarding agains empty collection before calling the enumerator?

Answer 1

Any Collection implementation can implement these methods however they like, as long as they are correct.

You can go to the Swift GitHub repository to see how each of the built-in collections are implemented.

I will focus on the default implementations of the Collection and Sequence (which Collection inherits) methods in this answer. See CollectionAlgorithms.swift and SequenceAlgorithms.swift.

None of the default implementations that involve iteration checks isEmpty. In the Collection methods, iteration is generally implemented like this:

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

If the collection is empty, startIndex will be equal to endIndex. Consequently, the loop does not run.

For the Sequence methods, the only way available to iterate through a Sequence is to makeIterator and repeatedly call next. It is always some form of:

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

Note that a for loop is basically syntactic sugar for something like the above.

next implicitly checks for emptiness. If there is no elements, it returns nil. Consequently, the loop does not run. Also note that Sequence does not require an isEmpty method, so these methods cannot check emptiness this way.

Whether you classify this as "skip the loop" or "still start the loop but finish at the very beginning" is up to you. Those descriptions are equivalent as far as I'm concerned.