removeObjectsAtIndexes for Swift arrays

Question

What is a Swift array equivalent to NSMutableArray's -removeObjectsAtIndexes:? Removing each index one by one doesn't work, as remaining indexes will shift after removing one index. What's an efficient way to implement this functionality?

Answer 1

I like a pure Swift solution, i.e. without resorting to NSIndexSet:

extension Array {
    mutating func removeAtIndexes (ixs:[Int]) -> () {
        for i in ixs.sorted(>) {
            self.removeAtIndex(i)
        }
    }
}

EDIT In Swift 4 that would be:

extension Array {
    mutating func remove (at ixs:[Int]) -> () {
        for i in ixs.sorted(by: >) {
            self.remove(at:i)
        }
    }
}

But years after I wrote that answer, the WWDC 2018 Embracing Algorithms video points out the flaw: it's O(n²), because remove(at:) itself has to loop through the array.

According to that video, Swift 4.2 removeAll(where:) is efficient because it uses half-stable partitioning. So we could write something like this:

extension Array {
    mutating func remove(at set:IndexSet) {
        var arr = Swift.Array(self.enumerated())
        arr.removeAll{set.contains($0.offset)}
        self = arr.map{$0.element}
    }
}

My tests show that despite the repeated contains, that's 100 times faster. However, @vadian's approach is 10 times faster than that, because he unrolls contains by ingeniously walking the index set at the same time he walks the array (using half-stable partitioning).