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).

Answer 2

According to WWDC 2018 Session 223 – Embracing Algorithms an efficient solution is the half stable partition algorithm:

extension RangeReplaceableCollection where Self: MutableCollection, Index == Int {

    mutating func remove(at indexes : IndexSet) {
        guard var i = indexes.first, i < count else { return }
        var j = index(after: i)
        var k = indexes.integerGreaterThan(i) ?? endIndex
        while j != endIndex {
            if k != j { swapAt(i, j); formIndex(after: &i) }
            else { k = indexes.integerGreaterThan(k) ?? endIndex }
            formIndex(after: &j)
        }
        removeSubrange(i...)
    }
}

It moves all elements which are not in the index set to the end of the array just by swapping the elements. Half stable means the algorithm preserves the order of the left partition but doesn't care about the order of the right side as the elements will be removed anyway. After the loop the variable i contains the first index of the items to be removed. The batch remove operation is inexpensive because no indexes will be shifted/rebuilt.

---

For example if you have an array

[0, 1, 2, 3, 4, 5, 6, 7]

and you want to remove the elements at index 2 and 4 the algorithm performs the following steps in the while loop (the initial value of the index j is the index after the first index to be removed):

• Index 3: Swap elements at index 2 and 3 → [0, 1, 3, 2, 4, 5, 6, 7]
• Index 4: No change
• Index 5: Swap elements at index 3 and 5 → [0, 1, 3, 5, 4, 2, 6, 7]
• Index 6: Swap elements at index 4 and 6 → [0, 1, 3, 5, 6, 2, 4, 7]

• Index 7: Swap elements at index 5 and 7 → [0, 1, 3, 5, 6, 7, 4, 2]

• Finally remove the elements at subrange 6...

---

Answer 3

Updated for Swift 2.0:

extension Array {
    mutating func removeAtIndices(incs: [Int]) {
        incs.sort(>).map { removeAtIndex($0) }
    }
}

Use forEach instead of map if it gives a warning that the result isn't used (Since Swift 2 beta 6 I think)

EDIT: Super generic lazy solution:

extension RangeReplaceableCollectionType where Index : Comparable {
    mutating func removeAtIndices<S : SequenceType where S.Generator.Element == Index>(indices: S) {
        indices.sort().lazy.reverse().forEach{ removeAtIndex($0) }
    }
}