on Wed Jul 06 2016, Haravikk <[email protected]> wrote: >> On 6 Jul 2016, at 03:39, Dave Abrahams via swift-evolution >> <[email protected]> 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 _______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
