Стратегии увеличения размера

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

Задание 1. Дана последовательность действительных чисел. Необходимо сформировать новую последовательность по некоторому правилу. Для представления исходной и результирующей последовательности используйте библиотечный шаблон QVector.

Варианты задания

1. Новая последовательность должна содержать все ненулевые элементы исходной (с сохранением исходного относительного порядка).
2. В новой последовательности сначала должны идти все отрицательные элементы исходной, затем все нулевые элементы, затем все положительные (с сохранением исходного относительного порядка).
3. Новая последовательность должна содержать все неотрицательные элементы исходной (с сохранением исходного относительного порядка).
4. Новая последовательность сначала должна содержать все элементы исходной с четными индексами, затем - все остальные (с сохранением исходного относительного порядка).
5. В новую последовательность из исходной требуется занести те элементы исходной, модуль которых не превышает 1.
6. Новая последовательность сначала должна содержать все элементы исходной, значение которых по модулю меньше 1, затем - все остальные (с сохранением исходного относительного порядка).
7. Новая последовательность должна содержать сначала все нулевые элементы исходной, затем все остальные элементы (с сохранением исходного относительного порядка).
8. Новая последовательность должна содержать все элементы исходной, модуль которых находится в заданном промежутке [a; b].
9. Новая последовательность должна содержать сначала все элементы исходной с нечетными индексами, затем - с четными (с сохранением исходного относительного порядка).
10. Новая последовательность должна содержать сначала все положительные элементы исходной, затем - все неположительные (с сохранением исходного относительного порядка).
11. Новая последовательность должна содержать все элементы исходной, значение которых находится в заданном промежутке [a; b].
12. Новая последовательность должна содержать сначала все ненулевые элементы исходной (с сохранением исходного порядка), потом - все нулевые.