Iteration

The Collection Classes give you two methods of iteration:

• Using cursors
• Using the allElementsDo function together with applicators or applicator functions

Ordered (including sorted) collections have a well-defined ordering of their elements, while unordered collections have no defined order in which the elements are visited in an iteration. However, in both cases, each element is visited exactly once.

You cannot add or remove elements from a collection while you are iterating over a collection, or all elements may not be visited once. You cannot use any of the iterations described in this section if you want to remove all of the elements of a collection that have a certain property. Use the function removeAll that takes a predicate function as an argument.

Iteration with Cursors

To use the collection classes, you also need a cursor class for referencing an element in a collection, and an applicator class or function for iterating over a collection.

Cursors and iterators give you convenient methods for accessing the elements stored in the collections.

• cursors
• tree cursors
• applicators
• constant applicators

A cursor is a reference to the position of an element in a collection. If the position of the element changes, the cursor is invalidated. A cursor is always associated with a collection. The collection is specified when the cursor is created. Each collection function that takes a cursor argument has a precondition that the cursor actually belongs to the collection. Simple functions, such as advancing the cursor, are also functions of the cursor itself.

With cursors the Collection Classes provide:

• An iteration scheme that is simpler than using iterators.
• The ability to define functions that return cursors. Such functions can give you fast access to an element if it exists, or indicate the non-existence of an element by returning an invalid cursor.

Cursors are only temporarily defined. As soon as elements are added to or removed from the collection, existing cursors become undefined. One of the three following situations occurs:

1. The cursor is invalidated (isValid will return false).
2. The cursor remains valid and points to an element of the collection; however, it may point to a different element than before.
3. The cursor remains valid but no longer points to an element of the collection.

Do not use an undefined cursor as an argument to a function that requires the cursor to point to an element of the collection.

Each concrete collection class, such as ISet<int>, has an inner definition of a class Cursor that can be accessed as ISet<int>::Cursor.

Because abstract classes declare functions on cursors just as concrete classes do, there is a base class ICursor for these specific cursor classes. To allow for the creation of specific cursors for all kinds of collections, every abstract class has a virtual member function newCursor, which creates an appropriate cursor for the given collection object.

Iteration with allElementsDo

Cursor iteration has two possible drawbacks:

• For unordered collections, the explicit notion of an (arbitrary) ordering may be undesirable for stylistic reasons. For example, it could mislead you (or another programmer) into perceiving or exploiting an order where in fact the order does not exist or is not guaranteed.
  
• Iteration in an arbitrary order might be done more efficiently using something other than cursors. For example, with tree representations, a recursive descent iteration may be faster than the cursor navigation, even though the time for extra function calls must be considered.

The Collection Classes provide the allElementsDo function that addresses both drawbacks by calling a function that is applied to all elements. The function returns an IBoolean value that tells whether the iteration should be continued or not. For ordered collections, the function is applied in this order. Otherwise the order is unspecified.

The function that is applied in each iteration step can be given in two ways: directly as a C++ function, or by defining the function as a method of a user-defined applicator class:

• As a C++ function: Code the function that you want to be applied to all elements as a C++ function, then use allElementsDo to apply the function to the elements.
• As an object of an applicator class: Code the function as a member function of an applicator class that you create (for example, MyApplicatorClass) and let the applicator apply this function to every element, by using allElementsDo(myApplicatorObject), where myApplicatorObject is an object of MyApplicatorClass.

Introduction to the Collection Classes
Collection Characteristics
Ordering of Collection Elements
Access by Key
Equality Relation
Uniqueness of Entries
Flat Collections
Trees
Thread Safety and the Collection Classes

Adding an Element to a Collection
Removing an Element from a Collection
Using Cursors to Locate and Access Elements
Using Cursors to Iterate Over a Collection
Using allElementsDo and Applicators to Iterate Over a Collection
Cursors vs. Exception Handling
Taking Advantage of the Abstract Class Hierarchy
Instantiating the Collection Classes