on Sun Jun 19 2016, Haravikk <[email protected]> wrote: >> On 19 Jun 2016, at 11:12, Haravikk via swift-evolution >> <[email protected]> wrote: >> >> I think the following should work for the generic case, and is pretty >> similar: >> >> extension MutableCollection { >> public mutating func remove(indices: Set<Index>) { >> var index = self.startIndex >> self = self.filter { >> let result = indices.contains(index) >> self.formIndex(after: &index) >> return result >> } >> } >> } > > Apologies for the double-post but I’m honour bound to follow up that my > generic method is a load of nonsense at the moment; it’s missing some kind of > constructor (I don’t recall if there’s a common option that will satisfy > this), also, due to the way .filter {} currently works even in its lazy form > it can end up calling the filter closure more than once per item, so > advancing the index currently won’t work as expected (elements are skipped, > children murdered, it’s just the worst). > > So yeah, best option to do this right now is with a proper loop over > self.indices, but it still requires some kind constructor to build a new copy > of the correct type. > > For arrays this is a bit simpler as you *can* safely remove indices in > reverse order, since later indices cannot invalidate earlier ones, but this > is reliant on the array’s indices being integers (reasonable enough, but not > really correct in the strictest sense), so like so: > > extension Array { > public mutating func remove(indices: Set<Index>) { > for eachIndex in indices.sort(>) { // greater than > should give descending order > self.remove(at: eachIndex) > } > } > }
This is still an O(N^2) algorithm. You can do this in O(N) by taking Dmitri's approach. -- Dave _______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
