Читать «Базовые алгоритмы Qt 4 (Qt 4"s Generic Algorithms)» онлайн

Qt предоставляет собственные алгоритмы потому, что некоторые платформы (например, embedded Linux) не предоставляет реализацию STL. Алгоритмы используются внутри Qt и доступны его пользователям.

Два вида сортировки

Stable сортировка имеет свойство сохранения порядка похожих элементов при сортировке. Это полезно, когда имеешь дело с элементами, которые сравниваются между собой, даже если они не полностью эквивалентны. Например, если сортируется список адресов по фамилии, можно использовать qStableSort (), чтобы сохранить начальный порядок людей с одинаковой фамилией. Обычная сортировка не гарантирует этого.

Линейный и бинарный поиск

Алгоритмы qFind() и qBinaryFind() в качестве параметров получают итераторы диапазона и значение, а возвращают итератор на элемент, который соответствует данному значению, или "end" итератор, если не найдено ни одного элемента. Алгоритм бинарного поиска намного быстрее чем линейный алгоритм, но он может работать только с сортированными диапазонами.

Если значение встречается более одного раза, qFind() вернет итератор на первый элемент, тогда как qBinaryFind() на произвольный.

Для большей гибкости, Qt 4 предоставляет qLowerBound() и qUpperBound(). Как и qBinaryFind(), они работают с сортированным диапазоном. Если значение найдено, qLowerBound() вернет итератор на первый найденный элемент, а qUpperBound() вернет итератор, указывающий на следующий за последним элемент. Если значение не найдено, они вернут итератор на позицию, в которую данный элемент может быть вставлен.

Частый пример использования qLowerBound() и qUpperBound() это проход по всем вхождениям значения:

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;

}

Пример: статическая Map

Сначала, мы определяем структуру для имен, а так же операторы сравнения для поиска вхождения фамилий:

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().