3.1 Collections and Iterators

All of the one dimensional collection types we use are derived from the Collection class. The elements contained in a collection can be examined via the creation of an iterator - different collections will have different kinds of iterators, all of which are derived from class Iterator . Any collection must be able to allocate (via new ) the appropriate type of iterator. The iterator can be dereferenced (via operator * ) to access the current element or incremented (via operator ++ ) to move to the next element. If an iterator is used where a boolean is required (e.g. in the conditional expression of a for loop), the operator bool() function will return true iff there are more elements to be iterated over. The class declarations include the following lines:

template<class T> class Collection {
public:
        Iterator<T> *new_iterator();
    Any_Iterator<T>  any_iterator();

                 int size() const;
};

template<class T> class Iterator {
public:
          T &  operator*();
       void    operator++();
               operator bool() const;
};

We can therefore enumerate the elements of any collection as follows:

        int sum(Collection<int> &c)
            {
            Iterator<int> *i;
            int s = 0;

            for (i = c.new_iterator(); (*i); (*i)++)
                s += *(*i);

            delete i;
            return s;
            }

As it is easy to forget that the new_iterator must later be delete d, we have provided the type Any_Iterator , which handles this issue automatically.

        int sum(Collection<int> &c)
            {
            int s = 0;

            for (Any_Iterator i = c.any_iterator(); i; i++)
                s += *i;

            return s;
            }

Caveats

If a collection is changed (elements are added or removed), all the behavior of any iterators on that collection is, in general, not defined.

Both the new_iterator and any_iterator functions cause heap allocation. If we know what kind of collection we are working with, we can avoid the overhead inherent in this allocation by using a specialized iterator for that type of collection (such as a List_Iterator

for a List , as in Section 3.3).

Note that iterators can also be manipulated via an alternate set of functions: live() , curr() , and next() . These are particularly useful in a debugger, where the other syntax can be difficult to use.

Many classes in the Presburger library have iterators to walk through the structure -- iterators over conjunctions in a formula in disjunctive normal form, iterators over constraints in a conjunction, or iterators over variables in a constraint. These will be discussed in more detail later.

Web Accessibility