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

Введение

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

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

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

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). Функция, выполняющаяся за логарифмическое время, — это функция, время выполнения которой пропорционально логарифму количества элементов в контейнере. Одним примером является 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(ключ) % QHash::capacity() (количество корзин). Это замечание относится также к QSet<T> и QCache<Key, T>.

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

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

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