Overview

Collections are aggregate data structures that map from keys to elements. All collections are instances of the class <collection>.

<collection> has two covering subclasses: <sequence> and <explicit-key-collection>. Every concrete subclass of <collection> must also be a subclass of <sequence> or <explicit-key-collection>. Sequences use successive non-negative integers as keys; explicit key collections may use any object as a key. Both of these classes have predefined subclasses and may be additionally subclassed by programmers. See Collections on page 206 for a complete description of these classes.

A large number of functions are available on collections, including functions for iteration, mapping, random access of elements, sorting, filtering, etc. See Collection Operations on page 294 for a complete description of these functions.

The Iteration Protocol

All collections implement an iteration protocol that allows iteration to be specified abstractly. Many higher level operations on collections can be defined in terms of only the iteration protocol. For many programs these higher level operations are sufficient; they will not need to use the iteration protocol directly. The iteration protocol is used by programs defining new collection types, and for certain types of iteration that cannot be handled by the built-in higher level operations.

The iteration protocol centers on the notion of a state object for an iteration. Each collection class chooses its own most appropriate representation for an iteration state, and only the functions of the iteration protocol are affected by this choice.

Use of the iteration protocol is based on the assumption that the collection over which iteration occurs remains static for the duration of the iteration. That is, arbitrary changes to a mutable collection while an iteration is in progress may cause the iteration to produce unpredictable results.

With notable exceptions, two or more iterations over the same collection are not guaranteed to produce the same values in the same order, even if the collection is unaltered. For details, see Iteration Stability and Natural Order as follows.

The built-in collection functions are implemented in terms of the iteration protocol. When defining a new collection class, a programmer need only define the iteration protocol for the class. Once this is done, instances of the class can be used with all the built-in collection functions. Of course, in some cases it will be more efficient to define methods on these functions optimized for the new class, rather than relying on the default implementation based on the iteration protocol.