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

[Brent Royal-Gordon]

>> 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'm imagining an implementation something like this:

	func lastIndex(of value: Element) -> Index? {
		let count = self.count
		
		for endOffset in 0..<count {
			let offset = count - endOffset - 1
			let i = index(startIndex, offsetBy: offset)
			
			if self[i] == value {
				return i
			}
		}
		
		return nil
	}

`index(_:offsetBy:)` is O(N) for a ForwardCollection, and `offset` gets smaller as you execute the loop, so I *believe* this ends up being O(N log N). I was never that good at big-O notation, though, so I could be wrong about that. What I can say is that it would be O(N^2) if not for the decreasing size of `offset`, so it's smaller than that.

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

If you guys think it's okay, I'm not going to argue.

-- 
Brent Royal-Gordon
Architechies