Swift Collection underestimateCount usage
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.
(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
).