SE-0265: Offset-Based Access to Indices, Elements, and Slices

[Michael_Ilseman]

@jrose

• Because _reverseOffsetIndex(_:by:) is a new requirement, any Collections in existing binary frameworks will be stuck with the minimal default implementation, even if they are bidirectional or random-access collections. Binary frameworks will have to be recompiled to pick up the proper bidirectional implementation. (That is, the runtime will not do overload resolution to pick a default implementation for you.)
• The new performance characteristics of existing methods are only available on systems with an SE-0265-capable standard library. We should probably document that.

That’s an interesting point. I agree about documenting it somehow. @nnnnnnnn , what do you think the best convention would be? A note at the end of the doc providing a Complexity section for older OSes?

(note that the default implementation of _reverseOffsetIndex is still O(1) for random-access collections, as its implemented in terms of distance and index(_:offsetBy:))

How do you feel about the following phrasing, sticking it under “Effect on ABI stability”?

Collection types defined in previously-compiled binaries would use the default Collection implementation of _reverseOffsetIndex until recompiled, giving O(1) complexity if random-access, else O(n) (even if bidirectional).