[swift-evolution] Dropping Comparable requirement for indices

Haravikk swift-evolution at haravikk.me
Wed Jul 6 15:49:08 CDT 2016

> On 6 Jul 2016, at 03:39, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
> For example, with
> Comparable indices, you can't build a linked list that supports
> restructuring (e.g. insert, delete, splice) in O(1) without invalidating
> indices... not even an unsafe linked list with reference semantics.

I think the question is why you need to retain indices in these cases?

When it comes to these operations I wonder if we might want to investigate something like a mutating iterator; you might still use an index to jump to an initial position, but then use .insert(), .remove() etc. methods of the iterator to perform modification without the need to track indices at all. This is essentially how you want to edit trees anyway, as indexing them isn't especially pretty, as it avoids the need to track the indices at all for these operations, and many common cases should work well when done as part of an iterator in this way.

More information about the swift-evolution mailing list