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

Введение

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

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

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

Контейнеры предоставляют итераторы для обхода элементов. Итераторы в стиле STL являются наиболее эффективными и могут использоваться совместно с общими алгоритмами Qt и STL qtalgorithms. Итераторы в стиле 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;
};

Некоторые контейнеры имеют дополнительные требования к типам данных, которые они могут хранить. Например, тип Key в 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 автоматически инициализируют значение до 0.

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

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

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

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

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

API итераторов STL моделируется на основе указателей в массиве. Например, оператор ++ перемещает итератор к следующему элементу, а оператор * возвращает элемент, на который указывает итератор. Фактически, для QList и QStack, которые хранят свои элементы в смежных позициях памяти, тип итератора — это просто псевдоним для T *, а тип const_iterator — это просто псевдоним для 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)
    ...

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

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

Неявная совместная работа имеет еще одно последствие для итераторов в стиле 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 с контейнерами std

Контейнеры Qt и алгоритмы std

Вы можете использовать контейнеры Qt с функциями из #include <algorithm>.

QList<int> list { 2, 3, 1 };

std::sort(list.begin(), list.end());
/*
    Sort the list, now contains { 1, 2, 3 }
*/

std::reverse(list.begin(), list.end());
/*
    Reverse the list, now contains { 3, 2, 1 }
*/

int even_elements =
        std::count_if(list.begin(), list.end(), [](int element) { return (element % 2 == 0); });
/*
    Count how many elements that are even numbers, 1
*/

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

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

• QCache<Key, T> предоставляет кэш для хранения объектов определенного типа T, связанных с ключами типа Key.
• 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>:

В таблице «Amort.» обозначает «амортизированное поведение». Например, «Amort. 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() для освобождения дополнительной выделенной памяти.