[swift-evolution] [stdlib] Collection mutators availability inconsistent

[Max Moiseev]

Hi Louis,

I believe the difference is due to the performance guarantees. One can only efficiently implement `popFirst` and `removeFirst` on slices, where it’s just a matter of index manipulation. Removing the first element of a Collection is potentially an O(n) operation. Using `popFirst` in a loop in some algorithm would result in a quadratic complexity.

So the reason is: we only provide `popFirst` in a context where it is guaranteed to be O(1). Same applies to `popLast`, actually.. I think.

To reiterate what I mentioned in your pull request <https://github.com/apple/swift/pull/5333>:
> This case clearly identifies the flaw in the design of these methods, solving which might become a part of a follow-up to this proposal  <https://github.com/apple/swift-evolution/blob/master/proposals/0132-sequence-end-ops.md>one day.

Max

> On Oct 18, 2016, at 11:16 AM, Louis D'hauwe via swift-evolution <swift-evolution at swift.org> wrote:
> 
> Collections have mutating functions for removing the first and last element.
> One of these is popLast(), which will safely check if the collection is empty before popping the last element.
> 
> So calling popLast() is like doing:
> if !collection.isEmpty {
> 	collection.removeLast()
> }
> 
> There also exists a popFirst() function, but what I find inconsistent is that popFirst() is only available on ArraySlice.
> 
> Example:
> var collection = [1, 2, 3, 4]
> collection.removeFirst() // works fine
> collection.removeLast() // works fine
> let last = collection.popLast() // works fine
> let first = collection.popFirst() // Compile error: [Int] is not convertible to 'ArraySlice<Int>'
> 
> Is it intended that popLast() is available on collections, but popFirst() is not?
> 
> – Louis D'hauwe
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20161018/000a0a12/attachment.html>