Жасмин Бланшет - QT 4: программирование GUI на С++
Обычно ассоциативные массивы имеют одно значение для каждого ключа: если новое значение присваивается существующему ключу, старое значение заменяется новым, чтобы не было элементов с одинаковыми ключами. Можно иметь несколько пар ключ—значение с одинаковым ключом, если использовать функцию insertMulti() или удобный подкласс QMultiMap<K, T>. QMap<K, T> имеет перегруженную функцию values(const К &), которая возвращает список QList со всеми значениями заданного ключа. Например:
QMultiMap<int, QString> multiMap;
multiMap.insert(1, "one"); multiMap.insert(1, "eins");
multiMap.insert(1, "uno");
QList<QString> vals = multiMap.values(1);
QHash<K, T> — это структура данных, которая хранит пары ключ—значение в хэш—таблице. Ее интерфейс почти совпадает с интерфейсом QMap<K, T>, однако здесь предъявляются другие требования к шаблонному типу К и операции поиска обычно выполняются значительно быстрее, чем в QMap<K, T>. Еще одним отличием является неупорядоченность значений в QHash<K, T>.
Кроме стандартных требований, которым должен удовлетворять любой тип значений, хранимых в контейнере, для типа К в QHash<K, T> должен быть предусмотрен оператор operator == () и должна быть обеспечена глобальная функция qHash(), возвращающая хэш—код для ключа. Qt уже имеет перегрузки функции qHash() для целых типов, указателей, QChar, QString и QByteArray.
QHash<K, T> автоматически выделяет некий первичный объем памяти для своей внутренней хэш—таблицы и изменяет его, когда элементы вставляются или удаляются. Кроме того, можно обеспечить более тонкое управление производительностью с помощью функции reserve(), которая устанавливает ожидаемое количество элементов в хэш—таблице, и функции squeeze(), которая сжимает хэш—таблицу, учитывая текущее количество элементов. Обычно действуют так: вызывают reserve(), обеспечивая максимальное ожидаемое количество элементов, затем добавляют данные и, наконец, вызывают squeeze() для сведения к минимуму расхода памяти, если элементов оказалось меньше, чем ожидалось.
Хэш-таблицы обычно имеют одно значение на каждый ключ, однако одному ключу можно присвоить несколько значений, используя функцию insertMulti() или удобный подкласс QMultiHash<K, T>.
Кроме QHash<K, T> в Qt имеется также класс QCache<K, T>, который может использоваться для создания кэша объектов, связанных с ключом, и контейнер QSet<K>, который хранит только ключи. Оба класса реализуются на основе QHash<K, T> и предъявляют к типу К такие же требования, как и QHash<K, T>.
Для прохода по всем парам ключ—значение, находящимся в ассоциативном контейнере, проще всего использовать итератор в стиле Java. Поскольку итераторы должны обеспечивать доступ и к ключу, и к значению, итераторы в стиле Java работают с ассоциативными контейнерами немного иначе, чем с последовательными контейнерами. Основное отличие проявляется в том, что функции next() и previous() возвращают пару ключ—значение, а не просто одно значение. Компоненты ключа и значения можно извлечь из объекта пары с помощью функций key() и value(). Например:
QMap<QString, int> map;
…
int sum = 0;
QMapIterator<QString, int> i(map);
while (i.hasNext())
sum += i.next().value();
Если требуется получить доступ как к ключу, так и к значению, мы можем просто игнорировать значение, возвращаемое функциями next() и previous(), и использовать функции итератора key() и value(), которые работают с последним пройденным элементом.
QMapIterator<QString, int> i(map);
while (i.hasNext()) {
i.next();
if (i.value() > largestValue) {
largestKey = i.key();
largestValue = i.value();
}
}
Допускающие запись итераторы имеют функцию setValue(), которая модифицирует значение, содержащееся в текущем элементе:
QMutableMapIterator<QString, int> i(map);
while (i.hasNext()) {
i.next();
if (i.value()< 0.0)
i.setValue(-i.value());
}
Итераторы в стиле STL также имеют функции key() и value(). Для неконстантных типов итераторов value() возвращает неконстантную ссылку, позволяя нам изменять значение в ходе просмотра контейнера. Следует отметить, что хотя эти итераторы называются итераторами «в стиле STL», они существенно отличаются от итераторов STL контейнера map<K, T>, которые ссылаются на pair<K, T>.
Оператор цикла foreach также работает с ассоциативными контейнерами, но только с компонентом значение пар ключ—значение. Если нужны как ключи, так и значение, мы можем вызвать функции keys() и values(const К &) во внутреннем цикле foreach:
QMultiMap<QString, int> map;
…
foreach (QString key, map.keys()) {
foreach (int value, map.values(key)) {
do_something(key, value);
}
}
Обобщенные алгоритмы
В заголовочном файле <QtAlgorithms> объявляются глобальные шаблонные функции, которые реализуют основные алгоритмы для контейнеров. Большинство этих функций работают с итераторами в стиле STL.
Заголовочный файл STL <algorithm> содержит более полный набор обобщенных алгоритмов. Эти алгоритмы могут использоваться не только с STL-контейнерами, но и с Qt—контейнерами. Если STL доступен на всех ваших платформах, вероятно, нет причин не использовать STL—алгоритмы, когда в Qt отсутствует эквивалентный алгоритм. Далее мы кратко рассмотрим наиболее важные Qt—алгоритмы.
Алгоритм qFind() выполняет поиск конкретного значения в контейнере. Он принимает «начальный» и «конечный» итераторы и возвращает итератор, ссылающийся на первый подходящий элемент, или «конечный» итератор, если нет подходящих элементов. В представленном ниже примере i устанавливается на list.begin() + 1, a j устанавливается на list.end().
QStringList list;
list << "Emma" << "Karl" << "James" << "Mariette";
QStringList::iterator i = qFind(list.begin(), list.end(), "Karl");
QStringList::iterator j = qFind(list.begin(), list.end(), "Petra");
Алгоритм qBinaryFind() выполняет поиск подобно алгоритму qFind(), за исключением того, что он предполагает упорядоченность элементов в возрастающем порядке и использует двоичный поиск в отличие от линейного поиска в qFind().
Алгоритм qFill() заполняет контейнер конкретным значением:
QLinkedList<int> list(10);
qFill(list.begin(), list.end(), 1009);
Как и другие алгоритмы, основанные на применении итераторов, qFill() может выполняться для части контейнера, если соответствующим образом установить аргументы. В следующем фрагменте программного кода первые пять элементов вектора инициализируются значением 1009, а последние пять элементов — значением 2013:
QVector<int> vect(10);
qFill(vect.begin(), vect.begin() + 5, 1009);
qFill(vect.end() - 5, vect.end(), 2013);
Алгоритм qCopy() копирует значения одного контейнера в другой.
QVector<int> vect(list.count());
qCopy(list.begin(), list.end(), vect.begin());
Алгоритм qCopy() может также использоваться для копирования элементов в рамках одного контейнера, если исходный диапазон и целевой диапазон не перекрываются. В следующем фрагменте программного кода мы заменяем последние два элемента списка первыми двумя элементами:
qCopy(list.begin(), list.begin() + 2, list.end() - 2);
Алгоритм qSort() сортирует элементы контейнера в порядке их возрастания.
qSort(list.begin(), list.end());
По умолчанию qSort() использует оператор < для сравнения элементов. Для сортировки элементов по убыванию передайте qGreater<T>() в качестве третьего аргумента (здесь T — тип элемента контейнера):
qSort(list.begin(), list.end(), qGreater<int>());
Мы можем использовать третий параметр для определения пользовательского критерия сортировки. Например, ниже приводится функция сравнения «меньше, чем», которая выполняет сравнение строк QString без учета регистра:
bool insensitiveLessThan(const QString &str1, const QString &str2)
{
return str1.toLower() < str2.toLower();
}
Тогда вызов qSort() будет таким:
QStringList list;
qSort(list.begin(), list.end(), insensitiveLessThan);
Алгоритм qStableSort() аналогичен qSort(), за исключением того, что он гарантирует сохранение порядка следования одинаковых элементов. Этот алгоритм стоит применять в тех случаях, когда критерий сортировки учитывает только часть значения элемента и пользователь видит результат сортировки. Мы использовали qStableSort() в главе 4 для реализации сортировки в приложении Электронная таблица.
