Swift Collection underestimateCount usage

Question

I wonder, what is the use case for Collection underestimateCount? Documentation says that it has the same complexity as standard Collection count.

/// 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 describe when it should be used and for what reason.

Answer 1

underestimatedCount 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 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:

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.

Therefore, because of this default implementation, using a Collection's underestimatedCount directly is definitely less common than using a Sequence's, as Collection guarantees non-destructive iteration, and in most cases underestimatedCount will just return the count.

Although, of course, custom collection types could 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, which could potentially be useful.

Answer 2

(Since the duplicate target I've suggested is somewhat outdated)

In Swift 3, the method underestimateCount() has been replaced by the computed property underestimatedCount. We can have a look at the source code for the implementation of the latter for Collection:

  /// A value less than or equal to the number of elements in the collection.
  ///
  /// - Complexity: O(1) if the collection conforms to
  ///   `RandomAccessCollection`; otherwise, O(*n*), where *n* is the length
  ///   of the collection.
  public var underestimatedCount: Int {
    // TODO: swift-3-indexing-model - review the following
    return numericCast(count)
  }

  /// The number of elements in the collection.
  ///
  /// - Complexity: O(1) if the collection conforms to
  ///   `RandomAccessCollection`; otherwise, O(*n*), where *n* is the length
  ///   of the collection.
  public var count: IndexDistance {
    return distance(from: startIndex, to: endIndex)
  }

Its apparent that underestimatedCount simply makes use of count for types conforming to Collection (unless these types implements their own version of underestimatedCount).