Trolltech | Documentation | Qt Quarterly

Qt 4's Generic Algorithms
by Morten Sørvig
Qt has provided a set of template-based algorithms that implement the most useful STL algorithms, since version 2. In this article, we'll have a look at some of the algorithms offered by Qt 4's <QtAlgorithms> header.
Qt provides its own algorithms because some platforms (e.g., embedded Linux) don't provide an implementation of STL. The algorithms are used internally by Qt and are available to Qt users.

It is perfectly possible to mix and match the STL and Qt implementations of containers and algorithms. For example, you can use the std::find() algorithm on a QList<T>, or qSort() on a std::vector<T>. This works because the algorithms are based on STL-style iterators and the Qt containers' iterator classes meet the STL requirements.

Two Sorts of Sort

The qSort() and qStableSort() algorithms can be used to sort the items of a QList<T>, a QVector<T>, or even a plain C++ array in increasing order. With Qt 4, it is also possible to specify a custom comparison operator (instead of operator<()).

Stable sort has the property that the order of equal elements is preserved when sorting. This is useful when dealing with elements that compare "equal" even when they aren't entirely equivalent. For example, if you sort an address list on last name, you can use qStableSort() to preserve the initial order of people with the same last name. The normal sort doesn't offer this guarantee.

Linear and Binary Search

The qFind() and qBinaryFind() algorithms take an iterator range and a value and return an iterator to an item that matches the given value, or the "end" iterator if no such item was found. The binary search algorithm is much faster than the linear algorithm, but it can only operate on sorted ranges.

If the value occurs more than once, qFind() returns an iterator to the first occurrence, whereas qBinaryFind() points to an arbitrary occurrence.

For more flexibility, Qt 4 also provides qLowerBound() and qUpperBound(). Like qBinaryFind(), they operate on a sorted range. If the value is found, qLowerBound() returns an iterator to the first item that matches and qUpperBound() returns an iterator "one past the last" item that matched. If the value isn't found, they return an iterator to the position where that value would have been if it had been there. You can then use this iterator to insert the value, for example.

One common use of qLowerBound() to qUpperBound() is for iterating over all the occurrences of a value:

    QStringList list;
    QStringList::iterator i, j;
    ...
    i = qLowerBound(list.begin(), list.end(), value);
    j = qUpperBound(list.begin(), list.end(), value);
    
    while (i != j) {
        processItem(*i);
        ++i;
    }

Example: A Static Map

In this section, we will use binary search to implement a "static const" map. The data structure is entirely stored in read-only memory and consists of "family name, given name" pairs that are sorted on family name. Compared to using QMap or QHash, this approach saves memory and makes sense in highly optimized applications or libraries.

First, we define a struct for holding a name, as well as less-than comparison operators for looking up an entry by family name:

    struct Entry {
        const char *familyName;
        const char *givenName;
    };
    
    bool operator<(const Entry &entry, const QString &family)
    {
        return entry.familyName < family;
    }
    
    bool operator<(const QString &family, const Entry &entry)
    {
        return family < entry.familyName;
    }

Then we declare our data:

    static const int NumEntries = 4;
    static const Entry entries[NumEntries] = {
        { "Deitel", "Harvey" },
        { "Deitel", "Paul" },
        { "Jobs", "Steve" },
        { "Torvalds", "Linus" }
    };
    static const Entry * const end = entries + NumEntries;

The end pointer marks the end of the array.

    bool contains(const QString &family)
    {
        return qBinaryFind(entries, end, family) != end;
    }

Now that everything is in place, implementing contains() is trivial. Since C++ pointers meet the criteria of an STL random-access iterator, we can use them in conjunction with qBinaryFind().

    QString givenName(const QString &family)
    {
        const Entry *i = qBinaryFind(entries, end, family);
        if (i == end)
            return "";
        return i->givenName;
    }

The givenName() function returns the first name of a person with the given family name. For example, if we pass "Torvalds" as the argument, we get back "Linus"; if we pass "Deitel", the function returns either "Harvey" or "Paul".

    QStringList givenNames(const QString &family)
    {
        const Entry *i = qLowerBound(entries, end, family);
        const Entry *j = qUpperBound(entries, end, family);
        QStringList result;
        while (i != j)
            result += (i++)->givenName + (" " + family);
        return result;
    }

The givenNames() function returns the list of people belonging to a certain family. It illustrates the use of qLowerBound() and qUpperBound() to iterate through a range of values.


This document is licensed under the Creative Commons Attribution-Share Alike 2.5 license.

Copyright © 2005 Trolltech Trademarks