KlimczakM KlimczakM - 1 month ago 11
iOS Question

Swift Collection underestimateCount usage

What is a use case for Collection

underestimateCount
. Documentation says that it has the same complexity as standard Collection count.

I've seen it's declaration:

/// Returns a value less than or equal to the number of elements in
/// `self`, *nondestructively*.
///
/// - Complexity: O(N).
public func underestimateCount() -> Int


But it doesn't tell me anything about when should I use it and for what reason.

Answer

underestimateCount is actually a requirement of the Sequence protocol, and has a default implementation that just returns 0:

public var underestimatedCount: Int {
  return 0
}

However, for sequences that provide their own implementation of underestimatedCount, this can be useful for logic that needs a lower bound limit of how long the sequence is, without having to iterate through it (remember that Sequence gives no guarantee of non-destructive iteration).

For example, the map(_:) method on Sequence (see its implementation here) uses underestimateCount in order to reserve an initial capacity for the resultant array:

  public func map<T>(
    _ transform: (Iterator.Element) throws -> T
  ) rethrows -> [T] {

    let initialCapacity = underestimatedCount
    var result = ContiguousArray<T>()
    result.reserveCapacity(initialCapacity) 

    // ...

This allows map(_:) to minimise the cost of repeatedly appending to the result, as an initial block of memory has (possibly) already been allocated for it (although its worth noting in any case that ContiguousArray has an exponential growth strategy that amortises the cost of appending).

However, in the case of a Collection, the default implementation of underestimateCount actually just returns the collection's count (see its implementation here):

public var underestimatedCount: Int {
    // TODO: swift-3-indexing-model - review the following
  return numericCast(count)
}

Which, will be an O(1) operation for collections that conform to RandomAccessCollection, O(n) otherwise.

Although, of course, custom collection types can provide their own implementation of underestimatedCount – giving a lower bound of how many elements they contain, in a possibly more efficient way than their count implementation.