Implementing a Collection.removingIndices(_:)

Using Swift
41

This has been something I've been wanting to propose. I believe the best customization hook would be a replaceSubrange that returned the range of the replacement after the modification. In practice, the vast majority of RRCs can provide this and it would allow in-place batch mutations whether traversing forwards or backwards.

1 Like
42

Something has always bugged me about this solution, even as I was writing that post. A predicate means that the code has to test against every valid index before determining what to delete. The other versions of the method given around here use an explicit list of the elements they want gone, so the indexes of uninvolved elements are never tested. Those other methods can add a Hashable requirement to Index, or allow the targeted indexes to be listed in any order and/or have repeats, or all of the above.

We need a Sequence that can guarantee that it contains its element values exactly once, in increasing order, and exploit the already-required Comparable conformance instead of unnecessarily adding a Hashable one. I dusted off a desire to copy C++'s comparable-based associative containers and wrote a sorted-set type. The new requirement method to RangeReplacableCollection will take a SortedSet<Index> as its parameter, which any other sequence of indexes can convert to, and use the set to arrange how it will remove multiple discontinuous elements without losing track after the first block is removed.

43

Here's a sample default implementation:

extension RangeReplaceableCollection {

    /// Removes all the elements at the given indices.
    public mutating func removeAll(at positions: SortedSet<Index>) {
        var newSelf = Self()
        newSelf.reserveCapacity(Swift.max(0, count - positions.count))

        var start = startIndex
        for position in positions {
            guard start < endIndex else { break }

            newSelf.append(contentsOf: self[start..<position])
            start = index(after: position)
        }
        newSelf.append(contentsOf: self[start...])
        self = newSelf
    }

}

var s = "Thanks for the memories"
let vowels: Set<Character> = ["a", "e", "i", "o", "u"]
let si = s.indices.filter { vowels.contains(s[$0]) }
s.removeAll(at: SortedSet(si))

s will have the value of "Thnks fr th mmrs". The method should be a new customization point to allow optimized allocations when the type can internally track discontinuous removals.

44

Foundation.IndexSet provides that sorted-ness guarantee for Int, so you could implement this using offsets (edit: though you'll have to do some clever relative offsetting instead of starting from 0 to avoid N^2 traversal for non-random-access collections). But then you're depending on Foundation.

1 Like