[SR-7654] Default implementation of removeAll(where:) for RangeReplaceableCollection takes O(N) space #50195
Labels
bug
A deviation from expected or documented behavior. Also: expected but undesirable behavior.
Additional Detail from JIRA
md5: abe3daeb315a3a7369aa989489262905
Issue Description:
The space bound on removeAll(where🙂 isn't documented, which is supposed to mean it's an O(1) space operation—we would document any O(N) space operations whose space bound was not already an implication of the signature. The fact that there are no known models of `RangeReplaceableCollection` that cannot perform this operation in O(1) space is a good indication that O(N) space is not actually the right bound for this operation. The cure is to remove the default implementation from `RangeReplaceableCollection` and only provide a default for `RangeReplaceableCollection & MutableCollection`. I don't believe an O(1) space default implementation that only depends on `RangeReplaceableCollection` exists.
The text was updated successfully, but these errors were encountered: