对于Swift数组,removeObjectsAtIndexes

Question

什么是斯威夫特阵列相当于一个NSMutableArray的-removeObjectsAtIndexes:？逐个删除每个索引不起作用,因为删除一个索引后剩余的索引将会移位.什么是实现此功能的有效方法？

Answer 1

我喜欢纯粹的Swift解决方案,即不使用NSIndexSet:

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

编辑在Swift 4中将是:

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

但是在我写完这个答案的几年后,WWDC 2018 Embracing Algorithms视频指出了这个缺陷:它是O(n ²),因为remove(at:)它本身必须循环通过阵列.

根据该视频,Swift 4.2 removeAll(where:)是高效的,因为它使用半稳定分区.所以我们可以这样写:

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

我的测试显示,尽管重复contains,但速度要快100倍.然而,@ vadian的方法比这快10倍,因为他contains在走完阵列的同时巧妙地走了索引集(使用半稳定分区).

Answer 2

根据WWDC 2018 Session 223 - Embracing Algorithms,一种有效的解决方案是半稳定分区算法:

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

它只是通过交换元素将所有不在索引集中的元素移动到数组的末尾.半稳定意味着算法保留左分区的顺序但不关心右侧的顺序,因为无论如何都将移除元素.循环之后,变量i包含要删除的项的第一个索引.批量删除操作很便宜,因为不会移动/重建索引.

例如,如果您有一个数组

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

并且您希望删除索引处的元素,2并且4算法在while循环中执行以下步骤(索引的初始值j是要删除的第一个索引之后的索引):

• 索引3:在索引2和3→ 交换元素[0, 1, 3, 2, 4, 5, 6, 7]
• 指数4:没有变化
• 索引5:在索引3和5→ 交换元素[0, 1, 3, 5, 4, 2, 6, 7]
• 索引6:在索引4和6→ 交换元素[0, 1, 3, 5, 6, 2, 4, 7]

• 索引7:在索引5和7→ 交换元素[0, 1, 3, 5, 6, 7, 4, 2]

• 最后删除子范围内的元素 6...

Answer 3

针对Swift 2.0进行了更新:

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

使用forEach而不是map如果它发出不使用结果的警告(我认为Swift 2 beta 6)

编辑:超级通用懒人解决方案:

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

我找到了一个系统 api，但它位于适用于 iOS 13+ 的 SwiftUI 中。

Answer 5

我最终以这种方式这样做：

根据Apple关于的文档NSIndexSet，“索引集将索引存储为排序范围”。因此，我们可以NSIndexSet 向后枚举给定的值，并在每个索引处逐个删除数组中的元素，如下所示：

extension Array {

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

}

Answer 6

这是我目前使用的解决方案：

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