Текст книги "Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms)"
Автор книги: Morten Sшrvig
Жанр:
Программирование
сообщить о нарушении
Текущая страница: 1 (всего у книги 1 страниц)
Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms)
Qt предоставляет ряд алгоритмов на основе шаблона, которые реализуют самые полезные алгоритмы STL, начиная с версии 2. В этой статье, мы рассмотрим некоторые из алгоритмов, предлагаемых в Qt 4
Qt предоставляет собственные алгоритмы потому, что некоторые платформы (например, embedded Linux) не предоставляет реализацию STL. Алгоритмы используются внутри Qt и доступны его пользователям.
Возможно смешивание реализаций STL и Qt контейнеров и алгоритмов. Например, вы можете использовать алгоритм std::find() для QList
Два вида сортировки
Алгоритмы qSort() и qStableSort()могут быть использованы при сортировке элементов QList
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
В этой секции, мы будем использовать бинарный поиск, для реализации «static const» map. Структура данных полностью хранится в памяти и состоит из пары «фамилия, имя», которые отсортированы по фамилии. По сравнению с использованием 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().
