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

Dave Abrahams dabrahams at apple.com
Tue Oct 18 15:41:04 CDT 2016


on Tue Oct 18 2016, Max Moiseev <swift-evolution at swift.org> wrote:

> 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. 

Well, and on deques, doubly-linked lists, and circular buffers.

> 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.

Right.

--
Dave



More information about the swift-evolution mailing list