Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms)

   Qt предоставляет ряд алгоритмов на основе шаблона, которые реализуют самые полезные алгоритмы STL, начиная с версии 2. В этой статье, мы рассмотрим некоторые из алгоритмов, предлагаемых в Qt 4 <QtAlgorithms>.
 
   Qt предоставляет собственные алгоритмы потому, что некоторые платформы (например, embedded Linux) не предоставляет реализацию STL. Алгоритмы используются внутри Qt и доступны его пользователям.
   Возможно смешивание реализаций STL и Qt контейнеров и алгоритмов. Например, вы можете использовать алгоритм std::find() для QList<T>, или qSort() для std::vector<T>. Это работает потому, что алгоритмы основаны на итераторах STL-стиля, и итераторы контейнеров классов Qt отвечают требованиям STL.

QList<T>, QVector<T> или в любом динамическом C++ массиве. С Qt 4, также возможно определить любой оператор сравнения (вместо operator<()).
   Stable сортировка имеет свойство сохранения порядка похожих элементов при сортировке. Это полезно, когда имеешь дело с элементами, которые сравниваются между собой, даже если они не полностью эквивалентны. Например, если сортируется список адресов по фамилии, можно использовать qStableSort (), чтобы сохранить начальный порядок людей с одинаковой фамилией. Обычная сортировка не гарантирует этого.

QMapили QHash, этот подход экономит память и имеет смысл в высоко оптимизированных приложениях или библиотеках.
   Сначала, мы определяем структуру для имен, а так же операторы сравнения для поиска вхождения фамилий:
    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;
    }
   Затем объявляем наши данные:
    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;
   Указатель end отмечает конец массива.
    bool contains(const QString &family)
    {
    return qBinaryFind(entries, end, family) != end;
    }
   Теперь, когда все на месте, реализация contains() тривиальна. Так как C++ указатели отвечают критериям STL итераторов произвольного доступа, мы можем использовать их в связке с qBinaryFind().
    QString givenName(const QString &family)
    {
    const Entry *i = qBinaryFind(entries, end, family);
    if (i == end)
    return "";
    return i->givenName;
    }
   Функция givenName() возвращает имя человека с данной фамилией. Например, если мы передаем в качестве аргумента "Torvalds", мы получаем "Linus"; если мы передаем "Deitel", функция возвращает "Harvey" или "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;
    }
   Функция givenNames() возвращает список людей, принадлежащих определенной семье. Здесь показано использование qLowerBound() и qUpperBound().