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

Введение

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

Контейнеры определены в отдельных заголовочных файлах с тем же именем, что и контейнер (например, <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 предоставляют operator<<() и operator>>(), чтобы их можно было легко читать и записывать с помощью QDataStream. Это означает, что типы данных, хранящиеся в контейнере, также должны поддерживать operator<<() и operator>>(). Предоставление такой поддержки несложно; вот как мы могли бы сделать это для структуры 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() для итератора:

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

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

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