Container Classes

Java-Style Iterators

The Java-style iterators are new in Qt 4 and are the standard ones used in Qt applications. They are more convenient to use than the STL-style iterators, at the price of being slightly less efficient. Their API is modelled on Java's iterator classes.

For each container class, there are two Java-style iterator data types: one that provides read-only access and one that provides read-write access.

In this discussion, we will concentrate on QList and QMap. The iterator types for QLinkedList, QVector, and QSet have exactly the same interface as QList's iterators; similarly, the iterator types for QHash have the same interface as QMap's iterators.

Unlike STL-style iterators (covered below), 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:

Here's a typical loop for iterating through all the elements of a QList<QString> in order and printing them to the console:

 QList<QString> list;
 list << "A" << "B" << "C" << "D";

 QListIterator<QString> i(list);
 while (i.hasNext())
     qDebug() << i.next();

It works as follows: The QList to iterate over is passed to the QListIterator constructor. At that point, the iterator is located just in front of the first item in the list (before item "A"). Then we call hasNext() to check whether there is an item after the iterator. If there is, we call next() to jump over that item. The next() function returns the item that it jumps over. For a QList<QString>, that item is of type QString.

Here's how to iterate backward in a QList:

 QListIterator<QString> i(list);
 i.toBack();
 while (i.hasPrevious())
     qDebug() << i.previous();

The code is symmetric with iterating forward, except that we start by calling toBack() to move the iterator after the last item in the list.

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

The following table summarizes the QListIterator API:

QListIterator provides no functions to insert or remove items from the list as we iterate. To accomplish this, you must use QMutableListIterator. Here's an example where we remove all odd numbers from a QList<int> using QMutableListIterator:

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

The next() call in the loop is made every time. It jumps over the next item in the list. The remove() function removes the last item that we jumped over from the list. The call to remove() does not invalidate the iterator, so it is safe to continue using it. This works just as well when iterating backward:

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

If we just want to modify the value of an existing item, we can use setValue(). In the code below, we replace any value larger than 128 with 128:

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

Just like remove(), setValue() operates on the last item that we jumped over. If we iterate forward, this is the item just before the iterator; if we iterate backward, this is the item just after the iterator.

The next() function returns a non-const reference to the item in the list. For simple operations, we don't even need setValue():

 QMutableListIterator<int> i(list);
 while (i.hasNext())
     i.next() *= 2;

As mentioned above, QLinkedList's, QVector's, and QSet's iterator classes have exactly the same API as QList's. We will now turn to QMapIterator, which is somewhat different because it iterates on (key, value) pairs.

Like QListIterator, QMapIterator provides toFront(), toBack(), hasNext(), next(), peekNext(), hasPrevious(), previous(), and peekPrevious(). 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> map;
 map.insert("Paris", "France");
 map.insert("Guatemala City", "Guatemala");
 map.insert("Mexico City", "Mexico");
 map.insert("Moscow", "Russia");
 ...

 QMutableMapIterator<QString, QString> i(map);
 while (i.hasNext()) {
     if (i.next().key().endsWith("City"))
         i.remove();
 }

QMapIterator also provides a key() and a value() function that operate directly on the iterator and that return the key and value of the last item that the iterator jumped above. For example, the following code copies the contents of a QMap into a QHash:

 QMap<int, QWidget *> map;
 QHash<int, QWidget *> hash;

 QMapIterator<int, QWidget *> i(map);
 while (i.hasNext()) {
     i.next();
     hash.insert(i.key(), i.value());
 }

If we want to iterate through all the items with the same value, we can use findNext() or findPrevious(). Here's an example where we remove all the items with a particular value:

 QMutableMapIterator<int, QWidget *> i(map);
 while (i.findNext(widget))
     i.remove();

 QList<QString> list;
 list << "A" << "B" << "C" << "D";

 QList<QString>::iterator i;
 for (i = list.begin(); i != list.end(); ++i)
     *i = (*i).toLower();

 QList<QString> list;
 list << "A" << "B" << "C" << "D";

 QList<QString>::iterator i = list.end();
 while (i != list.begin()) {
     --i;
     *i = (*i).toLower();
 }

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

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

 // RIGHT
 const QList<int> sizes = splitter->sizes();
 QList<int>::const_iterator i;
 for (i = sizes.begin(); i != sizes.end(); ++i)
     ...

 // WRONG
 QList<int>::const_iterator i;
 for (i = splitter->sizes().begin();
         i != splitter->sizes().end(); ++i)
     ...

 QLinkedList<QString> list;
 ...
 QString str;
 foreach (str, list)
     qDebug() << str;

 QLinkedList<QString> list;
 ...
 QLinkedListIterator<QString> i(list);
 while (i.hasNext())
     qDebug() << i.next();

 QLinkedList<QString> list;
 ...
 foreach (const QString &str, list)
     qDebug() << str;

 QLinkedList<QString> list;
 ...
 foreach (const QString &str, list) {
     if (str.isEmpty())
         break;
     qDebug() << str;
 }

 QMap<QString, int> map;
 ...
 foreach (const QString &str, map.keys())
     qDebug() << str << ":" << map.value(str);

 QMultiMap<QString, int> map;
 ...
 foreach (const QString &str, map.uniqueKeys()) {
     foreach (int i, map.values(str))
         qDebug() << str << ":" << i;
 }

 forever {
     ...
 }

 CONFIG += no_keywords

 QString onlyLetters(const QString &in)
 {
     QString out;
     for (int j = 0; j < in.size(); ++j) {
         if (in[j].isLetter())
             out += in[j];
     }
     return out;
 }