[SR-6693] Collection.underestimatedCount shouldn't call .count when the latter isn't O(1).

[swift-ci]

Previous ID	SR-6693
Radar	None
Original Reporter	CTMacUser (JIRA User)
Type	Bug

Additional Detail from JIRA

| | | |------------------|-----------------| |Votes | 0 | |Component/s | Standard Library | |Labels | Bug | |Assignee | @airspeedswift | |Priority | Medium | md5: 1c211f9ba3face77d56f58149370eaa0

Issue Description:

Browsing the Collection source code at Apple's GitHub site, I noticed that the default implementation of Collection.underestimatedCount always forwards to .count. The "count" method is O👎 except when it's O(1) for random-access collections. Meanwhile, Sequence.underestimatedCount is supposed to be O(1).

So .underestimatedCount should forward to .count only for RandomAccessCollection. The wimpier, traversal-wise, Collection types should forward to .isEmpty instead. That keeps all Collection.underestimatedCount variants at O(1). Using .isEmpty limits the results of .underestimatedCount to 0 or 1, but that's OK since it's an under-estimate.

[belkadan]

O👎 / O(n) strikes again!

[xwu]

The documentation has already been updated to reflect actual practice by Thomas Di Meco in PR#13111.

[swift-ci]

Comment by Daryle Walker (JIRA)

I know having .underestimatedCount blindly forward to .count is current practice; I’m also saying keeping it that way is wrong. In old versions of Swift, was it possible to specialize on RandomAccessCollection over the others? If not, maybe declaring Collection.underestimatedCount as O👎 was a retroactive justification. We’re not limited by that now, and we have an alternative (using .isEmpty) to retain O(1). As-is, there’s no advantage to using .underestimatedCount over .count, not even at least speed.

[xwu]

Changing behavior now presents the possibility of silently changing user code in very difficult-to-debug ways. I would be strongly opposed to such an action.