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

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 2

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

Answer 4

I found a system api, but it's in SwiftUI available for iOS 13+.

Answer 5

I ended up doing it this way:

According to Apple's documentation on NSIndexSet, "index sets store indexes as sorted ranges". So we could enumerate over the given NSIndexSet backwards and remove the element from the array at each index one by one, like so:

extension Array {

  mutating func removeAtIndexes(indexes: NSIndexSet) {
    for var i = indexes.lastIndex; i != NSNotFound; i = indexes.indexLessThanIndex(i) {
      self.removeAtIndex(i)
    }
  }

}

Answer 6

Another expansion on Ethan's answer (trimmed down from what I have in my own framework):

extension Array {
    // Code taken from https://stackoverflow.com/a/26174259/1975001
    // Further adapted to work with Swift 2.2
    /// Removes objects at indexes that are in the specified `NSIndexSet`.
    /// - parameter indexes: the index set containing the indexes of objects that will be removed
    public mutating func removeAtIndexes(indexes: NSIndexSet) {
        for i in indexes.reverse() {
            self.removeAtIndex(i)
        }
    }
}

This version uses NSIndexSet's SequenceType extension provided by Swift's Foundation bridge.

edit: Also, newer versions of Swift (Don't remember which one added it) have a struct type called IndexSet, which can be bridged to/from NSIndexSet. And can be reverse()d like NSIndexSet.

Answer 7

To complete Ethan's answer, C-loop styles will be deprecated in Swift 3.0. Here's then a Swift 3.0 compatible answer:

mutating func removeAtIndexes(indexes: NSIndexSet) {
    var i = indexes.lastIndex
    while i != NSNotFound {
        self.removeAtIndex(i)
        i = indexes.indexLessThanIndex(i)
    }
}

Answer 8

I needed this for working with a NSTableview. This is what I use.

extension Array{
mutating func removeElementsAtIndexes(indexset:NSIndexSet){
    self = self.enumerate().filter({!indexset.containsIndex($0.index)}).map({$0.element})
    }
}

Answer 9

Swift 4 attempt

extension Array {

    mutating func removeAtIndexes(indexes: IndexSet) {
        var i:Index? = indexes.last
        while i != nil {
            self.remove(at: i!)
            i = indexes.integerLessThan(i!)
        }
    }
}

Answer 10

I used Swift's filter function:

func removeMusicListAtIndexes(idxSet: NSIndexSet) {
    if idxSet.containsIndex(selectedMusic) {
        selectedMusic = -1;
    }
    musicList = musicList.filter({
        var idx = find(self.musicList, $0)
        // If a value isn't in the index, it isn't being removed
        return !idxSet.containsIndex(idx!)
        })
}

Answer 11

Based upon Kent's solution but updated for Swift 3

extension Array {
    mutating func remove(indices: IndexSet) {
        self = self.enumerated().filter { !indices.contains($0.offset) }.map { $0.element }
    }
}

Answer 12

I have not tested this, but I would bet that a non-mutating version is faster if it copies contiguous subranges. Something like:

extension Array {
        public func removing(indices indicesToRemove: IndexSet) -> Self {
            guard let lastIndex = indicesToRemove.last else {
                return self
            }

            assert(lastIndex <= (self.count - 1), message: "Index set contains out of bounds indices")

            var result = Self()
            result.reserveCapacity(self.count - indicesToRemove.count)

            let indicesToKeep = IndexSet(self.indices).subtracting(indicesToRemove)
            let rangesToKeep = indicesToKeep.rangeView

            rangesToKeep.forEach { (range) in
                result.append(contentsOf: self[range])
            }

            return result
        }
}

Answer 13

one way is:

var arrayB = arrayA.removeAtIndex(5)

Another way is:

var arr = ["I", "Love", "Life"]
let slice = arr[1..<2]
println(slice)
//[Love]

Answer 14

Here is the solution I currently use:

extension Array {
    mutating func removeObjectAtIndexes(indexes: [Int]) {
        var indexSet = NSMutableIndexSet()

        for index in indexes {
            indexSet.addIndex(index)
        }

        indexSet.enumerateIndexesWithOptions(.Reverse) {
            self.removeAtIndex($0.0)
            return
        }
    }

    mutating func removeObjectAtIndexes(indexes: Int...) {
        removeObjectAtIndexes(indexes)
    }
}