<QtAlgorithms> - Generic Algorithms

Functions

Qt provides a number of global template functions in <QtAlgorithms> that work on containers and perform well-know algorithms. You can use these algorithms with any container class that provides STL-style iterators, including Qt's QList, QLinkedList, QVector, QMap, and QHash classes.

These functions have taken their inspiration from similar functions available in the STL <algorithm> header. Most of them have a direct STL equivalent; for example, qCopyBackward() is the same as STL's copy_backward() algorithm.

If STL is available on all your target platforms, you can use the STL algorithms instead of their Qt counterparts. One reason why you might want to use the STL algorithms is that STL provides dozens and dozens of algorithms, whereas Qt only provides the most important ones, making no attempt to duplicate functionality that is already provided by the C++ standard.

Most algorithms take STL-style iterators as parameters. The algorithms are generic in the sense that they aren't bound to a specific iterator class; you can use them with any iterators that meet a certain set of requirements.

Let's take the qFill() algorithm as an example. Unlike QVector, QList has no fill() function that can be used to fill a list with a particular value. If you need that functionality, you can use qFill():

 QStringList list;
 list << "one" << "two" << "three";

 qFill(list.begin(), list.end(), "eleven");
 // list: [ "eleven", "eleven", "eleven" ]

qFill() takes a begin iterator, an end iterator, and a value. In the example above, we pass list.begin() and list.end() as the begin and end iterators, but this doesn't have to be the case:

 qFill(list.begin() + 1, list.end(), "six");
 // list: [ "eleven", "six", "six" ]

Different algorithms can have different requirements for the iterators they accept. For example, qFill() accepts two forward iterators. The iterator types required are specified for each algorithm. If an iterator of the wrong type is passed (for example, if QList::ConstIterator is passed as an output iterator), you will always get a compiler error, although not necessarily a very informative one.

Some algorithms have special requirements on the value type stored in the containers. For example, qEqual() requires that the value type supports operator==(), which it uses to compare items. Similarly, qDeleteAll() requires that the value type is a non-const pointer type (for example, QWidget *). The value type requirements are specified for each algorithm, and the compiler will produce an error if a requirement isn't met.

 QChar resolveEntity(const QString &entity)
 {
     static const QLatin1String name_table[] = {
         "AElig", "Aacute", ..., "zwnj"
     };
     static const ushort value_table[] = {
         0x0061, 0x00c1, ..., 0x200c
     };
     int N = sizeof(name_table) / sizeof(name_table[0]);

     const QLatin1String *name = qBinaryFind(name_table, name_table + N,
                                             entity);
     int index = name - name_table;
     if (index == N)
         return QChar();

     return QChar(value_table[index]);
 }

 QChar resolveEntity(const QString &entity)
 {
     static QMap<QString, int> entityMap;

     if (!entityMap) {
         entityMap.insert("AElig", 0x0061);
         entityMap.insert("Aacute", 0x00c1);
         ...
         entityMap.insert("zwnj", 0x200c);
     }
     return QChar(entityMap.value(entity));
 }

 QVector<int> vect;
 vect << 3 << 3 << 6 << 6 << 6 << 8;

 QVector<int>::iterator i =
         qBinaryFind(vect.begin(), vect.end(), 6);
 // i == vect.begin() + 2 (or 3 or 4)

 QStringList list;
 list << "one" << "two" << "three";

 QVector<QString> vect1(3);
 qCopy(list.begin(), list.end(), vect1.begin());
 // vect: [ "one", "two", "three" ]

 QVector<QString> vect2(8);
 qCopy(list.begin(), list.end(), vect2.begin() + 2);
 // vect: [ "", "", "one", "two", "three", "", "", "" ]

 QStringList list;
 list << "one" << "two" << "three";

 QVector<QString> vect(5);
 qCopyBackward(list.begin(), list.end(), vect.end());
 // vect: [ "", "", "one", "two", "three" ]

 QList<int> list;
 list << 3 << 3 << 6 << 6 << 6 << 8;

 int countOf6 = 0;
 qCount(list.begin(), list.end(), 6, countOf6);
 // countOf6 == 3

 int countOf7 = 0;
 qCount(list.begin(), list.end(), 7, countOf7);
 // countOf7 == 0

 QList<Employee *> list;
 list.append(new Employee("Blackpool", "Stephen"));
 list.append(new Employee("Twist", "Oliver"));

 qDeleteAll(list.begin(), list.end());
 list.clear();

 QStringList list;
 list << "one" << "two" << "three";

 QVector<QString> vect(3);
 vect[0] = "one";
 vect[1] = "two";
 vect[2] = "three";

 bool ret1 = qEqual(list.begin(), list.end(), vect.begin());
 // ret1 == true

 vect[2] = "seven";
 bool ret2 = qEqual(list.begin(), list.end(), vect.begin());
 // ret2 == false

 QStringList list;
 list << "one" << "two" << "three";

 qFill(list.begin(), list.end(), "eleven");
 // list: [ "eleven", "eleven", "eleven" ]

 qFill(list.begin() + 1, list.end(), "six");
 // list: [ "eleven", "six", "six" ]

 QStringList list;
 list << "one" << "two" << "three";

 QStringList::iterator i1 = qFind(list.begin(), list.end(), "two");
 // i1 == list.begin() + 1

 QStringList::iterator i2 = qFind(list.begin(), list.end(), "seventy");
 // i2 == list.end()

 QList<int> list;
 list << 33 << 12 << 68 << 6 << 12;
 qSort(list.begin(), list.end(), qGreater<int>());
 // list: [ 68, 33, 12, 12, 6 ]

 QList<int> list;
 list << 33 << 12 << 68 << 6 << 12;
 qSort(list.begin(), list.end(), qLess<int>());
 // list: [ 6, 12, 12, 33, 68 ]

 QList<int> list;
 list << 3 << 3 << 6 << 6 << 6 << 8;

 QList<int>::iterator i = qLowerBound(list.begin(), list.end(), 5);
 list.insert(i, 5);
 // list: [ 3, 3, 5, 6, 6, 6, 8 ]

 i = qLowerBound(list.begin(), list.end(), 12);
 list.insert(i, 12);
 // list: [ 3, 3, 5, 6, 6, 6, 8, 12 ]

 QVector<int> vect;
 vect << 3 << 3 << 6 << 6 << 6 << 8;
 QVector<int>::iterator begin6 =
         qLowerBound(vect.begin(), vect.end(), 6);
 QVector<int>::iterator end6 =
         qUpperBound(begin6, vect.end(), 6);

 QVector<int>::iterator i = begin6;
 while (i != end6) {
     *i = 7;
     ++i;
 }
 // vect: [ 3, 3, 7, 7, 7, 8 ]

 QList<int> list;
 list << 33 << 12 << 68 << 6 << 12;
 qSort(list.begin(), list.end());
 // list: [ 6, 12, 12, 33, 68 ]

 bool caseInsensitiveLessThan(const QString &s1, const QString &s2)
 {
     return s1.toLower() < s2.toLower();
 }

 int doSomething()
 {
     QStringList list;
     list << "AlPha" << "beTA" << "gamma" << "DELTA";
     qSort(list.begin(), list.end(), caseInsensitiveLessThan);
     // list: [ "AlPha", "beTA", "DELTA", "gamma" ]
 }

 QList<int> list;
 list << 33 << 12 << 68 << 6 << 12;
 qSort(list.begin(), list.end(), qGreater<int>());
 // list: [ 68, 33, 12, 12, 6 ]

 QStringList list;
 list << "AlPha" << "beTA" << "gamma" << "DELTA";

 QMap<QString, QString> map;
 foreach (QString str, list)
     map.insert(str.toLower(), str);

 list = map.values();

 QList<int> list;
 list << 33 << 12 << 68 << 6 << 12;
 qStableSort(list.begin(), list.end());
 // list: [ 6, 12, 12, 33, 68 ]

 bool caseInsensitiveLessThan(const QString &s1, const QString &s2)
 {
     return s1.toLower() < s2.toLower();
 }

 int doSomething()
 {
     QStringList list;
     list << "AlPha" << "beTA" << "gamma" << "DELTA";
     qStableSort(list.begin(), list.end(), caseInsensitiveLessThan);
     // list: [ "AlPha", "beTA", "DELTA", "gamma" ]
 }

 QList<int> list;
 list << 33 << 12 << 68 << 6 << 12;
 qStableSort(list.begin(), list.end(), qGreater<int>());
 // list: [ 68, 33, 12, 12, 6 ]

 double pi = 3.14;
 double e = 2.71;

 qSwap(pi, e);
 // pi == 2.71, e == 3.14

 QList<int> list;
 list << 3 << 3 << 6 << 6 << 6 << 8;

 QList<int>::iterator i = qUpperBound(list.begin(), list.end(), 5);
 list.insert(i, 5);
 // list: [ 3, 3, 5, 6, 6, 6, 8 ]

 i = qUpperBound(list.begin(), list.end(), 12);
 list.insert(i, 12);
 // list: [ 3, 3, 5, 6, 6, 6, 8, 12 ]

 QVector<int> vect;
 vect << 3 << 3 << 6 << 6 << 6 << 8;
 QVector<int>::iterator begin6 =
         qLowerBound(vect.begin(), vect.end(), 6);
 QVector<int>::iterator end6 =
         qUpperBound(vect.begin(), vect.end(), 6);

 QVector<int>::iterator i = begin6;
 while (i != end6) {
     *i = 7;
     ++i;
 }
 // vect: [ 3, 3, 7, 7, 7, 8 ]