Chap.3: SMART ITERATORS

A class library usually provides one or several iterators for each data structure. The iterator permits you to traverse the data using the operators ++ and --. However, if you try to destroy an aggregate by traversing it and destroying individual children, most libraries will crash:

    class Department { ... };
    class Employee { ... };

    Employee *e;
    Aggregate<Department,Employee> agg;

    // create a department with 10 employees
    Department* d=new Department;
    for(i=0; i<10; i++){
        e=new Employee;
        aggr.addTail(d,e);
    }

    // disconnect and destroy all employees
    AggregateIterator<Department,Employee> it;
    for(e=it.start(d); e; e=++it){ // crash on the second pass
        aggr.remove(e);
        delete e; 
    };

The reason for this crash is that most iterators remember the current object, and use its next pointer to get to the next object on the list. If the current object is destroyed within the loop, the next call to ++ attempts to use pointer next on an invalid (already destroyed) object, which results in a crash.

The cure for this problem is to have the iterator remember not the current object, but the next object on the list. Then, even if the current object is destroyed, you still get the next object correctly. This is the method used througout the Pattern Template Library. If you look at the implementation of any of the iterators in lib/*.h, you will see that this only slightly complicates the logic of the operators ++ and --, and is certainly worth the qualitative improvement in the behavior of the iterator.

The improved iterator still is not bullet proof. For example, if you perform the following operation, it will crash:

    Employee *e, *nxt;
    for(e=it.start(d); e; e=++it){
        if(...){
            nxt=aggr.nextChild(e);
            aggr.remove(nxt);
            delete nxt; 
        }
        ...
    };

It is possible to design an iterator which permits one to remove or add objects while traversing the list. In this case, for example, the Aggreate class must keep the list of all active AggregateIterator instances. Functions Aggregate::addTail() and Aggregate::remove() must run through all active iterators and check whether the change in the list affects the next object stored in each iterator, and if it does, modify it.

The PTL does not use this type of iterator, because it would cause problems when running with multiple threads.

The PTL permits you to use three styles of traversal loops. The first style combines a for(..) loop with functions start() or end() which start the iterator from the beginning or the end of the list:

    Department *d;
    Employee *e; 

    AggregateIterator<Department,Employee> it;

    ...

    for(e=it.start(d); e; e= ++it){
        ... // runs through all e under d
    }

    for(e=it.end(d); e; e= --it){
        ... // runs through all e under d
    } 

The second style uses the convenient macros ITERATE() or RETRACE(), which hide the underlying for() loops:

    Department *d;
    Employee *e;
    AggregateIterator<Department,Employee> it;
    

    ...
    ITERATE(it,d,e){
        ... // runs through all e under d
    }

    RETRACE(it,d,e){
        ... // runs through all e under d
    }

The third style uses function next(), but you have to handle the end of the loop yourself. Don't forget, we are working with a ring:

    for(e=aggr.head(d); e; e=aggr.next(e)){
        ... // runs through all e under d
        if(e==aggr.tail(d))break; // end condition
    }

Multiple loops are permitted in both styles, ++ and -- can be used within the same loop. If you use the iterator, functions next() and prev() may be used, but must not be used to advance the loop variable. For example:

    Department *d;
    Employee *e,*ee;
    AggregateIterator<Department,Employee> it;
    Aggregate<Department,Employee> aggr;
    ...
    ITERATE(it,d,e){
        ...
        e=aggr.next(e);  // has no effect on the next iteration
        ee=aggr.next(e); // no problem
        ...
    }

SUMMARY:

1. For basic loops, use ITERATE() or RETRACE(); otherwise, start each loop with a begin() or end() function.
2. Multiple loops are allowed.
3. Operators ++ and -- may be used within the same loop.
4. When using iterators, do not advance the loop variable using the functions next() or prev().