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

Введение

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

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

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

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

Qt также предлагает ключевое слово foreach, что значительно упрощает итерацию по всем элементам, хранящимся в контейнере.

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

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

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

Qt предоставляет следующие последовательные контейнеры: QList, QLinkedList, QVector, QStack и QQueue. Для большинства приложений QList является лучшим типом для использования. Хотя он реализован как список с массивом, он обеспечивает очень быстрые добавления в начало и конец. Если вам действительно нужен связанный список, используйте QLinkedList; если вы хотите, чтобы ваши элементы занимали смежные места в памяти, используйте QVector. QStack и QQueue — это вспомогательные классы, которые предоставляют семантику LIFO и FIFO.

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

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

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

Контейнеры определяются в отдельных заголовочных файлах с тем же именем, что и контейнер (например, <QLinkedList>). Для удобства контейнеры объявлены в <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;
}

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

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

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

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

Итераторы в стиле Java появились в Qt 4 и являются стандартными в приложениях Qt. Они удобнее в использовании, чем итераторы в стиле STL, но немного менее эффективны. Их API моделируется по классам итераторов Java.

Для каждого класса контейнера существуют два типа итераторов в стиле Java: один для чтения без возможности изменения и один для чтения и записи.

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

В отличие от итераторов в стиле STL (описанных ниже), итераторы в стиле Java указывают между элементами, а не непосредственно на элементы. По этой причине они либо указывают на самое начало контейнера (перед первым элементом), на самый конец контейнера (после последнего элемента) или между двумя элементами. На диаграмме ниже показаны допустимые позиции итераторов в виде красных стрелок для списка, содержащего четыре элемента:

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

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

QListIterator<QString> i(list);
while (i.hasNext())
    qDebug() << i.next();

Он работает следующим образом: QList, по которому необходимо выполнить итерацию, передается в конструктор QListIterator. В этот момент итератор находится непосредственно перед первым элементом списка (перед элементом "A"). Затем мы вызываем hasNext(), чтобы проверить, есть ли элемент после итератора. Если он есть, мы вызываем next(), чтобы перейти к этому элементу. Функция next() возвращает элемент, к которому она переходит. Для QList<QString> этот элемент имеет тип QString.

Вот как выполнить обратную итерацию по QList:

QListIterator<QString> i(list);
i.toBack();
while (i.hasPrevious())
    qDebug() << i.previous();

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

На диаграмме ниже показано влияние вызова next() и previous() на итератор:

В следующей таблице обобщается API QListIterator:

QListIterator не предоставляет функций для вставки или удаления элементов из списка во время итерации. Для этого необходимо использовать QMutableListIterator. Вот пример, где мы удаляем все нечетные числа из QList<int> с помощью QMutableListIterator:

QMutableListIterator<int> i(list);
while (i.hasNext()) {
    if (i.next() % 2 != 0)
        i.remove();
}

Вызов next() в цикле выполняется каждый раз. Он переходит к следующему элементу в списке. Функция remove() удаляет последний элемент, к которому мы перешли, из списка. Вызов remove() не делает итератор недействительным, поэтому его безопасно продолжать использовать. Это работает так же при обратной итерации:

QMutableListIterator<int> i(list);
i.toBack();
while (i.hasPrevious()) {
    if (i.previous() % 2 != 0)
        i.remove();
}

Если нам нужно только изменить значение существующего элемента, мы можем использовать setValue(). В приведенном ниже коде мы заменяем любое значение, большее 128, на 128:

QMutableListIterator<int> i(list);
while (i.hasNext()) {
    if (i.next() > 128)
        i.setValue(128);
}

Как и remove(), setValue() работает с последним элементом, к которому мы перешли. Если мы выполняем итерацию вперед, это элемент перед итератором; если мы выполняем итерацию назад, это элемент после итератора.

next() функция возвращает неконстантную ссылку на элемент в списке. Для простых операций нам даже не нужен setValue():

QMutableListIterator<int> i(list);
while (i.hasNext())
    i.next() *= 2;

Как упоминалось выше, классы итераторов QLinkedList, QVector и QSet имеют точно такой же API, как итераторы QList. Теперь мы перейдём к QMapIterator, который несколько отличается, поскольку он выполняет итерацию по парам (ключ, значение).

Как и QListIterator, QMapIterator предоставляет toFront(), toBack(), hasNext(), next(), peekNext(), hasPrevious(), previous() и peekPrevious(). Компоненты ключ и значение извлекаются путём вызова key() и value() на объекте, возвращаемом next(), peekNext(), previous() или peekPrevious().

Следующий пример удаляет все пары (столица, страна), где название столицы заканчивается на «Город»:

QMap<QString, QString> map;
map.insert("Paris", "France");
map.insert("Guatemala City", "Guatemala");
map.insert("Mexico City", "Mexico");
map.insert("Moscow", "Russia");
...

QMutableMapIterator<QString, QString> i(map);
while (i.hasNext()) {
    if (i.next().key().endsWith("City"))
        i.remove();
}

QMapIterator также предоставляет функции key() и value(), которые работают непосредственно с итератором и возвращают ключ и значение последнего элемента, который итератор перешёл. Например, следующий код копирует содержимое QMap в QHash:

QMap<int, QWidget *> map;
QHash<int, QWidget *> hash;

QMapIterator<int, QWidget *> i(map);
while (i.hasNext()) {
    i.next();
    hash.insert(i.key(), i.value());
}

Если мы хотим проитерировать по всем элементам с одинаковым значением, мы можем использовать findNext() или findPrevious(). Вот пример, где мы удаляем все элементы с определённым значением:

QMutableMapIterator<int, QWidget *> i(map);
while (i.findNext(widget))
    i.remove();

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

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

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

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

В этом обсуждении мы сосредоточимся на QList и QMap. Типы итераторов для QLinkedList, QVector и 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();

В отличие от итераторов Java-стиля, итераторы 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-стиля: следует избегать копирования контейнера, пока активны итераторы этого контейнера. Итераторы указывают на внутреннюю структуру, и если вы копируете контейнер, нужно быть очень осторожными с вашими итераторами. Например:

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

QVector<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 QVector this is likely to crash.
*/

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

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

Если вам нужно выполнить итерацию по всем элементам контейнера в порядке, вы можете использовать ключевое слово Qt foreach. Это ключевое слово — специфично для Qt и реализовано с помощью препроцессора.

Его синтаксис: foreach (переменная, контейнер) оператор. Например, вот как использовать foreach для итерации по QLinkedList<QString>:

QLinkedList<QString> list;
...
QString str;
foreach (str, list)
    qDebug() << str;

Код foreach значительно короче, чем эквивалентный код с использованием итераторов:

QLinkedList<QString> list;
...
QLinkedListIterator<QString> i(list);
while (i.hasNext())
    qDebug() << i.next();

Если тип данных не содержит запятой (например, QPair<int, int>), переменную, используемую для итерации, можно определить в операторе foreach:

QLinkedList<QString> list;
...
foreach (const QString &str, list)
    qDebug() << str;

И, как и любой другой оператор цикла C++, вы можете использовать фигурные скобки вокруг тела цикла foreach и использовать break для выхода из цикла:

QLinkedList<QString> list;
...
foreach (const QString &str, list) {
    if (str.isEmpty())
        break;
    qDebug() << str;
}

В случае с QMap и QHash, foreach автоматически обращается к компоненту значения пар (ключ, значение), поэтому вы не должны вызывать values() для контейнера (это создаёт ненужную копию, см. ниже). Если вы хотите выполнить итерацию как по ключам, так и по значениям, вы можете использовать итераторы (которые быстрее), или вы можете получить ключи и использовать их для получения значений:

QMap<QString, int> map;
...
foreach (const QString &str, map.keys())
    qDebug() << str << ':' << map.value(str);

Для карты с множественными значениями:

QMultiMap<QString, int> map;
...
foreach (const QString &str, map.uniqueKeys()) {
    foreach (int i, map.values(str))
        qDebug() << str << ':' << i;
}

Qt автоматически создаёт копию контейнера при входе в цикл foreach. Если вы изменяете контейнер во время итерации, это не повлияет на цикл. (Если вы не изменяете контейнер, всё равно создаётся копия, но благодаря неявному совместному использованию копирование контейнера очень быстро).

Поскольку foreach создаёт копию контейнера, использование ссылки без const для переменной не позволяет изменить исходный контейнер. Это влияет только на копию, что, вероятно, не то, что вам нужно.

Альтернативой циклу Qt foreach является цикл с диапазоном for, который является частью C++ 11 и более поздних версий. Однако помните, что цикл с диапазоном for может заставить контейнер Qt отсоединиться, в то время как foreach этого не сделает. Но цикл foreach всегда копирует контейнер, что обычно не дёшево для контейнеров STL. В случае сомнений, предпочитайте foreach для контейнеров Qt и циклы с диапазоном for для контейнеров STL.

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

forever {
    ...
}

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

CONFIG += no_keywords

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

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

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

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

Алгоритмическая сложность

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

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

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

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

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

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

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

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

QVector<T>, QString и QByteArray хранят свои элементы непрерывно в памяти; QList<T> поддерживает массив указателей на хранимые элементы для обеспечения быстрого доступа по индексу (если T не является типом указателя или базовым типом размера указателя, в таком случае значение само хранится в массиве); 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. Тогда произойдут следующие 18 перевыделений (из возможных 15000), когда QString закончится памятью: 4, 8, 12, 16, 20, 52, 116, 244, 500, 1012, 2036, 4084, 6132, 8180, 10228, 12276, 14324, 16372. В конце QString выделено 16372 символа Юникода, из которых 15000 заняты.

Вышеуказанные значения могут показаться немного странными, но вот руководящие принципы:

• QString выделяет по 4 символа за раз, пока не достигнет размера 20.
• От 20 до 4084 увеличивается вдвое каждый раз. Более точно, он увеличивается до следующей степени двойки, минус 12. (Некоторые менеджеры памяти работают хуже при запросе точных степеней двойки, поскольку они используют несколько байтов на блок для ведения записей.)
• Начиная с 4084, он увеличивается блоками по 2048 символов (4096 байт). Это имеет смысл, поскольку современные операционные системы не копируют все данные при перевыделении буфера; физические страницы памяти просто переупорядочиваются, и копировать фактически нужно только данные на первой и последней страницах.

QByteArray и QList<T> используют примерно тот же алгоритм, что и QString.

QVector<T> также использует этот алгоритм для типов данных, которые можно перемещать в памяти с помощью memcpy() (включая базовые типы C++, типы указателей и общие классы Qt), но использует другой алгоритм для типов данных, которые можно перемещать только вызывая конструктор копирования и деструктор. Поскольку стоимость перевыделения в этом случае выше, QVector<T> уменьшает количество перевыделений, всегда удваивая память при недостатке места.

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

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

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

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