Next: 3.2 Sequences Up: 3 Primitive Data Structures Previous: 3 Primitive Data Structures

# 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.

Next: 3.2 Sequences Up: 3 Primitive Data Structures Previous: 3 Primitive Data Structures

omega@cs.umd.edu

Web Accessibility