The removeAll(where:) in the standard library is pretty awesome but I find wanting to remove a set of indices quite often. (Like with UICollectionView). The best quick thing I could come up with is this:
Very nice! I suppose we could get super optimized by reserving the capacity of the into array by count - removeSet.count. (Assuming removeSet contains all hits.)
This is a great solution too. My first attempt looked (a little) like this but couldn't figure out the lazy trick. By dropping the requirement on Hashable you move the responsibility of performance to the caller and it does save an allocation.
I am interested in the rationale of why you changed the name from removingIndices to removingAllIndicies. I struggle a bit with the names so curious to know what your thinking was here.
An alternative approach would be to start with sorted indices (either by sorting the parameter or specifying the order as a precondition). The algorithm can then copy chunks of the source collection into the result without checking every index, which might be more efficient:
extension Collection {
func removingIndices<S: Sequence>(_ indicesToRemove: S) -> [Element]
where S.Element == Index
{
var result: [Element] = []
var low = startIndex
for high in indicesToRemove {
result.append(contentsOf: self[low..<high])
low = index(after: high)
}
result.append(contentsOf: self[low...])
return result
}
}
@jawbroken and @TizianoCoroneo your implementations work, but they're semantically distinct from removeAll(where:), whose important distinction from filter(_:) is that it operates in-place.
I was trying to make a mutating function like removeAll(where:) already present in the standard library, but I couldn't figure it out so I left the All word there just for consistency (and Indices instead of Indicies is indeed a spelling fix from Latin - it is the nominative plural of "index"). Thinking a little more about the name, I would probably go for this:
extension Collection {
func removingAll<Indices: Sequence>(
indices indicesToRemove: Indices
) -> [Element]
where Indices.Element == Index {
return zip(self.indices, self).lazy
.filter { !indicesToRemove.contains($0.0) }
.map { $0.1 }
}
}
@AlexanderM That's why we are calling these functions removing instead of remove, since we return the result instead of mutating in place.
I tried to write an implementation for the mutating function, but my current results have embarrassing performance
extension RangeReplaceableCollection {
mutating func removeAll<Indices: Sequence>(
indices indicesToRemove: Indices
)
where Indices.Element == Index {
// Not sure what to do here
}
}
I was testing the performance of various different ways of implementing this function, and I found out that the fastest implementation is this one... by a lot:
extension RangeReplaceableCollection {
// The implementation defined in `Collection` in my previous post takes 0.111 sec. This takes 0.001 sec! 🤯
mutating func removeAll<Indices: Sequence>(
indices indicesToRemove: Indices
)
where Indices.Element == Index {
let sortedIndices = indicesToRemove.sorted()
sortedIndices
.lazy
.reversed()
.forEach { self.remove(at: $0) }
}
}
EDIT: I just added @nnnnnnnn iterative version to the test benchmark and it is an order of magnitude faster than this last implementation. Nice job!
It's worth mentioning that indices expire when Collection mutates (even indices before the mutating index). It should work fine for most cases, but that should also be documented.
For Array specifically, you can reverse-sort the indices-to-remove, then rotate each in turn to the end (ie. rotate array[i...] to the left by 1), and finally drop the last n elements.
You’d have to implement rotate, but you can copy-and-paste it from the standard library algorithm prototypes file.
Be careful as well that the algorithm performs in quadratic time.
For larger collection, it'd probably become slow very quickly.
Here's another one.
extension RangeReplaceableCollection where Self: MutableCollection {
/// - Requires: `swapAt` does NOT invalidate indices.
mutating func removeAll<Indices: Sequence>(indices: Indices) where Indices.Element == Index {
var currentIndex = startIndex
// Uses `Set` if that proves faster.
var toSkip = indices.sorted().makeIterator()
var skipping = toSkip.next()
for index in self.indices {
if index == skipping {
skipping = toSkip.next()
} else {
swapAt(currentIndex, index)
formIndex(after: ¤tIndex)
}
}
removeSubrange(currentIndex..<endIndex)
}
}
Sure, but you don't have any other option for an implementation on Collection (or any of the standard libraries that inherit from Collection, like RangeReplaceableCollection) because any attempt at an in-place version will invalidate all the indices on the first modification.
so I left the 
: