Ассоциативные контейнеры

Ассоциативные контейнеры

Ассоциативный контейнер содержит произвольное количество элементов одинакового типа, индексируемых некоторым ключом. Qt содержит два основных класса ассоциативных контейнеров: QМар<К, T> и QHash<K, T>.

QMap<K, T> — это структура данных, которая содержит пары ключ—значение, упорядоченные по возрастанию ключей. Такая организация данных обеспечивает хорошую производительность операций поиска и вставки, а также при проходе данных в порядке их сортировки. Внутренне QMap<K, T> реализуется как слоеный список (skip—list).

Рис. 11.6. Ассоциативный массив, связывающий QString с int.

Простой способ вставки элементов в ассоциативный массив состоит в использовании функции insert():

QMap<QString, int> map;

map.insert("eins", 1);

map.insert("sieben", 7);

map.insert("dreiundzwanzig", 23);

Можно поступить по-другому — просто присвоить значение заданному ключу:

map["eins"] = 1;

map["sieben"] = 7;

map["dreiundzwanzig"] = 23;

Оператор [ ] может использоваться как для вставки, так и для поиска. Но если этот оператор используется для поиска значения, для которого не существует ключа, будет создан новый элемент с данным ключом и пустым значением. Чтобы не создавать случайно пустые элементы, вместо оператора [ ] можно использовать функцию value():

int val = map.value("dreiundzwanzig");

Если ключ отсутствует в ассоциативном массиве, возвращается значение по умолчанию, создаваемое стандартным конструктором данного типа значений. Для базовых типов и указателей возвращается нуль. Мы можем определить другое значение, используемое по умолчанию, с помощью второго аргумента функции value(), например:

int seconds = map.value("delay", 30);

Это эквивалентно следующим операторам:

int seconds = 30;

if (map.contains("delay"))

seconds = map.value("delay");

Типы данных К и T в ассоциативном массиве QMap<K, T> могут быть базовыми типами (например, int и double), указатели и классы, которые имеют стандартный конструктор, конструктор копирования и оператор присваивания. Кроме того, тип К должен обеспечивать оператор operator < (), поскольку QMap<K, T> применяет его для хранения элементов в порядке возрастания значений ключей.

Класс QMap<K, T> имеет две удобные функции, keys() и values(), которые особенно полезны при работе с небольшими наборами данных. Они возвращают списки типа QList ключей и значений ассоциативного массива.

Обычно ассоциативные массивы имеют одно значение для каждого ключа: если новое значение присваивается существующему ключу, старое значение заменяется новым, чтобы не было элементов с одинаковыми ключами. Можно иметь несколько пар ключ—значение с одинаковым ключом, если использовать функцию 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);

}

}