Hi swift-evolution,
Another short proposal related to the Collection algorithms theme, this time for removing elements in-place from a collection. Online copy here: https://github.com/airspeedswift/swift-evolution/blob/1aac5593828941431d1805503865e7a2913d538b/proposals/NNNN-RemoveWhere.md Adding in-place removeAll to the Standard Library Proposal: SE-NNNN <file:///Users/ben_cohen/Documents/swift-evolution/proposals/NNNN-filename.md> Authors: Ben Cohen <https://github.com/airspeedswift> Review Manager: TBD Status: Awaiting review Introduction It is common to want to remove all occurrences of a certain element from a collection. This proposal is to add two in-place remove algorithms to the standard library, which will remove all entries in a collection in-place matching either an Equatable value, or match that a certain criteria. Motivation Removing all elements matching some criteria is a very common operation. However, it can be tricky to implement correctly and efficiently. The easiest way to achieve this effect in Swift 3 is to use filter and assign back, negating the thing you want to remove (because filter takes a closure of items to “keep”): var nums = [1,2,3,4,5] // remove odd elements nums = nums.filter { !isOdd($0) } In addition to readability concerns, this has two performance problems: fresh memory allocation, and a copy of all the elements in full even if none need to be removed. The alternative is to open-code a for loop. The simplest performant solution is the “shuffle-down” approach. While not especially complex, it is certainly non-trivial: if var i = nums.index(where: isOdd) { var j = i + 1 while j != nums.endIndex { let e = nums[j] if !isOdd(nums[j]) { nums[i] = nums[j] i += 1 } j += 1 } nums.removeSubrange(i..<nums.endIndex) } Possibilities for logic and performance errors abound. There are probably some in the above code. Additionally, this approach does not work for range-replaceable collections that are not mutable i.e. collections that can replace subranges, but can’t guarantee replacing a single element in constant time. String is the most important example of this, because its elements (graphemes) are variable width. Proposed solution Add the following methods to RangeReplaceableCollection: nums.removeAll(equalTo: 9) nums.removeAll(where: isOdd) The default implementation will use the protocol’s init() and append(_:) operations to implement a copy-based version. Collections which also conform to MutableCollection will get the more efficient “shuffle-down” implementation, but still require RangeReplaceableCollection as well because of the need to trim at the end. Collections which are range replaceable but not mutable (like String) will be able to implement their own version which makes use of their internal layout. Collections like Array may also implement more efficient versions using memory copying operations. Since Dictionary and Set would benefit from this functionality as well, but are not range-replaceable, they should be given concrete implementations for consistency. Detailed design Add the following to RangeReplaceableCollection: protocol RangeReplaceableCollection { /// Removes every element satisfying the given predicate from the collection. mutating func removeAll(where: (Iterator.Element) throws -> Bool) rethrows } extension RangeReplaceableCollection where Iterator.Element: Equatable { /// Removes every element equal to the given element from the collection. mutating func removeAll(equalTo element: Iterator.Element) } Source compatibility This change is purely additive so has no source compatibility consequences. Effect on ABI stability This change is purely additive so has no ABI stability consequences. Effect on API resilience This change is purely additive so has no API resilience consequences. Alternatives considered Regarding the name: remove instead of removeAll was considered. removeAll(equalTo: 5) seems clearer when seen alongside similar methods removeFirst(5) and remove(at: 5). In the case of remove(where:), the All in the basename is preserved for trailing closures. removeAll(where:) takes a closure with true for elements to remove. filter takes a closure with elements to keep. In both cases, true is the “active” case, so likely to be what the user wants without having to apply a negation. The naming of filter is unfortunately ambiguous as to whether it’s a removing or keeping operation, but re-considering that is outside the scope of this proposal.
_______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
