RFC: Deque: should it have an opaque index?

I don't think so -- in Array's case, startIndex is the constant 0, and it's perfectly fine to save it out and keep reusing it, even after removing the element that was in the location it originally addressed. (As long as there are enough elements remaining, of course.) Deque works the same way, and I think all RandomAccessCollections should do the same.

I expect the code sample to print 2. It would be surprising if anything else happened!

Indices represent positions in the collection; they aren't just addressing a particular element. (E.g., consider that MutableCollection's subscript setter is required not to invalidate any index, even though it changes the element that corresponds to one of them. One major problem with RangeReplaceableCollection is that it allows its mutations to invalidate indices, without providing any way to keep your position in the collection -- RRC mutations ought to all return fresh new indices around the subrange that they modified.)

Now in theory we could say that Deque's indices should address specific slots in the storage buffer, so popping the first element would increment the startIndex (wrapping to zero if necessary). However:

  1. This would violate the substitutability requirement(*) of Equatable. Two Deques that compare the same could have different indices, so they wouldn't be substitutable with each other.

    Not that Equatable's substitutability requirement is anything other than a vague preference in practice. It certainly doesn't have a precise formal definition, and we aren't taking it very seriously, even in the stdlib -- e.g., Set and Dictionary are flagrantly violating it when it comes to indices (or element ordering), and the world has not ended yet. :wink:

  2. It would make it overly complicated to implement the index type's Comparable requirement.

  3. Most importantly, it would make Deque work surprisingly different to its traditional implementations elsewhere, as far as I can tell without providing any meaningful practical benefit.

1 Like