Iterators
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 Container documentation.
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:
QVector<int> vector1;
vector1 << 1 << 2 << 3 << 4;
QVector<int>::const_iterator it = vector1.constBegin();
vector1 << 5 << 6 << 7 << 8; // we change vector1
qDebug() << *it; // oops! it is dangling pointer
Problem 2. Creating a copy of a container when a non-const iterator is active has unexpected side effects.
QVector<int> vector1;
vector1 << 1 << 2 << 3 << 4;
QVector<int>::iterator it = vector1.begin();
QVector<int> vector2 = vector1; // vector2 now shares the data with vector1
*it = 10;
// not just vector1, but vector2 is now modified too!
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:
QVector<int> vector1;
vector1 << 1 << 2 << 3 << 4;
QVectorIterator<int> it(vector1); // 'it' now holds a copy of vector1
vector1 << 5 << 6 << 7 << 8; // vector1 detaches and the local copy inside QVectorIterator is untouched
qDebug() << it.value(); // safe, will print 1. we are only iterating over a copy of vector1, not vector1 itself
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,
QVector v1;
v1 << 1 << 2 << 2;
QVector v2 = v1; // v1 and v2 share the same data thanks to implicit sharing
v1.setSharable(false); // marks v1 as non-sharable (internal API) and makes the container detach (i.e deep copy)
QVector v3 = v1; // v3 gets it's own copy of data since v1 is 'non-sharable'
Thanks to non-sharability, problem 2 is averted - writing using the iterator of one object does not overwrite the data of some other object.
QVector<int> vector1;
vector1 << 1 << 2 << 3 << 4;
QMutableVectorIterator it(vector1); // the iterator holds a pointer to vector1 data and makes vector1 non-sharable
QVector<int> vector2 = vector1; // since vector1 is not sharable, vector2 get it's own copy
it.setValue(10); // only vector1 modified
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:
QMap<QString, QString> map;
QMap<QString, QString>::const_iterator it = map.find("girish"); // code compiles and works fine but find() returns the non-const QMap::iterator that detaches!