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

Введение

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

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

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

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

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 автоматически инициализируют значение нулём.

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

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

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

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

Для каждого класса контейнера существуют два типа итераторов в стиле 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 или non-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

Сравнение контейнеров 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 содержит много элементов, поскольку половина элементов должна быть перемещена на одну позицию в памяти.

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

• Постоянное время: 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(), чтобы освободить дополнительную выделенную память.