Qt Template library

Thq Qt Template Library is a set of templates within Qt dealing with containers of objects. It provides a list of objects, a stack of objects, a map (or dictionary) from one type to another, and associated iterators and algorithms.

Qt also contains similar classes that deal with pointers to objects; QValueList vs. QList, etc. Compared to the pointer-based templates, the QTL offers easy copying of the container, real support for classes that e.g. require constructors, expand to much more object code, can often be a bit faster, require that the objects stored can be copied, and finally, have a worse record of compiler problems.

Compared to the STL, the QTL contains only the most important features of the STL, has more regular function naming, has no platform differences, is often a little slower and often expands to less object code.

If you can not make copies of the objects you want to store you are better off with QCollection and friends. They were designed to handle exactly that kind of pointer semantics. This applies for example to all classes derived from QObject. A QObject does not have a copy constructor, so using it as value is impossible. You may choose be store pointers to QObjects in a QValueList, but using QList directly seems to be the better choice for this kind of application domain. QList, like all other QCollection based containers, provides far more sanity checking than a speed-optimized value based container.

If you have objects that implement value semantics, use the Qt template library. Value semantics require at least

• a copy constructor,
• an assignment operator and
• a default constructor, i.e. a constructor that does not take any arguments.

Note that a fast copy constructor is absolutely crucial for a good overall performance of the container, since many copy operations are going to happen.

Examples for value based classes are QRect, QPoint, QSize and all simple C++ types like int, bool or double.

The Qt template library is designed for speed. Especially iterators are extremely fast. On the drawback side, less error checking is done than in the QCollection based containers. A template library container for example does not track associated iterators. This makes certain validity checks, like on removing items, impossible to perform automatically.

Iterators

The Qt template library deals with value objects, not with pointers. For that reason, there is no other way of iterating over containers than using iterators. This is no disadvantage as the size of an iterator matches the size of a normal pointer - 32 or 64 bits depending on your CPU architecture.

To iterate over a container, use a loop like this:

        typedef QValueList<int> List;
        List l;
        for( List::Iterator it = l.begin(); it != l.end(); ++it )
                printf("Number is %i\n",*it);

begin() returns the iterator pointing at the first element, while end() returns an iterator that points after the last element. end() marks an invalid position, it can never be dereferenced. It's the break condition in any iteration, may it be from begin() or fromLast(). For maximum speed, use increment or decrement iterators with the prefix operator (++it, --it) instead of the the postfix one (it++, it--), since the former is slightly faster.

The same concept applies to the other container classes:

        typedef QMap<QString,QString> Map;
        Map map;
        for( Map::Iterator it = map.begin(); it != map.end(); ++it )
                printf("Key=%s Data=%s\n", it.key().ascii(), it.data().ascii() );

        typedef QArray<int> Array;
        Array array;
        for( Array::Iterator it = array.begin(); it != array.end(); ++it )
                printf("Data=%i\n", *it );

There are two kind of iterators, the volatile iterator shown in the examples above and a version that returns a const reference to its current object, the ConstIterator. Const iterators are required whenever the container itself is const, such as a member variable inside a const function. Assigning a ConstIterator to a normal Iterator is not allowed as it would violate const semantics.

Algorithms

The template library defines a number of algorithms that operate on its containers: qHeapSort(), qBubbleSort(), qSwap() and qCopy(). These algorithms are implemented as template functions.

qHeapSort() and qBubbleSort() provide the well known sorting algorithms. You can use them like this:

        typedef QValueList<int> List;
        List l;
        l << 42 << 100 << 1234 << 12 << 8;
        qHeapSort( l );

        List l2;
        l2 << 42 << 100 << 1234 << 12 << 8;
        List::Iterator b = l2.find( 100 );
        List::Iterator e = l2.find( 8 );
        qHeapSort( b, e );

        double arr[] = { 3.2, 5.6, 8.9 };
        qHeapSort( arr, arr + 3 );

The first example sorts the entire list. The second one sorts all elements enclosed in the two iterators, namely 100, 1234 and 12. The third example shows that iterators act like pointers and can be treated as such.

Naturally, the sorting templates won't work with const iterators.

Another utility is qSwap(). It exchanges the values of two variables:

        QString second( "Einstein" );
        QString name( "Albert" );
        qSwap( second, name );

Another template function is qCopy(). It copies a container or a slice of it to an OutputIterator, in this case a QTextOStreamIterator:

        typedef QValueList<int> List;
        List l;
        l << 100 << 200 << 300;
        QTextOStream str( stdout );
        qCopy( l, QTextOStreamIterator( str ) );

In addition, you can use any Qt template library iterator as the OutputIterator. Just make sure that the right hand of the iterator has as many elements present as you want to insert. The following example illustrates this:

        QStringList l1, l2;
        l1 << "Weis" << "Ettrich" << "Arnt" << "Sue";
        l2 << "Torben" << "Matthias";
        qCopy( l2, l1.begin() );

At the end of this code fragment, the List l1 contains "Torben", "Matthias", "Arnt" and "Sue", with the prior contents being overwritten. Another flavor of qCopy() takes three arguments to make it possible to copy a slice of a container:

        typedef QValueList<int> List;
        List l;
        l << 42 << 100 << 1234 << 12 << 8;
        List::Iterator b = l.find( 100 );
        List::Iterator e = l.find( 8 );
        QTextOStream str( stdout );
        qCopy( b, e, QTextOStreamIterator( str ) );

If you write new algorithms, consider writing them as template functions in order to make them usable with as many containers possible. In the above example, you could just as easily print out a standard C++ array with qCopy():

        int arr[] = { 100, 200, 300 };
        QTextOStream str( stdout );
        qCopy( arr, arr + 3, QTextOStreamIterator( str ) );

Streaming

All mentioned containers can be serialized with the respective streaming operators. Here is an example.

        QDataStream str(...);
        QValueList<QRect> l;
        // ... fill the list here
        str << l;

The container can be read in again with:

        QValueList<QRect> l;
        str >> l;

The same applies to QStringList, QValueStack and QMap.

Classes:

• QMap (Value based template class that provides a dictionary)
• QMapConstIterator (Iterator for QMap)
• QMapIterator (Iterator for QMap)
• QStringList (A list of strings)
• QValueList (Value based template class that provides doubly linked lists)
• QValueListConstIterator (Iterator for QValueList)
• QValueListIterator (Iterator for QValueList)
• QValueStack (Value based template class that provides a stack)