[swift-evolution] Dropping Comparable requirement for indices

[Dave Abrahams]

on Wed Jul 06 2016, Haravikk <swift-evolution at swift.org> wrote:

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

There is no way, AFAIK, to implement important algorithms like rotate
binarySearch and several others, without having some representation of
position within a collection.

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

I don't know what you mean by “track,” here.  We don't track the
indices of an array.

-- 
Dave