Qt 4 introduces a new type of iterator, inspired by Java's iterators. In this article, I will start by reviewing the old-style STL-like iterators and the main problems associated with their use. Then I will show off Qt 4's Java-style iterators.

• Pros and Cons of STL Iterators
• The Qt 4 Alternative: Java-Style Iterators
• Implicit Sharing and Iterators
• Foreach Loops

But first, a bit of history. Qt 3 provides a set of value-based container classes, dubbed "QTL", whose iterators are inspired from the C++ Standard Template Library (STL).

The Qt 4 Tulip container classes have a very similar API to the old QTL value-based classes and still provide STL-style iterators. They have been optimized for minimal code expansion and can safely be copied across threads, even though they use implicit sharing as a speed and memory optimization. For an overview of the Qt 4 Tulip containers, see the Generic Containers page from the online documentation.

The main advantage of STL iterators over any other type of iterators is that you can use them together with STL generic algorithms (defined in ). For example, if you want to sort all the items in a QVector, you can call sort() as follows:

QVector<int> vector;
vector << 3 << 1 << 4 << 1 << 5 << 9 << 2;
 
sort(vector.begin(), vector.end());
// vector: [1, 1, 2, 3, 4, 5, 9]

Qt 4 also provides a set of generic algorithms in (or if you prefer the old style of includes). This is useful if you build your software on platforms that don't provide an STL implementation (e.g., on Qt/Embedded).

The STL iterator syntax is modeled after the syntax of pointers into an array. This makes it possible to use STL's (or Qt's) generic algorithms on a plain C++ array. For example:

int array[7] = { 3, 1, 4, 1, 5, 9, 2 };
int *begin = &array[0];
int *end = &array[7];
 
sort(begin, end);
// array: [1, 1, 2, 3, 4, 5, 9]

The table below gives an overview of the STL iterator syntax:

(To keep the article short, the table gives a somewhat simplified view of reality. See SGL's STL page for a formal definition of STL iterators.)

Each Tulip container QXxx has two STL-style iterator classes: QXxx::iterator and QXxx::const_iterator. The non-const iterator can be used to modify the container while iterating; the const iterator should be used for read-only access.

The three main advantages of Qt's STL-style iterators are that they are implemented very efficiently (an STL iterator is typically just syntactic sugar for a pointer), that they are compatible with STL's generic algorithms, and that most C++/Qt programmers are already familiar with them. But they have some disadvantages as well.

• Modifying a container using a non-const STL iterator is notoriously error-prone.

For example, the following code might skip one item, or skip the "end" item and crash:

// WRONG
for (i = list.begin(); i != list.end(); ++i) {
    if (*i > threshold)
        i = list.erase(i);
}

It must be written as follows:

i = list.begin();
while (i != list.end()) {
    if (*i > threshold)
        i = list.erase(i);
    else
        ++i;
}

• Iterating forward and backward are not symmetric.

When iterating backward, you must decrement the iterator before you access the item. For example:

// Forward                  // Backward
i = list.begin();           i = list.end();
while (i != list.end()) {   while (i != list.begin()) {
    bamboozle(*i);              --i;
    ++i;                        bamboozle(*i);
}                           }

The STL addresses this problem by providing a reverse_iterator<> iterator adaptor that wraps an iterator type to make it iterate backward, as well as rbegin() and rend() functions in its containers. This enables you to write

i = list.rbegin();
while (i != list.rend()) {
    bamboozle(*i);
    ++i;
}

However, this solution requires two additional iterator types, reverse_iterator and const_reverse_iterator. }

• Many users find the operator-based syntax cumbersome and inconsistent with the rest of the Qt API.

The operator-based syntax is especially cumbersome when the value type is a pointer, because you then need to dereference the iterator twice---once to get the pointer and once to get the object. For example:

QList<QWidget *> list;
...
QList<QWidget *>::iterator i = list.begin();
while (i != list.end()) {
    (*i).show();   // won't compile
    i->show();     // won't compile
    (**i).show();  // OK
    (*i)->show();  // OK
    ++i;
}

The requirement that you must call both begin() and end() on the container object is also a common source of confusion. For example, the following code typically results in a crash:

// WRONG
i = splitter->sizes().begin();
while (i != splitter->sizes().end()) {
    humbug(*i);
    ++i;
}

This is because the object on which begin() is called isn't the same as the object on which end() is called; QSplitter::size() returns a container by value, not by reference.

Qt 4 introduces Java-style iterators as an alternative to STL-style iterators. As their name suggests, their syntax is inspired from the Java iterator classes. They attempt to solve the main issues with STL-style iterators.

Like STL-style iterators, Java-style iterators come in two variants: a const and a non-const iterator class. For QList, the Java-style iterator classes are QListIterator and QMutableListIterator. Notice that the shorter name is given to the iterator type that is most frequently used (the const iterator).

One nice feature of the non-const iterators (the "mutable" iterators) is that they automatically take a shallow copy of the container. If you accidentally modify the container while an iterator is active, the iterator will take a deep copy and continue iterating over the original data, instead of giving wrong results or crashing. This makes Java-style iterators less error-prone to use than STL-style iterators.

The main disadvantage of Java-style iterators is that they expand to more code in your executables. If you're using Qt/Embedded and deploying on a resource-scarce device, you might want to stick to using STL-style iterators.

Java-style iterators don't point directly at items; instead, they are located either before or after an item. This eliminates the need for a "one past the last" item (STL's end()) and makes iterating backward symmetric with iterating forward.

Let's see how this works in practice. Here's a loop that computes the sum of all items in a QList:

QList<int> list;
...
QListIterator<int> i(list);
while (i.hasNext())
    sum += i.next();

The list is passed to the iterator's constructor. The iterator is then initialized to the position before the first item. Then we call hasNext() to determine whether there is an item to the right of the iterator ("Item 0"), and if so, we call next() to obtain that item and advance the iterator beyond the item. We repeat this operation until the iterator is located after the last item. At that point, hasNext() returns false.

Iterating backward is similar, except that we must call toBack() first to move the iterator to after the last item:

QList<int> list;
...
QListIterator<int> i(list);
i.toBack();
while (i.hasPrevious())
    sum += i.previous();

The hasPrevious() function returns true if there is an item to the left of the current iterator position; previous() returns that item and moves the iterator back by one position. Both functions return the item that was skipped.

Sometimes we need the same item multiple times. We cannot call next() or previous() multiple times, because it moves the iterator in addition to returning the item. The obvious solution is to store the return value in a variable:

while (i.hasNext()) {
    int value = i.next();
    sumSquares += value * value;
}

For convenience, the iterator classes offer a peekNext() function that returns the item after the current iterator position, without side effects. This allows us to rewrite the code snippet as follows:

while (i.hasNext()) {
    sumSquares += i.peekNext() * i.peekNext();
    i.next();
}

You can also use peekPrevious() to obtain the item before the current iterator position. This gives us yet another way of writing the "sum squares" code snippet:

while (i.hasNext()) {
    i.next();
    sumSquares += i.peekPrevious() * i.peekPrevious();
}

So far, we've only seen how to use the const iterator types (e.g., QListIterator). Non-const, or mutable, iterators provide the same navigation functions, but in addition they offer functions to insert, modify, and remove items from the container.

Let's start with a code snippet that replaces all negative values in a QList with zero:

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

The setValue() function changes the value of the last item that was skipped. If we are iterating forward, this means the item to the left of the new current position.

When iterating backward, setValue() correctly modifies the item to the right of the new current position. For example, the following code snippets replaces all negative values with zero starting from the end:

QMutableListIterator<int> i(list);
i.toBack();
while (i.hasPrevious()) {
    if (i.previous() < 0)
        i.setValue(0);
}

First we move the iterator to the back of the list. Then, for every item, we skip backward past the item and, if its value is negative, we call setValue() to set its value to 0.

Let's now suppose that we want to remove all negative items from the list. The algorithm is similar, except that this time we call remove() instead of setValue():

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

One strength of Java-style iterators is that after the call to remove() we can keep iterating as if nothing had happened. We can also use remove() when iterating backward:

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

This time, remove() affects the item after the current iterator position, as we would expect.

You can also insert an item into the container as you are iterating over it by calling insert(). The new item is inserted at the iterator position, and the iterator is advanced to point between the new item and the next item.

If you need to find all occurrences of a certain value in a sequential container (a QList, QLinkedList, or QVector), you can use findNext() or findPrevious(). For example, the following loop removes all occurrences of 0 in a list:

while (i.findNext(0))
    i.remove();

Qt 4 provides Java-style iterators both for its sequential containers (QList, QLinkedList, QVector) and for its associative containers (QMap, QHash). The associative container iterators work a bit differently to their sequential counterparts, giving access to both the key and the value.

The following example computes the sum of all the values stored in a QMap:

    QMap<QString, int> map;
    map["Tokyo"] = 28025000;
    map["Mexico City"] = 18131000;
    ...
    QMapIterator<QString, int> i(map);
    while (i.hasNext())
        sum += i.next().value();
 

The next() and previous() functions return an object that holds a key--value pair. In the example above, we only need the value, so we call value(). If we need both the key and the value, we can use the iterator's key() and value() functions, which operate on the last item that was skipped. For example:

QMapIterator<QString, int> i(map);
while (i.hasNext()) {
    i.next();
    if (i.value() > largestValue) {
        largestKey = i.key();
        largestValue = i.value();
    }
}

Again, this works the same when iterating backward:

QMapIterator<QString, int> i(map);
i.toBack();
while (i.hasPrevious()) {
    i.previous();
    if (i.value() > largestValue) {
        largestKey = i.key();
        largestValue = i.value();
    }
}

We can modify the value associated with a key using setValue(). The associative iterators have no API for inserting items or for changing the key associated to an item, because this would make little sense for an associative container. You can't change a key without potentially changing the position of an item in the container.

In summary, Java-style iterators solve the main issues with STL-style iterators:

• Iterating forward and backward are symmetric operations.
• Modifying a container using a Java-style iterator is easy and not error-prone.
• The Java iterator syntax is highly readable and consistent with the rest of the Qt API.

The Java-style iterators have another advantage over their STL counterparts, related to Qt's extensive use of implicit sharing.

Implicit sharing is an optimization that takes place behind the scenes in Qt. When you take a copy of an object, only a pointer to the data is copied; the actual data is shared by the two objects (the original and the copy). When either object is modified, the object first takes a copy of the data, to ensure that the modification will apply only to this object, not to other objects that shared the data. This is why this optimization is sometimes called "copy on write".

Qt's container classes are all implicitly shared, so that you can pass them around to functions as you will. Because of this, implicit sharing encourages a programming style where containers (and other Qt classes such as QString and QImage) are returned by value:

QMap<QString, int> createPopulationMap()
{
    QMap<QString, int> map;
    map["Tokyo"] = 28025000;
    map["Mexico City"] = 18131000;
    ...
    return map;
}

The call to the function looks like this:

QMap<QString, int> map = createPopulationMap();

Without implicit sharing, you would be tempted to pass the map as a non-const reference to avoid the copy that takes place when the return value is stored in a variable:

void createPopulationMap(QMap<QString, int> &map)
{
    map.clear();
    map["Tokyo"] = 28025000;
    map["Mexico City"] = 18131000;
    ...
}

The call then becomes

QMap<QString, int> map;
createPopulationMap(map);

Programming like this can rapidly become tedious. Imagine if every function in Qt that returns a QString took a QString & instead? It's also error-prone, because the implementor must remember to call clear() at the beginning of the function.

Implicit sharing is a guarantee from Qt that the data won't be copied if you don't modify it. If you use STL-style iterators for read-only access, you should always use const_iterator, not iterator---the latter might cause a deep copy of the data to occur. For the same reason, you should call constBegin() and constEnd(), which return a const_iterator, rather than begin() and end().

With Java-style iterators, the same rule applies: Use QXxxIterator rather than QMutableXxxIterator whenever possible.

Finally, there is one rule that you must keep in mind when using STL-style iterators: Don't take a copy of a container while non-const iterators are active on that container. If you break that rule, you might end up having strange side effects. For example:

QList<int> list;
list << 1 << 2 << 3 << 4;
 
QList<int>::iterator i = list.begin();
QList<int> copy = list;
*i = 99;
// list: [99, 2, 3, 4]
// copy: [99, 2, 3, 4]

This doesn't occur if you create the copy before calling begin(), because begin() causes a deep copy to occur.

This issue is practically impossible to fix without making the STL iterators significantly heavier or compromising Qt's guarantee that copying a container occurs in constant time.

The higher-level Java-style iterators don't suffer from that flaw. While the iterator is active, you can still take copies of the container, but the copies won't be shared.

It would be impossible to write an article about iterators in Qt 4 without mentioning foreach, a Qt keyword that allows you to iterate over all items in a container conveniently. But since the bottom of this page is rapidly catching up with me, I'm restricted to giving one code snippet and point to the reference documentation for more information. So here's the code:

QStringList nameList;
nameList << "Maria" << "Peter" << "Alexandra";
 
foreach (QString name, nameList)
    cout << name.ascii() << endl;

And the docs: http://www.crossplatform.ru/documentation/qtdoc4.3/containers.php.