Swift Collection underestimateCount usage
collections, ios, swift
Solution
`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.
Problem
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.