[swift-evolution] [Pitch] remove(at: Set<Index>)

[Dmitri Gribenko]

On Sat, Jun 18, 2016 at 10:59 PM, Karl <razielim at gmail.com> wrote:
> What exactly are the guarantees for index safety across mutations? Both
> Collection and Indexable stop short of making any kind of guarantees about
> what happens to indexes after you mutate. For example, popFirst() has the
> potential to invalidate all stored indexes, but you wouldn’t know that if
> you were just working in terms of Collection.

https://github.com/apple/swift/blob/master/docs/IndexInvalidation.rst

Mutating a collection invalidates all indices.  Specific types and
protocols relax this:

- Replacing an element in a MutableCollection does not invalidate any indices.

- RangeReplaceableCollection only invalidates indices after the one
where the structural mutation happened.  For example,
replaceRange(a..<b, ...) invalidates "a" and all indices after it.

Collections in stdlib/private/StdlibCollectionUnittest/MinimalCollections.swift.gyb
check these rules.

> If we can guarantee tail-end removal is safe, a minimalist’s solution could
> be:
>
> extension RangeReplaceableCollection {
>
> mutating func remove<S:Sequence where S.Iterator.Element == Index>(at
> indexes: S) {
>
> for idx in indexes.sorted(isOrderedBefore: >) {
> remove(at: idx)
> }
> }
> }

Yes, this works, but it is O(n^2).  We can do better.

Dmitri

-- 
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr at gmail.com>*/