[swift-evolution] (Draft) Add last(where:) and lastIndex(where:) methods

[Dave Abrahams]

on Thu May 19 2016, Brent Royal-Gordon <brent-AT-architechies.com> wrote:

>> Why shouldn't this work with all Collections, with an optimized version
>> for BidirectionalCollections?
>
> Why don't we have `index(before:)` on non-BidirectionalCollections? It's not that you can't write it:
>
> 	func index(before index: Index) -> Index {
> 		let offset = distance(from: startIndex, to: index)
> 		return index(startIndex, offsetBy: offset - 1)
> 	}
>
> We don't do that because it would be so slow as to form an attractive
> nuisance. 

It's O(N) worst case no matter what you do.

> Similarly, we shouldn't provide operations which are going to
> repeatedly seek elements near the tail of the list unless we're using
> a type which can access that tail efficiently. `last` is one
> thing—it's only O(N). `lastIndex(of:)` is, I believe, O(n log n) in
> the case of an element that doesn't exist.

I can't imagine where your O(N log N) comes from in this case, but even
if it is the right complexity that wouldn't be a reason not to provide
the operation.  I learned last week there's an O(N log N) in-place
reverse() for ForwardCollections, and I think we ought to have it.  log
N is effectively a constant for most purposes.

>> I think we need to consider consistency of naming more carefully in this
>> area.  If we go this route, I want:
>> 
>>  x.firstIndex(of: 10)
>
> I think that's actually great, because it will separate the
> user-facing `index(of:)` and `index(where:)` from the stdlib-facing
> `index(after:)`, `index(before:)`, `index(_:offsetBy:)`, etc.

Yes.

-- 
-Dave