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

Введение

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

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

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

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

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

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

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>. Единственная проблема — необходимо вставлять пробел между закрывающими угловыми скобками (>); в противном случае компилятор C++ неправильно интерпретирует две > как оператор сдвига вправо (>>) и сообщит об ошибке синтаксиса.

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

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

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

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

Итераторы обеспечивают унифицированный способ доступа к элементам в контейнере. Классы контейнеров 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), так как они немного быстрее.

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

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

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

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

• Постоянное время: O(1). Функция считается работающей за постоянное время, если она требует одинакового времени независимо от того, сколько элементов присутствует в контейнере. Одним примером является QLinkedList::insert().
• Логарифмическое время: O(log n). Функция, работающая за логарифмическое время, — это функция, время выполнения которой пропорционально логарифму количества элементов в контейнере. Одним примером является qBinaryFind().
• Линейное время: 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(), чтобы освободить дополнительную выделенную память.