# Implementing a Collection.removingIndices(\_:)

**URL:** <https://forums.swift.org/t/implementing-a-collection-removingindices/27681>\
**Category:** Using Swift\
**Created:** [August 7, 2019, 6:06am UTC](https://forums.swift.org/t/implementing-a-collection-removingindices/27681 "2019-08-07T06:06:45Z")\
**Posts on this page:** 20\
**Page:** 2

<div class="post-metadata">

**Author:** ![dabrahams](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/dabrahams/32/9815_2.png) [@dabrahams](https://forums.swift.org/u/dabrahams)\
**Post date:** [August 13, 2019, 4:21am UTC](https://forums.swift.org/t/implementing-a-collection-removingindices/27681/21 "2019-08-13T04:21:58Z")

</div>

You can do this algorithm in place. It turns out that the classic stable partition algorithm only visits each element once, before it is moved, so you can partition the elements based on their indices. That's probably true of the simpler half-stable partition as well, but I haven't checked.

Actually it looks like @vadian may have posted this answer above.

---

<div class="post-metadata">

**Author:** ![dabrahams](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/dabrahams/32/9815_2.png) [@dabrahams](https://forums.swift.org/u/dabrahams)\
**Post date:** [August 13, 2019, 4:30am UTC](https://forums.swift.org/t/implementing-a-collection-removingindices/27681/22 "2019-08-13T04:30:50Z")

</div>

Aren't these all O(N²) algorithms?

---

<div class="post-metadata">

**Author:** ![TizianoCoroneo](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/tizianocoroneo/32/4398_2.png) [@TizianoCoroneo](https://forums.swift.org/u/TizianoCoroneo)\
**Post date:** [August 13, 2019, 7:52am UTC](https://forums.swift.org/t/implementing-a-collection-removingindices/27681/23 "2019-08-13T07:52:24Z")

</div>

Yes indeed, in fact all of them have big trouble dealing with arrays with more than 1000 elements.  
The only faster implementations are @nnnnnnnn version:

> **Iterative copying**
>
> ```swift
> 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
> }
> }
> 
> ```

and @vadian version:

> **It's all about partitions**
>
> ```swift
> 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...)
> }
> }
> 
> ```

@dabrahams the "Iterative copying" version is not O(n²), isn't it? If it is, then I don't understand how it is much faster than the other (bad) implementations.  
Thank you for your amazing WWDC presentation 👌

---

<div class="post-metadata">

**Author:** ![Nevin](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nevin/32/617_2.png) [@Nevin](https://forums.swift.org/u/Nevin)\
**Post date:** [August 13, 2019, 1:23pm UTC](https://forums.swift.org/t/implementing-a-collection-removingindices/27681/24 "2019-08-13T13:23:16Z")

</div>

> [@dabrahams](#):
>
> You can do this algorithm in place.

Does the constraint “`MutableCollection & RangeReplaceableCollection`” provide sufficient guarantees of index stability for this?

---

<div class="post-metadata">

**Author:** ![TizianoCoroneo](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/tizianocoroneo/32/4398_2.png) [@TizianoCoroneo](https://forums.swift.org/u/TizianoCoroneo)\
**Post date:** [August 13, 2019, 3:12pm UTC](https://forums.swift.org/t/implementing-a-collection-removingindices/27681/25 "2019-08-13T15:12:35Z")

</div>

Here's someone saying that the new method actually appears on the Standard Library documentation: [RangeReplaceableCollection - #10 by mattrips](https://forums.swift.org/t/rangereplaceablecollection/27839/10)

---

<div class="post-metadata">

**Author:** ![mattrips](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/mattrips/32/4079_2.png) [@mattrips](https://forums.swift.org/u/mattrips)\
**Post date:** [August 13, 2019, 4:01pm UTC](https://forums.swift.org/t/implementing-a-collection-removingindices/27681/26 "2019-08-13T16:01:24Z")

</div>

The specific addition that the documentation says to have been made is [`remove(atOffsets offsets: IndexSet)`](https://developer.apple.com/documentation/swift/rangereplaceablecollection/3349502-remove). There also is a new method: [`applying(_ difference: CollectionDifference<Self.Element>) -> Self?`](https://developer.apple.com/documentation/swift/rangereplaceablecollection/3200974-applying). These changes were made in Catalina Beta 5.

The question raised on the other [thread](https://forums.swift.org/t/rangereplaceablecollection/27839/9) is whether these changes actually are changes to the Standard Library, as the documentation indicates, or whether they might be extensions made within the `SwiftUI` framework.

---

<div class="post-metadata">

**Author:** ![suyashsrijan](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/suyashsrijan/32/5292_2.png) [@suyashsrijan](https://forums.swift.org/u/suyashsrijan)\
**Post date:** [August 13, 2019, 4:10pm UTC](https://forums.swift.org/t/implementing-a-collection-removingindices/27681/27 "2019-08-13T16:10:15Z")

</div>

I can't find the implementation of the method in the stdlib code though (unless its yet to be committed publicly).

---

<div class="post-metadata">

**Author:** ![bzamayo](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/bzamayo/32/764_2.png) [@bzamayo](https://forums.swift.org/u/bzamayo)\
**Post date:** [August 13, 2019, 4:12pm UTC](https://forums.swift.org/t/implementing-a-collection-removingindices/27681/28 "2019-08-13T16:12:33Z")

</div>

`remove(atOffsets:)` is implemented in `SwiftUI` as an extension. I don't know why the list page miscategorises it, but if you [click through](https://developer.apple.com/documentation/swift/rangereplaceablecollection/3349502-remove) and look at the sidebar, it says 'Framework: SwiftUI'.

`applying(_:)` is correctly grouped in the standard library domain and was introduced in the [collection diffing proposal](https://github.com/apple/swift-evolution/blob/master/proposals/0240-ordered-collection-diffing.md).

---

<div class="post-metadata">

**Author:** ![dlbuckley](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/dlbuckley/32/14986_2.png) [@dlbuckley](https://forums.swift.org/u/dlbuckley)\
**Post date:** [August 13, 2019, 4:23pm UTC](https://forums.swift.org/t/implementing-a-collection-removingindices/27681/29 "2019-08-13T16:23:52Z")

</div>

I started a proposal for this a while ago but didn't have the time to take it forwards. If anyone want to take it on you are quite welcome: [[Pre-pitch] removeAll(at:)](https://forums.swift.org/t/pre-pitch-removeall-at/24820)

---

<div class="post-metadata">

**Author:** ![mattrips](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/mattrips/32/4079_2.png) [@mattrips](https://forums.swift.org/u/mattrips)\
**Post date:** [August 13, 2019, 4:27pm UTC](https://forums.swift.org/t/implementing-a-collection-removingindices/27681/30 "2019-08-13T16:27:49Z")

</div>

Actually, with a little more digging, it appears the `remove(atOffsets:)` method is implemented in the `Foundation` framework.

And, as you indicate, `applying(_:)` is _anticipated_ to be included in the Standard Library, but has not yet been accepted.

I observe these bare facts, here. I'll post discussion in the other [thread](https://forums.swift.org/t/rangereplaceablecollection/27839/9).

---

<div class="post-metadata">

**Author:** ![bzamayo](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/bzamayo/32/764_2.png) [@bzamayo](https://forums.swift.org/u/bzamayo)\
**Post date:** [August 13, 2019, 4:29pm UTC](https://forums.swift.org/t/implementing-a-collection-removingindices/27681/31 "2019-08-13T16:29:10Z")

</div>

> [@mattrips](#):
>
> And, as you indicate, `applying(_:)` is _anticipated_ to be included in the Standard Library, but has not yet been accepted.

It was [accepted](https://forums.swift.org/t/accepted-with-modifications-se-0240-ordered-collection-diffing/20008).

---

<div class="post-metadata">

**Author:** ![nnnnnnnn](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nnnnnnnn/32/264_2.png) [@nnnnnnnn](https://forums.swift.org/u/nnnnnnnn)\
**Post date:** [August 13, 2019, 4:45pm UTC](https://forums.swift.org/t/implementing-a-collection-removingindices/27681/32 "2019-08-13T16:45:24Z")

</div>

> [@Nevin](#):
>
> Does the constraint “ `MutableCollection & RangeReplaceableCollection` ” provide sufficient guarantees of index stability for this?

When working with RRCs, you're constrained in what you can do — whenever you call a mutating RRC method you invalidate all existing indices (though some concrete collections, like array, won't have problems).

If you constrain to both MutableCollection and RRC, you can use swapAt (which doesn't invalidate indices) to rearrange as much as necessary, and then remove a single batch of elements at the end of your algorithm, once you don't need to access any other indices.

---

<div class="post-metadata">

**Author:** ![mattrips](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/mattrips/32/4079_2.png) [@mattrips](https://forums.swift.org/u/mattrips)\
**Post date:** [August 13, 2019, 4:47pm UTC](https://forums.swift.org/t/implementing-a-collection-removingindices/27681/33 "2019-08-13T16:47:02Z")

</div>

> [@mattrips](#):
>
> Actually, with a little more digging, it appears the `remove(atOffsets:)` method is implemented in the `Foundation` framework.
> 
> And, as you indicate, `applying(_:)` is _anticipated_ to be included in the Standard Library, but has not yet been accepted.

Right. Back in January it was accepted.

I've been referencing the most recent [thread](https://forums.swift.org/t/amendment-se-0240-ordered-collection-diffing/26084), which was a re-review on account of an amendment. The proposal itself is still listed as being in [Active Review (June 19 - 25 2019)](https://github.com/apple/swift-evolution/blob/master/proposals/0240-ordered-collection-diffing.md).

---

<div class="post-metadata">

**Author:** ![Lantua](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lantua/32/8868_2.png) [@Lantua](https://forums.swift.org/u/Lantua)\
**Post date:** [August 13, 2019, 4:47pm UTC](https://forums.swift.org/t/implementing-a-collection-removingindices/27681/34 "2019-08-13T16:47:38Z")

</div>

> [@nnnnnnnn](#):
>
> you can use swapAt (which doesn't invalidate indices)

Where is it guaranteed? I couldn't find it in the doc.

---

<div class="post-metadata">

**Author:** ![nnnnnnnn](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nnnnnnnn/32/264_2.png) [@nnnnnnnn](https://forums.swift.org/u/nnnnnnnn)\
**Post date:** [August 13, 2019, 4:50pm UTC](https://forums.swift.org/t/implementing-a-collection-removingindices/27681/35 "2019-08-13T16:50:48Z")

</div>

That guarantee belongs to the protocol, but it doesn't appear to be documented explicitly. The closest we get is in the Conforming to the MutableCollection Protocol section of the protocol docs, but even that doesn't spell out that other indices must also be unaffected by changes to the value at a particular position.

---

<div class="post-metadata">

**Author:** ![Lantua](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lantua/32/8868_2.png) [@Lantua](https://forums.swift.org/u/Lantua)\
**Post date:** [August 13, 2019, 4:55pm UTC](https://forums.swift.org/t/implementing-a-collection-removingindices/27681/36 "2019-08-13T16:55:53Z")

</div>

It could be heavily _implied_, but I think we should still be conservative on this.

---

<div class="post-metadata">

**Author:** ![nnnnnnnn](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nnnnnnnn/32/264_2.png) [@nnnnnnnn](https://forums.swift.org/u/nnnnnnnn)\
**Post date:** [August 13, 2019, 5:13pm UTC](https://forums.swift.org/t/implementing-a-collection-removingindices/27681/37 "2019-08-13T17:13:55Z")

</div>

We don't need to be conservative on this — it's core to the main function of the MutableCollection protocol. Without that guarantee, none of the in-place algorithms that MutableCollection is intended to enable (partition, reverse, sort, rotate, etc) would be possible. We just need improved docs!

---

<div class="post-metadata">

**Author:** ![Lantua](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/lantua/32/8868_2.png) [@Lantua](https://forums.swift.org/u/Lantua)\
**Post date:** [August 13, 2019, 5:20pm UTC](https://forums.swift.org/t/implementing-a-collection-removingindices/27681/38 "2019-08-13T17:20:22Z")

</div>

I agree, that the discrepancy should be resolved. Either to remove the assumption that appeared else where, or include it into the doc.

---

<div class="post-metadata">

**Author:** ![ben-cohen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ben-cohen/32/296_2.png) [@ben-cohen](https://forums.swift.org/u/ben-cohen)\
**Post date:** [August 13, 2019, 5:21pm UTC](https://forums.swift.org/t/implementing-a-collection-removingindices/27681/39 "2019-08-13T17:21:27Z")

</div>

The amendment was just to add an `inverse`. It doesn't affect the original proposal, which was accepted and implemented in 5.1.

---

<div class="post-metadata">

**Author:** ![CTMacUser](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ctmacuser/32/1802_2.png) [@CTMacUser](https://forums.swift.org/u/CTMacUser)\
**Post date:** [August 14, 2019, 1:41am UTC](https://forums.swift.org/t/implementing-a-collection-removingindices/27681/40 "2019-08-14T01:41:13Z")

</div>

Looking at this thread and the [[Pre-pitch] removeAll(at:)](https://forums.swift.org/t/pre-pitch-removeall-at/24820) thread, maybe we can generalize to:

```
protocol RangeReplaceableCollection {

    //...

    /// Removes all the elements whose indices satisfy the given predicate.
    ///
    /// Use this method to remove every element in a collection whose location
    /// meets a particular criteria. The order of the remaining elements is
    /// preserved. This example removes all the odd values from an
    /// array of numbers:
    ///
    /// var numbers = [5, 6, 7, 8, 9, 10, 11]
    /// numbers.removeAllAt(locations: { $0.isMultiple(of: 2) })
    /// // numbers == [6, 8, 10]
    ///
    /// - Parameter shouldBeRemoved: A closure that takes an index of the
    /// collection as its argument and returns a Boolean value indicating
    /// whether the corresponding element should be removed from the
    /// collection.
    ///
    /// - Complexity: O(*n*), where *n* is the length of the collection.
    mutating func removeAllAt(locations shouldBeRemoved: (Index) throws -> Bool) rethrows

}

```

Instead of using a `Set`, a hopefully sorted `Sequence`, or an arbitrary `Sequence`, we express the exclusion set as a predicate. Note that this is a customization point. There are two default implementations:

```
extension RangeReplaceableCollection {

    /// Removes all the elements whose indices satisfy the given predicate.
    ///
    /// Use this method to remove every element in a collection whose location
    /// meets a particular criteria. The order of the remaining elements is
    /// preserved. This example removes all the vowels from a string:
    ///
    /// var phrase = "The rain in Spain stays mainly in the plain."
    ///
    /// let vowels: Set<Character> = ["a", "e", "i", "o", "u"]
    /// let vowelIndices = Set(phrase.indices.lazy.filter({ vowels.contains(phrase[$0]) }))
    /// phrase.removeAllAt(locations: { vowelIndices.contains($0) })
    /// // phrase == "Th rn n Spn stys mnly n th pln."
    ///
    /// - Parameter shouldBeRemoved: A closure that takes an index of the
    /// collection as its argument and returns a Boolean value indicating
    /// whether the corresponding element should be removed from the
    /// collection.
    ///
    /// - Complexity: O(*n*), where *n* is the length of the collection.
    @inlinable public mutating func removeAllAt(locations shouldBeRemoved: (Self.Index) throws -> Bool) rethrows {
        var result = Self()
        result.reserveCapacity(count)
        for i in try indices.lazy.filter({ try !shouldBeRemoved($0) }) {
            result.append(self[i])
        }
        self = result
    }

}

extension RangeReplaceableCollection where Self: MutableCollection {

    /// Removes all the elements whose indices satisfy the given predicate.
    ///
    /// Use this method to remove every element in a collection whose location
    /// meets a particular criteria. The order of the remaining elements is
    /// preserved. This example removes all the odd values from an
    /// array of numbers:
    ///
    /// var numbers = [5, 6, 7, 8, 9, 10, 11]
    /// numbers.removeAllAt(locations: { $0.isMultiple(of: 2) })
    /// // numbers == [6, 8, 10]
    ///
    /// - Parameter shouldBeRemoved: A closure that takes an index of the
    /// collection as its argument and returns a Boolean value indicating
    /// whether the corresponding element should be removed from the
    /// collection.
    ///
    /// - Complexity: O(*n*), where *n* is the length of the collection.
    @inlinable public mutating func removeAllAt(locations shouldBeRemoved: (Self.Index) throws -> Bool) rethrows {
        var latest = startIndex
        for i in try indices.lazy.filter({ try !shouldBeRemoved($0) }) {
            self[latest] = self[i]
            formIndex(after: &latest)
        }
        removeSubrange(latest...)
    }

}

```

We need a customization point so collections that are not `MutableCollection` but (at least internally) don't necessarily invalidate indices upon (the first) removal, or can keep track of any shifts for at least one call, can do so in optimized implementations. This is helpful for collections that store elements as collections of collections, where removing elements in one segment doesn't disturb the internal indices of elements in other segments.

[Previous page](https://forums.swift.org/t/implementing-a-collection-removingindices/27681.md?page=1)

[Next page](https://forums.swift.org/t/implementing-a-collection-removingindices/27681.md?page=3)