[swift-evolution] Collection index complexity and data structures

[David Waite]

I noticed that the new Collection index(_:offsetBy:) <http://swiftdoc.org/v3.0/protocol/Collection/#comment-func-index_offsetby_> does not define that negative offsets require a BidirectionalCollection. It also declares that negative offsets must complete in O( | offset | ) time. This differs from other methods such as distance(from:to:) <http://swiftdoc.org/v3.0/protocol/Collection/#comment-func-distance-from_to_>which indicates start <= end if not a BidirectionalCollection

This would preclude some data structures from strictly implementing the Collection protocol, such as singly-linked lists.

Would it be appropriate to indicate instead that BidirectionalCollection defines the negative offset behavior and negative offset performance constraint?

-DW
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160624/2c041e41/attachment.html>