CopperSpice API: Iterator Classes

The CopperSpice container classes provide two types of iterators: Java style iterators and STL style iterators. Iterators provide a uniform way to access items in any container.

To traverse the items stored in a container use Java style iterators, STL style iterators, or a range based for loop.

Java Style Iterators

The Java style iterator API is modeled on Java's iterator classes. For each container class there are two Java style iterator data types, one which provides read only access and one which provides read write access.

Container	Read/Only Iterator	Read/Write Iterator
QList<T>, QQueue<T>	QListIterator<T>	QMutableListIterator<T>
QLinkedList<T>	QLinkedListIterator<T>	QMutableLinkedListIterator<T>
QVector<T>, QStack<T>	QVectorIterator<T>	QMutableVectorIterator<T>
QSet<T>	QSetIterator<T>	QMutableSetIterator<T>
QMap<Key, Val, C>	QMapIterator<Key, Val, C>	QMutableMapIterator<Key, Val, C>
QMultiMap<Key, Val, C>	QMultiMapIterator<Key, Val, C>	QMutableMultiMapIterator<Key, Val, C>
QHash<Key, Val, Hash, KeyEqual>	QHashIterator<Key, Val, Hash, KeyEqual>	QMutableHashIterator<Key, Val, Hash, KeyEqual>
QMultiHash<Key, Val, Hash, KeyEqual>	QMultiHashIterator<Key, Val, Hash, KeyEqual>	QMutableMultiHashIterator<Key, Val, Hash, KeyEqual>

Unlike STL style iterators, Java style iterators point between items rather than directly at items. For this reason they are either pointing to the very beginning of the container (before the first item), at the very end of the container (after the last item), or between two items. The diagram below shows the valid iterator positions as red arrows for a list containing four items.

Overview of Java Iterators

The Java style iterators for QList, QLinkedList, QSet, and QVector are very similar. Multiple iterators can be used on the same list, linked list, set, or vector. The following is a typical loop to iterate over all the elements of a QList<QString>.

QList<QString> data;
data << "A" << "B" << "C" << "D";
 
QListIterator<QString> iter(data);
 
while (iter.hasNext()) {
  qDebug() << iter.next();
}

In the example above the QList being iterated over is passed to the QListIterator constructor. The iterator is located just in front of the first item in the list (before item "A"). The method hasNext() is called to check whether there is an item after the iterator. If there is, you can call next() to jump over that item. The next() method returns the item which was jumped over. For a QList<QString> the data type of the item is of type QString.

The following code shows one way to iterate backwards in a QList. It is symmetric with iterating forward except we start by calling toBack() to move the iterator after the last item in the list.

Since these iterators are used in the same fashion, this block of code can be used with QLinkedList or QVector. It is not possible to iterate backwards over a QSet since the order is not meaningful.

QListIterator<QString> iter(data);
iter.toBack();
 
while (iter.hasPrevious()) {
   qDebug() << iter.previous();
}

The diagram below illustrates the effect of calling next() and previous() on an iterator.

The following table summarizes the QListIterator API.

Method	Behavior
toFront()	Moves the iterator to the front of the list (before the first item)
toBack()	Moves the iterator to the back of the list (after the last item)
hasNext()	Returns true if the iterator is not at the back of the list
next()	Returns the next item and advances the iterator by one position
peekNext()	Returns the next item without moving the iterator
hasPrevious()	Returns true if the iterator is not at the front of the list
previous()	Returns the previous item and moves the iterator back by one position
peekPrevious()	Returns the previous item without moving the iterator

QListIterator provides no methods to insert or remove items from the list as we iterate. To accomplish this use QMutableListIterator. Only one mutable iterator can be active on a given list at any time. Furthermore, no changes should be done directly to the list while the iterator is active (as opposed to through the iterator), since this could invalidate the iterator and lead to undefined behavior.

The following is an example where all the odd numbers are removed from a QList<int> using QMutableListIterator.

QMutableListIterator<int> iter(data);
 
while (iter.hasNext()) {
    if (iter.next() % 2 != 0) {
        iter.remove();
    }
}

The call to the next() method is made every time and jumps over the next item in the list. The remove() method removes the last item we jumped over in the list. The call to the remove() method does not invalidate the iterator so it is safe to continue using it.

This approach works the same when iterating backward or forward over the list.

QMutableListIterator<int> iter(list);
iter.toBack();
 
while (iter.hasPrevious()) {
    if (iter.previous() % 2 != 0) {
        iter.remove();
    }
}

To modify the value of an existing item use setValue(). The code below replaces any value larger than 128 with 128.

QMutableListIterator<int> iter(list);
 
while (iter.hasNext()) {
    if (iter.next() > 128) {
        iter.setValue(128);
    }
}

Just like remove(), setValue() operates on the last item jumped over. When iterating forward, the item just before the iterator will be modified. When iterating backward, the item just after the iterator will be modified.

The next() method returns an lvalue reference (non-const) which allows the value which was just jumped over to be modified.

QMutableListIterator<int> iter(list);
 
while (iter.hasNext()) {
    iter.next() *= 2;
}

QList Java Iterators

The QListIterator<T> class allows you to iterate over a QList<T>. If you want to modify the list use QMutableListIterator<T>.

QLinkedList Java Iterators

The QLinkedListIterator<T> class allows you to iterate over a QLinkedList<T>. If you want to modify the linked list use QMutableLinkedListIterator<T>.

QSet Java Iterators

The QSetIterator<T> class allows you to iterate over a QSet<T>. There is no mutable iterator for a QSet since the values can not be modified. The only way to edit an element is to erase it and add the new value.

QVector Java Iterators

The QVectorIterator<T> class allows you to iterate over a QVector<T> or a QStack<T>. If you want to modify the vector or the set use QMutableVectorIterator<T>.

QMap and QHash Java Iterators

The QMapIterator is different from the other iterators since it iterates on key, value pairs. The key and value components are extracted by calling key() and value() on the object returned by next(), peekNext(), previous(), or peekPrevious().

The following example removes all (capital, country) pairs where the capital's name ends with "City":

QMap<QString, QString> mapData;
mapData.insert("Paris", "France");
mapData.insert("San Francisco", "United States");
mapData.insert("Mexico City", "Mexico");
mapData.insert("Sydney", "Australia");
 
QMutableMapIterator<QString, QString> iter(mapData);
 
while (iter.hasNext()) {
    if (iter.next().key().endsWith("City")) {
        iter.remove();
    }
}

QMapIterator also provides key() and value() methods which operate directly on the iterator and return the key and value respectively for the last item the iterator jumped over. The following is an example using key() and value() and copies the contents of a QMap into a QHash.

QMap<int, QWidget *>  mapData;
QHash<int, QWidget *> hashData;
 
QMapIterator<int, QWidget *> iter(mapData);
 
while (iter.hasNext()) {
    iter.next();
    hashData.insert(iter.key(), iter.value());
}

To iterate over all the map items with the same value, use findNext() or findPrevious(). This example removes all the items in the map with a value matching widget.

QMutableMapIterator<int, QWidget *> iter(mapData);
 
while (iter.findNext(widget)) {
    iter.remove();
}

STL Style Iterators

For each container class there are two STL style iterators. There is one which provides read-only access and one which provides read-write access. Read-only iterators should be used wherever possible.

Container	Read/Only Iterator	Read/Write Iterator
QList<T> QQueue<T>	QList::const_iterator	QList::iterator
QLinkedList<T>	QLinkedList::const_iterator	QLinkedList::iterator
QSet<T>	QSet::const_iterator	QSet::iterator
QVector<T> QStack<T>	QVector::const_iterator	QVector::iterator
QMap<Key, Val, C>	QMap::const_iterator	QMap::iterator
QMultiMap<Key, Val, C>	QMultiMap::const_iterator	QMultiMap::iterator
QHash<Key, Val, Hash, KeyEqual>	QHash::const_iterator	QHash::iterator
QMultiHash<Key, Val, Hash, KeyEqual>	QMultiHash::const_iterator	QMultiHash::iterator

The API of the STL iterators is modeled on pointers. For example, the ++ operator advances the iterator to the next item and the * operator returns the item the iterator is pointing to.

Unlike Java style iterators STL style iterators point directly at items. The begin() method of a container returns an iterator which points to the first item in the container. The end() method returns an iterator to an imaginary item one position past the last item in the container. Since the end iterator points to an invalid position it must never be dereferenced and is typically used in a loop's break condition. If the list is empty, begin() will equal end() so the loop is never executed.

The diagram below shows the valid iterator positions as red arrows for a vector containing four items.

Overview of STL Iterators

The STL style iterators for QList, QLinkedList, QSet, and QVector are all very similar. Multiple iterators can be used to traverse the same container. Modifying the container may invalidate one of the iterators. The default iterator constructor creates an uninitialized iterator. You must initialize it using a method like begin(), end(), or insert() before using the iterator.

The following is a typical loop to iterate over all the elements of a QList<QString>.

QList<QString> data;
data.append("January");
data.append("February");
...
data.append("December");
 
QList<QString>::iterator iter;
 
for (iter = data.begin(); iter != data.end(); ++iter) {
   qDebug() << *iter;
}

The following example removes the elements which start with 'J' from a set.

QSet<QString> data;
data.insert("January");
data.insert("February");
...
data.insert("December");
 
QSet<QString>::iterator iter = data.begin();
 
while (iter != data.end()) {
   if ((*iter).startsWith('J')) {
      iter = data.erase(iter);
   } else {
      ++iter;
   }
}

STL style iterators can be used as arguments to generic algorithms. For example, the following example shows how to find an item in a set using the std::find() algorithm.

QSet<QString> set;
QSet<QString>::iterator iter = std::find(set.begin(), set.end(), "Jeanette");
 
if (iter != set.end()) {
   cout << "Found Jeanette" << endl;
}

One way to iterate backwards with an STL style iterator is to use a reverse iterator.

QList<QString> list;
list << "A" << "B" << "C" << "D";
 
QList<QString>::reverse_iterator iter = list.rbegin();
 
while (iter != list.rend()) {
   *iter = iter->toLower();
   ++iter;
}

To iterate over a container when read-only access is desired, use const_iterator, constBegin(), and constEnd().

QList<QString>::const_iterator iter;
 
for (iter = list.constBegin(); iter != list.constEnd(); ++iter) {
   qDebug() << *iter;
}

The following table summarizes the STL style iterator API.

Expression	Behavior
`*i`	Returns the current item
`++i`	Advances the iterator to the next item
`i += n`	Advances the iterator by `n` items
`–i`	Moves the iterator back by one item
`i -= n`	Moves the iterator back by `n` items
`i - j`	Returns the number of items between iterators `i` and `j`

The ++ and – operators are available both as prefix (++i, –i) and postfix (i++, i–) operators.

The prefix versions modify the iterator and return a reference to the modified iterator. The postfix versions take a copy of the iterator before they modify it, and then return a copy. In expressions where the return value is ignored, use the prefix operators (++i, –i) as these are slightly faster.

For non-const iterator types the return value of the unary * operator can be used on the left side of the assignment operator.

Indexed Access

An alternative to using iterators for QList or QVector is to use an index position. For these two classes there are overloaded methods which take an index as a parameter. This makes it possible to access, insert, and remove items without using iterators.

QList STL Iterators

The QList<T>::iterator class allows you to iterate over a QList<T> or QQueue<T> and to modify the element associated with the iterator.

To iterate over a const QList use QList<T>::const_iterator. It is generally good practice to use QList<T>::const_iterator on a non-const QList when possible.

QLinkedList STL Iterators

The QLinkedList<T>::iterator class allows you to iterate over a QLinkedList<T> and to modify the element associated with the iterator.

To iterate over a const QLinkedList use QLinkedList<T>::const_iterator. It is generally good practice to use QLinkedList<T>::const_iterator on a non-const QLinkedList when possible.

QSet STL Iterators

The QSet<T>::iterator class allows you to iterate over a QSet and to remove items using QSet::erase() while you iterate.

To iterate over a const QSet use QSet<T>::const_iterator. It is generally good practice to use QSet<T>::const_iterator on a non-const QSet when possible.

QSet does not let you modify a specific element using an iterator. The only way to edit an element is to erase it and add the new value.

QVector STL Iterators

The QVector<T>::iterator class allows you to iterate over a QVector<T> or a QStack<T> and to modify the element associated with the iterator.

To iterate over a const QVector use QVector<T>::const_iterator. It is generally good practice to use QVector<T>::const_iterator on a non-const QVector when possible.

QMap and QHash STL Iterator

For QMap and QHash, the * operator returns the value component of an item. To retrieve the key call key() on the iterator. For symmetry, the iterator also supports a value() method to retrieve the value. The following is an example of how to print all items in a QMap to the console.

QMap<int, int> map;
QMap<int, int>::const_iterator iter;
 
for (iter = map.constBegin(); iter != map.constEnd(); ++iter) {
    qDebug() << iter.key() << ":" << iter.value();
}