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
_______________________________________________
swift-evolution mailing list
[email protected]
https://lists.swift.org/mailman/listinfo/swift-evolution
