[swift-evolution] [Proposal] Change some collection iterators to use custom types instead of IndexIterator<T>

[Michael Gottesman]

Hello everyone!

Iterators are very important for performance since we use them for for loops. By default collections if they do not provide a custom iterator use IndexingIterator as an iterator. IndexingIterator, while only supporting forward movement, is based on indices which possess the ability to go backwards and forwards. For some indices, backwards iteration adds unnecessary cost/complexity.
In order to preserve future flexibility, we want to change certain of the types to use custom types that are essentially just IndexingIterator<T>. Then later on when we want to implement these optimizations, we can do it on the custom type underneath the hood without changing the API/ABI.

The reason I use the phrase "some iterators" is that I already know that we definitely want to do this for StringCharacterView but there are potentially other containers in the standard library that this could apply to. I still need to audit these containers for potential applications. That being said given the place where we are in the schedule, I think it is important to start the discussion about the general concept and after I audit the various containers, I will post an update.

Thoughts, flames, etc?
Michael

https://bugs.swift.org/browse/SR-1961