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

Введение

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

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

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

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

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

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

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

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