[swift-evolution] [RFC] New collections model: collections advance indices

[Dmitri Gribenko]

Hi,

We would like to propose a major change to how collection indices
work.  The standard library team has discussed this idea internally
and we wrote a prototype.  Now we think it is a viable direction to
consider, and we are bringing it for wider public discussion.

I'm pasting the first section of the proposal below to give you a
general idea about this change, but please read the proposal to
understand the full details.

You can find the most up to date version of the proposal at
https://github.com/gribozavr/swift-evolution/blob/new-collections/proposals/NNNN-collections-move-indices.md

Permalink: https://github.com/gribozavr/swift-evolution/blob/87df19a9a9d73e64a2a966b807440216a608b8ad/proposals/NNNN-collections-move-indices.md

Dmitri

## Introduction

We are proposing a new model for collections, where indices can only be
advanced forward or backward by the corresponding collection instance.
Indices become opaque tokens representing collection positions, that can
be produced and consumed by collection APIs.  This allows us to reduce
the amount of data stored in indices to the bare minimum.

Compared to the current state, the new scheme simplifies implementation
of non-trivial indices, and fixes concurrency issues in `Set` and
`Dictionary` indices.  It also allows us to eliminate reference-counted
stored properties from most indices, including non-trivial ones, like
`Set.Index` and `Dictionary.Index`, creating more optimizable code.

Out of scope for this proposal:

* Expanding the set of concrete collections provided by the standard
  library.

* Expanding the set of collection protocols to provide functionality
  beyond what is already provided (for example, protocols for sorted
  collections, queues etc.)  Discussing how other concrete collections
  fit into the current protocol hierarchy is in scope, though.

-- 
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr at gmail.com>*/