Iterators

English Български

Written By : Girish Ramakrishnan, ForwardBias Technologies

Overview

Qt’s container classes (QVector, QList, QHash etc) support two styles of iterators: STL-style and Java style. This article digs into the implementation of the iterators. For a tutorial on Qt’s container classes, read the Qt Container documentation [doc.trolltech.com].

STL iterators

STL iterators are extremely efficient and fast because they behave essentially like pointers. QVector<T>::iterator is just a typedef of T * and is a pointer to an entry inside the array that QVector internally uses. operator+, – etc is just pointer arithmetic and using * operator on the iterator is just dereferencing the pointer.

For containers like QList, the iterator is a pointer to a internal QList’s Node. Suffice to say that that arithmetic and dereferencing is very fast since they operate directly on the data.

Qt’s containers are implicitly shared – when you copy an object, only a pointer to the data is copied. When the object is modified, it first creates a deep copy of the data so that it does not affect the other objects. The process of creating a deep copy of the day is called detach’

Since, STL-style iterators are conceptually just pointers, they make modification to the underlying data directly. As a consequence, non-const iterators detach when created using Container::begin() so that other implicitly shared instances do not get affected by the changes. To merely iterate through the container without modifying it, const-iterators should be used. When an iterator is created using Container::constBegin(), the container does not detach.

The implementation of STL style iterators leads to some programming errors and pitfalls:
Problem 1. Any operation that changes the container’s internal data structure will most likely make existing iterators invalid. For example, QVector::append() might cause QVector to reallocate it’s internal array and thus any existing iterator is a dangling pointer. Whether an iterator becomes invalid or not depends on the container and is an implementation detail. For example, a QMap’s iterator remains valid even after the removal of an item as long as the removed item was not the one the iterator is pointing to. The same is true for QHash::erase() which does not rehash unlike QHash::remove(). In general, the thumb rule is to not use an iterator after the container has been changed.

To illustrate:

Problem 2. Creating a copy of a container when a non-const iterator is active has unexpected side effects.

Qt’s containers are implicitly shared and hence vector2 and vector1 share point to the same data. The iterator manipulates this data directly (since iterator is just a pointer). This is counter-intuitive to the nature of value based types which gives the guarantee that values never change behind their back.

Java style iterators

The main purpose of Java style iterators (other than the coding style) is to solve the problems of STL iterators (discussed above). Internally, they are implemented using STL iterators. So, for the purpose of this discussion, it is safe to assume that Java Style iterators also hold pointers but still manage to avert the problems of STL-iterators.

Problem 1 Solution. const (non-mutable) Java style iterators solve the first problem by having the iterator hold a local copy of the container. Internally, the const Java style iterators are implemented using STL iterators created over this copy. By keeping a copy, the const java iterator is safe from changes to the original object since Qt will detach when the original container is modified. This means that you can continue to iterate even after the original object is invalid. To illustrate:

Problem 2 Solution. The non-const (mutable) Java style iterators solve the second problem by making the container non-sharable. A non-sharable container is one that does not share it’s data even with new objects that create a copy of it. To illustrate,

Thanks to non-sharability, problem 2 is averted – writing using the iterator of one object does not overwrite the data of some other object.

QT_STRICT_ITERATORS

By default, it sometimes becomes possible to assign non-const iterators to const-iterators. Thinking of an iterator as a typedef of some pointer type, C++ allows assignment of a non-const pointer to a const pointer. To illustrate:

The above code works but ideally QMap::constFind() should be used since creation of a non-const STL iterator causes a detach (deep-copy). To fix errors such as above at compile time, QT_STRICT_ITERATORS can be defined. This makes Qt define the iterators differently so they don’t cast into each other.

Categories:

• QtInternals