Title: New Container Classes in Qt 4

The next major version of Qt, version 4.0, is expected to be released in June. Qt 4.0 introduces many new features and many APIs that have existed ever since version 1.0 have been redesigned.

In this article, we will review Qt 4's new set of template container classes.

Qt 1.0 was released in 1996 with its own container classes. These classes were used internally by Qt and were part of Qt's public API as an offer to Qt application developers. They existed in two versions: A macro-based implementation and a template-based implementation.

Having been developed before STL became part of the C++ Draft Standard, the Qt 1 container classes had their own original design. First, they were pointer-based, meaning that they stored pointers to objects instead of values. For example, a QList<int> was conceptually equivalent to a std::list<int *>.

In a GUI toolkit, most classes are not copiable (for example, QObject, QWidget and their subclasses), so it made sense to store pointer to these. When storing "value" types such as int and QString, the containers had an "auto-delete" option that you could turn on to give ownership to your objects to the container.

With Qt 2, the need for value-based collections was addressed by a new set of container classes inspired by the STL containers. Qt 2 introduced QValueList<T>, QValueStack<T> and QMap<K, T>, with an API that resembled STL a bit, with some adaptations to Qt's naming conventions (for example, push_back() is called append() in Qt). The iterators met the STL axioms for iterators, ensuring that you could use them in STL algorithms. Qt 2 also provided a few algorithms of its own, such as qHeapSort(), for the benefit of application developers who couldn't rely on the presence of STL.

With Qt 3, we added QValueVector<T> and we renamed the old-style, Qt 1 container classes to include "Ptr" in their name. QList<T> became QPtrList<T>, QVector<T> became QPtrVector<T>, QQueue<T> became QPtrQueue<T>, and QStack<T> became QPtrStack<T>. This step was taken to reduce confusion and to keep beginners away from these classes.

Unlike existing STL implementations, both sets of Qt containers (and in fact most Qt tool classes) use an optimization called implicit data sharing to make copying containers faster.

Implicit sharing 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".

Since Qt's container classes are all implicitly shared, 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> createCityMap()
  {
    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 = createCityMap();

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 createCityMap(std::map<std::string,
  int> &map)
  {
    map.clear();
    map["Tokyo"] = 28025000;
    map["Mexico City"] = 18131000;
    ...
  }

The call then becomes:

  std::map<std::string, int> map;
  createCityMap(map);

Programming like this can rapidly become tedious. It's also error-prone, because the implementor must remember to call clear() at the beginning of the function.

The main drawback with implicit sharing is that some care must be taken when copying containers across threads. Qt 3 includes a class called QDeepCopy that ensures that no two threads reference the same data simultaneously, but it is the application developer's job to remember to use this class when appropriate.

When we started working on Qt 4, the first issue we had to address was that of the container classes and the other tool classes (notably QString). Two of the main goals with Qt 4 were to provide a nicer API that can compete advantageously with newer toolkits and to make Qt more efficient, a requirement from Qt's embedded market.

One option was to deprecate Qt's container classes and to tell our users to use STL. This had many advantages, but also brought its share of issues:

For those reasons, we decided to write our own set of containers for Qt 4, which would replace the previous Qt containers and offer a solid alternative to STL. The new containers have the following advantages:

Qt 4.0 provides the container classes shown in Table 1, overleaf.

Table 2 summarizes the algorithmic complexity of index-based lookups, insertions in the middle, prepending and appending for Qt 4's sequential containers:

From the table above, it might look like insertions in the middle are much faster using QLinkedList<T> than using QList<T>. However, in practice, for lists of about a hundred items, both offer more or less the same speed for insertion in the middle. For lists smaller than that, QList<T> is faster.

The final table, Table 3, covers Qt 4's associative containers.

It is possible to get amortized O(1) behavior on average for insertions into a QHash<Key, T> or a QSet<T> by setting the number of buckets in the internal hash table to a suitably large integer before performing the insertions.

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 <algorithm>). For example, if you want to sort all the 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>. This is useful if you build your software on platforms that don't provide an STL implementation (e.g., on Qt/Embedded).

Each Qt 4 container QXxx has two STL-style iterator classes: QXxx::iterator and QXxx::const_iterator:

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

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<T>, the Java-style iterator classes are QListIterator<T> and QListMutableIterator<T>. 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.

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<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 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, 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 next() and previous() 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<T>). 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<int> with zero:

QList<int> list;
...
QListMutableIterator<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:

QListMutableIterator<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():

QListMutableIterator<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:

QListMutableIterator<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. 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.

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

If you just want to iterate over all the items in a container in order, you can use Qt's foreach keyword. The keyword is a Qt-specific addition to the C++ language, and is implemented using the preprocessor. Its syntax is:

foreach (variable, container)
  statement

For example, here's how to use foreach to iterate over a QLinkedList<QString>:

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

Just like C++'s for loop, the variable used for iteration can be defined within the foreach statement. And like any other C++ loop construct, you can use braces around the body of a foreach loop, and you can use break to leave the loop.

Qt automatically takes a copy of the container when it enters a foreach loop. If you modify the container as you are iterating, that won't affect the loop. (If you don't modify the container, the copy still takes place, but thanks to implicit sharing copying a container is very fast.)