Qt 4's New Style of Iterators

Материал из Wiki.crossplatform.ru

Qt Quarterly | Выпуск 12 | Документация

by Jasmin Blanchette

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

Содержание 1 The Qt 4 Alternative: Java-Style Iterators 2 Implicit Sharing and Iterators 3 Foreach Loops

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

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

|- bgcolor="#F0F0FF" | |Pros and Cons of STL Iterators |}

The main advantage of STL iterators over any other type of iteratorsis that you can use them together with STL generic algorithms(defined in <algorithm>). For example, if you want to sort allthe items in a QVector<int>, 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 <QtAlgorithms>(or <qalgorithms.h> if you prefer the old style of includes).This is useful if you build your software on platforms that don'tprovide an STL implementation (e.g., on Qt/Embedded).

The STL iterator syntax is modeled after the syntax of pointers intoan array. This makes it possible to use STL's (or Qt's) genericalgorithms 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 simplifiedview of reality. See SGL's STL pagefor a formal definition of STL iterators.)

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

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

• Modifying a container using a non-const STL iterator isnotoriously 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 beforeyou 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 iteratebackward, as well as rbegin() and rend() functions in itscontainers. 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 andinconsistent with the rest of the Qt API.

The operator-based syntax is especially cumbersome when the valuetype is a pointer, because you then need to dereference the iteratortwice---once to get the pointer and once to get the object. Forexample:

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() onthe container object is also a common source of confusion. Forexample, 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 thesame as the object on which end() is called; QSplitter::size()returns a container by value, not by reference.

[править] The Qt 4 Alternative: Java-Style Iterators

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

Like STL-style iterators, Java-style iterators come in two variants:a const and a non-const iterator class. For QList<T>, theJava-style iterator classes are QListIterator<T> andQMutableListIterator<T>. Notice that the shorter name is givento 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 thecontainer. If you accidentally modify the container while an iteratoris active, the iterator will take a deep copy and continue iteratingover the original data, instead of giving wrong results or crashing.This makes Java-style iterators less error-prone to use thanSTL-style iterators.

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

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

Let's see how this works in practice. Here's a loop that computes thesum of all items in a QList<int>:

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

The list is passed to the iterator's constructor. The iterator isthen initialized to the position before the first item. Then wecall hasNext() to determine whether there is an item to the rightof the iterator ("Item 0"), and if so, we call next() to obtainthat item and advance the iterator beyond the item. We repeat thisoperation until the iterator is located after the last item. Atthat 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 tothe left of the current iterator position; previous() returnsthat 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 callnext() or previous() multiple times, because it moves theiterator in addition to returning the item. The obvious solutionis 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() functionthat returns the item after the current iterator position, withoutside 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 thecurrent iterator position. This gives us yet another way of writingthe "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<T>). Non-const, or mutable, iterators provide thesame navigation functions, but in addition they offer functionsto insert, modify, and remove items from the container.

Let's start with a code snippet that replaces all negative values ina QList<int> 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 thatwas skipped. If we are iterating forward, this means the item to theleft of the new current position.

When iterating backward, setValue() correctly modifies the itemto the right of the new current position. For example, the followingcode snippets replaces all negative values with zero starting fromthe 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 everyitem, we skip backward past the item and, if its value is negative, we callsetValue() to set its value to 0.

Let's now suppose that we want to remove all negative items fromthe list. The algorithm is similar, except that this time we callremove() 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 toremove() 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 currentiterator position, as we would expect.

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

If you need to find all occurrences of a certain value in asequential container (a QList, QLinkedList, or QVector),you can use findNext() or findPrevious(). For example, thefollowing 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 associativecontainers (QMap, QHash). The associative container iteratorswork a bit differently to their sequential counterparts, givingaccess to both the key and the value.

The following example computes the sum of all the values stored in aQMap<QString, int>:

    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 holdsa key--value pair. In the example above, we only need the value, sowe call value(). If we need both the key and the value, we canuse the iterator's key() and value() functions, whichoperate 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 forchanging the key associated to an item, because this would makelittle sense for an associative container. You can't change a keywithout potentially changing the position of an item in thecontainer.

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

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

[править] Implicit Sharing and Iterators

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

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

Qt's container classes are all implicitly shared, so that you canpass them around to functions as you will. Because of this, implicitsharing encourages a programming style where containers (and otherQt 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 anon-const reference to avoid the copy that takes place when thereturn value is stored in a variable:

void createPopulationMap(QMap<QString, int> &amp;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 everyfunction in Qt that returns a QString took a QString &instead? It's also error-prone, because the implementor must rememberto call clear() at the beginning of the function.

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

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

Finally, there is one rule that you must keep in mind when usingSTL-style iterators: Don't take a copy of a container whilenon-const iterators are active on that container. If you break thatrule, 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 STLiterators significantly heavier or compromising Qt's guarantee thatcopying 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 thecontainer, but the copies won't be shared.

[править] Foreach Loops

It would be impossible to write an article about iterators in Qt 4without mentioning foreach, a Qt keyword that allows youto iterate over all items in a container conveniently. But since thebottom of this page is rapidly catching up with me, I'm restricted togiving one code snippet and point to the reference documentationfor 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.