Классы контейнеров

Введение

Библиотека Qt предоставляет набор шаблонизированных классов-контейнеров общего назначения. Эти классы могут использоваться для хранения элементов заданного типа. Например, если вам нужен изменяемый массив QStringов, используйте QList<QString>.

Эти классы-контейнеры разработаны, чтобы быть более лёгкими, безопасными и простыми в использовании, чем контейнеры STL. Если вы не знакомы со STL или предпочитаете работать «по-Qt», вы можете использовать эти классы вместо классов STL.

Классы-контейнеры являются неявными общими, они реентерабельны, и оптимизированы для скорости, низкого потребления памяти и минимального расширения встроенного кода, что приводит к более компактным исполняемым файлам. Кроме того, они потокобезопасны в ситуациях, когда они используются в качестве контейнеров только для чтения всеми потоками, используемыми для доступа к ним.

Контейнеры предоставляют итераторы для обхода. Итераторы STL-стиля являются наиболее эффективными и могут быть использованы вместе с общими алгоритмами Qt и STL . Итераторы Java-стиля предоставляются для обратной совместимости.

Примечание: С Qt 5.14 для большинства классов-контейнеров доступны конструкторы диапазонов. QMultiMap является заметным исключением. Их использование рекомендуется вместо различных методов from/to. Например:

QList<int> list { 1, 2, 3, 4, 4, 5 };
QSet<int> set(list.begin(), list.end());
/*
    Will generate a QSet containing 1, 2, 3, 4, 5.
*/

Классы контейнеров

Qt предоставляет следующие последовательные контейнеры: QList, QStack и QQueue. Для большинства приложений QList является лучшим типом для использования. Он обеспечивает очень быстрый добавление элементов. Если вам действительно нужна связанный список, используйте std::list. QStack и QQueue являются вспомогательными классами, которые обеспечивают семантику LIFO и FIFO.

Qt также предоставляет следующие ассоциативные контейнеры: QMap, QMultiMap, QHash, QMultiHash и QSet. Контейнеры «Multi» удобно поддерживают несколько значений, связанных с одним ключом. Контейнеры «Hash» обеспечивают более быстрый поиск, используя функцию хеширования вместо бинарного поиска в отсортированном наборе.

В качестве особых случаев классы QCache и QContiguousCache обеспечивают эффективный поиск по хешу объектов в ограниченном кэше.

Контейнеры могут быть вложены. Например, вполне возможно использовать QMap<QString, QList<int>>, где тип ключа – QString, а тип значения – QList<int>.

Контейнеры определены в отдельных заголовочных файлах с таким же именем, как и контейнер (например, <QList>). Для удобства контейнеры объявлены вперёд в <QtContainerFwd>.

Значения, хранящиеся в различных контейнерах, могут быть любого присваиваемого типа данных. Для этого тип должен предоставлять конструктор копирования и оператор присваивания. Для некоторых операций также требуется конструктор по умолчанию. Это охватывает большинство типов данных, которые вы, вероятно, захотите сохранить в контейнере, включая базовые типы, такие как int и double, указатели и типы данных Qt, такие как QString, QDate и QTime, но не охватывает QObject или любой подкласс QObject (QWidget, QDialog, QTimer и т.д.). Если вы попытаетесь создать QList<QWidget>, компилятор сообщит, что конструктор копирования и операторы присваивания для QWidget отключены. Если вы хотите сохранить такие объекты в контейнере, сохраняйте их в виде указателей, например, как QList<QWidget *>.

Вот пример пользовательского типа данных, который удовлетворяет требованию присваиваемого типа данных:

class Employee
{
public:
    Employee() {}
    Employee(const Employee &other);

    Employee &operator=(const Employee &other);

private:
    QString myName;
    QDate myDateOfBirth;
};

Если мы не предоставим конструктор копирования или оператор присваивания, C++ предоставит реализацию по умолчанию, которая выполнит копирование по членам. В приведённом выше примере этого было бы достаточно. Также, если вы не предоставите никаких конструкторов, C++ предоставит конструктор по умолчанию, который инициализирует его члены с использованием конструкторов по умолчанию. Несмотря на то, что этот тип данных не предоставляет явных конструкторов или операторов присваивания, его можно хранить в контейнере:

struct Movie
{
    int id;
    QString title;
    QDate releaseDate;
};

У некоторых контейнеров есть дополнительные требования к типам данных, которые они могут хранить. Например, тип ключа QMap<Key, T> должен предоставлять operator<(). Такие специальные требования документированы в подробном описании класса. В некоторых случаях у определённых функций есть особые требования; они описаны на основе каждой функции. Компилятор всегда будет выдавать ошибку, если требование не выполнено.

Контейнеры Qt предоставляют операторы <<() и >>(), чтобы их можно было легко читать и записывать с помощью QDataStream. Это означает, что типы данных, хранящиеся в контейнере, также должны поддерживать операторы <<() и >>(). Обеспечить такую поддержку просто; вот как мы могли бы это сделать для структуры Movie выше:

QDataStream &operator<<(QDataStream &out, const Movie &movie)
{
    out << (quint32)movie.id << movie.title
        << movie.releaseDate;
    return out;
}

QDataStream &operator>>(QDataStream &in, Movie &movie)
{
    quint32 id;
    QDate date;

    in >> id >> movie.title >> date;
    movie.id = (int)id;
    movie.releaseDate = date;
    return in;
}

В документации некоторых функций класса контейнера упоминаются значения, созданные по умолчанию; например, QList автоматически инициализирует свои элементы значениями, созданными по умолчанию, и QMap::value() возвращает значение, созданное по умолчанию, если указанный ключ отсутствует в словаре. Для большинства типов значений это просто означает, что значение создаётся с помощью конструктора по умолчанию (например, пустая строка для QString). Но для примитивных типов, таких как int и double, а также для указателей, язык C++ не определяет никакой инициализации; в этих случаях контейнеры Qt автоматически инициализируют значение нулём.

Классы итераторов

Итераторы предоставляют единый способ доступа к элементам в контейнере. Классы контейнеров Qt предоставляют два типа итераторов: итераторы STL-стиля и итераторы Java-стиля. Итераторы обоих типов становятся недействительными, когда данные в контейнере изменяются или отделяются от неявных общих копий из-за вызова неконстантного члена функции.

Итераторы STL-стиля

Итераторы STL-стиля доступны с выпуска Qt 2.0. Они совместимы с общими алгоритмами Qt и STL и оптимизированы для скорости.

Для каждого класса контейнера существует два типа итераторов STL-стиля: один, который предоставляет доступ только для чтения, и один, который предоставляет доступ для чтения и записи. Следует использовать итераторы только для чтения, когда это возможно, потому что они быстрее, чем итераторы для чтения и записи.

API итераторов STL моделируется на основе указателей в массиве. Например, оператор ++ перемещает итератор к следующему элементу, а оператор * возвращает элемент, на который указывает итератор. Фактически, для QList и QStack, хранящих элементы в смежных позициях памяти, тип итератора является просто typedef для T *, а тип const_iterator — просто typedef для const T *.

В данном обсуждении мы сосредоточимся на QList и QMap. Типы итераторов для QSet имеют точно такой же интерфейс, как и итераторы QList; аналогично, типы итераторов для QHash имеют тот же интерфейс, что и итераторы QMap.

Вот типичный цикл для итерации по всем элементам QList<QString> в порядке и преобразования их в нижний регистр:

QList<QString> list;
list << "A" << "B" << "C" << "D";

QList<QString>::iterator i;
for (i = list.begin(); i != list.end(); ++i)
    *i = (*i).toLower();

Итераторы в стиле STL указывают непосредственно на элементы. Функция begin() контейнера возвращает итератор, указывающий на первый элемент в контейнере. Функция end() контейнера возвращает итератор на воображаемый элемент, находящийся на одну позицию после последнего элемента в контейнере. end() обозначает недопустимую позицию; её никогда нельзя использовать для разыменования. Обычно она используется в условии выхода из цикла. Если список пуст, begin() равен end(), поэтому цикл никогда не выполняется.

На диаграмме ниже показаны допустимые позиции итераторов в виде красных стрелок для списка, содержащего четыре элемента:

Обратная итерация с помощью итератора в стиле STL выполняется с помощью обратных итераторов:

QList<QString> list;
list << "A" << "B" << "C" << "D";

QList<QString>::reverse_iterator i;
for (i = list.rbegin(); i != list.rend(); ++i)
    *i = i->toLower();

В предыдущих фрагментах кода мы использовали унарный оператор * для извлечения элемента (типа QString), хранящегося в определенной позиции итератора, и затем вызывали QString::toLower() на нём. Большинство компиляторов C++ также позволяют нам написать i->toLower(), но некоторые нет.

Для чтения только для доступа вы можете использовать const_iterator, constBegin() и constEnd(). Например:

QList<QString>::const_iterator i;
for (i = list.constBegin(); i != list.constEnd(); ++i)
    qDebug() << *i;

Следующая таблица обобщает API итераторов в стиле STL:

Операторы ++ и -- доступны как префиксные (++i, --i) и постфиксные (i++, i--) операторы. Префиксные версии изменяют итераторы и возвращают ссылку на изменённый итератор; постфиксные версии создают копию итератора до его изменения и возвращают эту копию. В выражениях, где значение возврата игнорируется, рекомендуется использовать префиксные операторы (++i, --i), так как они немного быстрее.

Для типов итераторов без const значение возвращаемого унарного оператора * может быть использовано в левой части оператора присваивания.

Для QMap и QHash оператор * возвращает компонент значения элемента. Если вам нужно получить ключ, вызовите key() на итераторе. Для симметрии, типы итераторов также предоставляют функцию value() для получения значения. Например, вот как мы можем вывести все элементы QMap в консоль:

QMap<int, int> map;
...
QMap<int, int>::const_iterator i;
for (i = map.constBegin(); i != map.constEnd(); ++i)
    qDebug() << i.key() << ':' << i.value();

Благодаря неявной совместной работе, для функции очень недорого вернуть копию контейнера по значению. API Qt содержит десятки функций, которые возвращают QList или QStringList по значению (например, QSplitter::sizes()). Если вы хотите итерироваться по этим значениям с помощью STL-итератора, всегда следует создавать копию контейнера и итерироваться по копии. Например:

// RIGHT
const QList<int> sizes = splitter->sizes();
QList<int>::const_iterator i;
for (i = sizes.begin(); i != sizes.end(); ++i)
    ...

// WRONG
QList<int>::const_iterator i;
for (i = splitter->sizes().begin();
        i != splitter->sizes().end(); ++i)
    ...

Эта проблема не возникает с функциями, возвращающими константную или неконстантную ссылку на контейнер.

Проблема с неявной совместной работой и итераторами

Неявная совместная работа имеет ещё одно следствие для итераторов в стиле STL: следует избегать копирования контейнера, пока итераторы активны на этом контейнере. Итераторы указывают на внутреннюю структуру, и при копировании контейнера необходимо очень осторожно обращаться с вашими итераторами. Например:

QList<int> a, b;
a.resize(100000); // make a big list filled with 0.

QList<int>::iterator i = a.begin();
// WRONG way of using the iterator i:
b = a;
/*
    Now we should be careful with iterator i since it will point to shared data
    If we do *i = 4 then we would change the shared instance (both vectors)
    The behavior differs from STL containers. Avoid doing such things in Qt.
*/

a[0] = 5;
/*
    Container a is now detached from the shared data,
    and even though i was an iterator from the container a, it now works as an iterator in b.
    Here the situation is that (*i) == 0.
*/

b.clear(); // Now the iterator i is completely invalid.

int j = *i; // Undefined behavior!
/*
    The data from b (which i pointed to) is gone.
    This would be well-defined with STL containers (and (*i) == 5),
    but with QList this is likely to crash.
*/

Приведённый выше пример показывает проблему только с QList, но эта проблема существует для всех контейнеров Qt с неявной совместной работой.

Итераторы в стиле Java

Итераторы в стиле Java были введены в Qt 4. Их API моделируется на основе классов итераторов Java. Новый код должен отдавать предпочтение итераторам в стиле STL.

Ключевые слова контейнеров

Ключевое слово foreach

Ключевое слово foreach не рекомендуется, новый код должен отдавать предпочтение циклам C++11 с основанными на диапазонах циклами.

Ключевое слово forever

В дополнение к foreach, Qt также предоставляет псевдоключевое слово forever для бесконечных циклов:

forever {
    ...
}

Если вы беспокоитесь о загрязнении пространства имён, вы можете отключить эти макросы, добавив следующую строку в ваш .pro файл:

CONFIG += no_keywords

Примечание: Альтернативные макросы Q_FOREACH и Q_FOREVER остаются определёнными независимо.

Другие классы, похожие на контейнеры

Qt включает другие шаблоны классов, которые в какой-то степени напоминают контейнеры. Эти классы не предоставляют итераторов и не могут быть использованы с ключевым словом foreach.

• QCache<Ключ, T> предоставляет кэш для хранения объектов определённого типа T, связанных с ключами типа Ключ.
• QContiguousCache<T> предоставляет эффективный способ кеширования данных, которые обычно обращаются к данным в смежных местах.

Дополнительные типы, не являющиеся шаблонами, которые конкурируют с шаблонами контейнеров Qt, это QBitArray, QByteArray, QString и QStringList.

Вычислительная сложность

Вычислительная сложность связана со скоростью (или медленностью) каждой функции по мере увеличения количества элементов в контейнере. Например, вставка элемента в середину std::list — это крайне быстрая операция, независимо от количества элементов в списке. С другой стороны, вставка элемента в середину QList потенциально очень дорога, если QList содержит много элементов, так как половина элементов должна быть перемещена на одну позицию в памяти.

Для описания вычислительной сложности мы используем следующую терминологию, основанную на записи «big Oh»:

• Постоянное время: O(1). Функция считается выполняемой за постоянное время, если она требует одинакового времени независимо от того, сколько элементов присутствует в контейнере. Примером является QList::push_back().
• Логарифмическое время: O(log n). Функция, выполняющаяся за логарифмическое время, — это функция, время выполнения которой пропорционально логарифму количества элементов в контейнере. Примером является алгоритм бинарного поиска.
• Линейное время: O(n). Функция, выполняющаяся за линейное время, будет выполняться за время, прямо пропорциональное количеству элементов, хранящихся в контейнере. Примером является QList::insert().
• Линейно-логарифмическое время: O(n log n). Функция, выполняющаяся за линейно-логарифмическое время, асимптотически медленнее, чем функция линейного времени, но быстрее, чем функция квадратичного времени.
• Квадратичное время: O(n²). Функция квадратичного времени выполняется за время, пропорциональное квадрату количества элементов, хранящихся в контейнере.

В следующей таблице обобщается вычислительная сложность последовательного контейнера QList<T>:

В таблице «Амортизировано» означает «амортизированное поведение». Например, «Амортизировано O(1)» означает, что если вы вызываете функцию только один раз, вы можете получить поведение O(n), но если вы вызываете её несколько раз (например, n раз), среднее поведение будет O(1).

В следующей таблице обобщена алгоритмическая сложность ассоциативных контейнеров и множеств Qt:

С QList, QHash и QSet, производительность добавления элементов амортизирована O(log n). Она может быть снижена до O(1) путём вызова QList::reserve(), QHash::reserve() или QSet::reserve() с ожидаемым количеством элементов перед вставкой.

Оптимизации для примитивных и перемещаемых типов

Контейнеры Qt могут использовать оптимизированные пути кода, если хранимые элементы перемещаемы или даже примитивные. Однако нельзя определить, являются ли типы примитивными или перемещаемыми во всех случаях. Вы можете объявить свои типы как примитивные или перемещаемые, используя макрос Q_DECLARE_TYPEINFO с флагом Q_PRIMITIVE_TYPE или Q_RELOCATABLE_TYPE. Смотрите документацию Q_DECLARE_TYPEINFO для получения дополнительной информации и примеров использования.

Если вы не используете Q_DECLARE_TYPEINFO, Qt будет использовать std::is_trivial_v<T> для идентификации примитивных типов и потребует как std::is_trivially_copyable_v<T>, так и std::is_trivially_destructible_v<T> для идентификации перемещаемых типов. Это всегда безопасный выбор, хотя, возможно, с несколько не оптимальной производительностью.

Стратегии роста

QList<T>, QString и QByteArray хранят свои элементы непрерывно в памяти; QHash<Key, T> поддерживает хеш-таблицу, размер которой пропорционален количеству элементов в хеше. Чтобы избежать перераспределения данных каждый раз при добавлении элемента в конец контейнера, эти классы обычно выделяют больше памяти, чем необходимо.

Рассмотрим следующий код, который строит QString из другого QString:

QString onlyLetters(const QString &in)
{
    QString out;
    for (int j = 0; j < in.size(); ++j) {
        if (in[j].isLetter())
            out += in[j];
    }
    return out;
}

Мы строим строку out динамически, добавляя по одному символу за раз. Предположим, что мы добавили 15000 символов в строку QString. Тогда произойдёт следующих 11 перераспределений (из возможных 15000), когда QString заканчивается памятью: 8, 24, 56, 120, 248, 504, 1016, 2040, 4088, 8184, 16376. В конце QString выделяет 16376 символов Юникода, из которых 15000 заняты.

Вышеупомянутые значения могут показаться немного странными, но есть руководящий принцип. Он увеличивается в два раза каждый раз. Более точно, он увеличивается до следующей степени двойки минус 16 байтов. 16 байт соответствует восьми символам, так как QString использует UTF-16 внутри.

QByteArray использует тот же алгоритм, что и QString, но 16 байт соответствует 16 символам.

QList<T> также использует этот алгоритм, но 16 байт соответствует 16/sizeof(T) элементам.

QHash<Key, T> — это совершенно другой случай. Внутренняя хеш-таблица QHash увеличивается по степеням двойки, и каждый раз при увеличении элементы перемещаются в новые ведра, вычисляемые как qHash(key) % QHash::capacity() (количество ведер). Это замечание относится и к QSet<T> и QCache<Key, T>.

Для большинства приложений алгоритм роста по умолчанию, предоставляемый Qt, подходит. Если вам нужен больший контроль, QList<T>, QHash<Key, T>, QSet<T>, QString и QByteArray предоставляют тройку функций, которые позволяют проверять и задавать объём памяти для хранения элементов:

• capacity() возвращает количество элементов, для которых выделена память (для QHash и QSet — количество ведер в хеш-таблице).
• reserve(size) явно выделяет память для size элементов.
• squeeze() освобождает любую память, не требуемую для хранения элементов.

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