Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[SR-7654] Default implementation of removeAll(where:) for RangeReplaceableCollection takes O(N) space #50195

Open
dabrahams opened this issue May 10, 2018 · 0 comments
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior.

Comments

@dabrahams
Copy link
Collaborator

Previous ID SR-7654
Radar None
Original Reporter @dabrahams
Type Bug
Additional Detail from JIRA
Votes 0
Component/s
Labels Bug
Assignee None
Priority Medium

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.

@swift-ci swift-ci transferred this issue from apple/swift-issues Apr 25, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior.
Projects
None yet
Development

No branches or pull requests

1 participant