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

Введение

Библиотека 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().

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

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)
    ...

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

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

Неявная совместная работа имеет еще одно следствие для итераторов в стиле 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 дополнение к языку C++, и оно реализовано с использованием препроцессора.

Его синтаксис: 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.

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

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

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

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

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

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

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

В таблице "Амортиз." означает "амортизированное поведение". Например, "Амортиз. 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. Затем при исчерпании места у QString происходит следующие 18 перераспределений (из возможных 15000): 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(), чтобы освободить дополнительную выделенную память.