Материал из Wiki.crossplatform.ru

Внимание: Актуальная версия перевода документации находится здесь

__NOTOC__

[править] Рядовые контейнеры

• Введение
• Классы-контейнеры
• Классы-итераторы
  • Итераторы в стиле Java
  • Итераторы в стиле STL
• Конструкция foreach
• Другие контейнероподобные классы
• Сложности алгоритмизации
• Стратегии увеличения размера

[править] Введение

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

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

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

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

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

[править] Классы-контейнеры

Qt предоставляет следующие классы-контейнеры:

Контейнеры могут быть вложенными. Например, вполне возможно использование QMap< QString, QList<int> >, где типом ключа является QString, а типом значения - QList<int>. Единственный нюанс - это то, что Вы должны оставить пространство между закрывающими угловыми скобками (>); иначе, компилятор C++ воспримет два символа > как оператор сдвига вправо (>>) и сообщит об ошибке.

Значения, хранящиеся в различных контейнерах, должны иметь один из присваиваемых типов данных. Для этого, тип должен предоставлять, конструктор по умолчанию, конструктор копирования и оператор присваивания. Этому соответствуют большинство типов данных, которые Вы, вероятно, захотите поместить в контейнер, включая базовые типы, такие как 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
    {
        QString title;
        QDate releaseDate;
    };

Некоторые из контейнеров предъявляют дополнительные требования к типам данных, которые они могут хранить. Например, для типа Key контейнера QMap<Key, T> должен быть реализован operator<(). Такие особые требования описаны в подробных описаниях классов. В некоторых случаях, определенные функции предъявляют специальные требования; они указаны в описаниях функций. Если эти требования не выполняются, компилятор обязательно сообщит об ошибке.

Контейнеры Qt предоставляют operator<<() и operator>>(), и, поэтому, они могут легко читать из и записывать в QDataStream. Это означает, что типы данных, помещаемых в контейнер, также должны поддерживать operator<<() и operator>>(). Поддержку этих операторов нужно реализовать напрямую, как это сделано для структуры Movie в следующем примере:

    inline QDataStream &amp;operator<<(QDataStream &amp;out, const Movie &amp;movie)
    {
        out << (quint32)movie.id << movie.title
            << (quint32)movie.year;
        return out;
    }
 
    inline QDataStream &amp;operator>>(QDataStream &amp;in, Movie &amp;movie)
    {
        quint32 id;
        quint32 year;
        in >> id >> movie.title >> year;
        movie.id = (int)id;
        movie.year = (int)year;
        return in;
    }

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

[править] Классы-итераторы

Итераторы предоставляют однородные средства доступа к элементам контейнера. Классы контейнеров Qt предоставляют два типа итераторов: итераторы в стиле Java и итераторы в стиле STL.

[править] Итераторы в стиле Java

Итераторы в стиле Java добавлены в Qt 4.0 и очень часто используются в приложениях 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. В следующем примере мы, с помощью QMutableListIterator, удаляем все элементы с нечетными значениями из QList<int>:

    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 - это всего лишь typedef для T *, а тип const_iterator - всего лишь typedef для 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(), поэтому цикл никогда не выполнится.

На нижеприведенной диаграмме, красными стрелками показаны возможные позиции итератора в контейнере vector, содержащем четыре элемента:

При переборе элементов в обратном порядке с помощью итераторов в стиле STL, требуется, чтобы оператор декремента использовался перед обращения к элементу. Вот требуемый цикл while:

    QList<QString> list;
    list << "A" << "B" << "C" << "D";
 
    QList<QString>::iterator i = list.end();
    while (i != list.begin()) {
        --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, то всегда должны иметь копию контейнера и перебирать ее элементы. Например:

    // ПРАВИЛЬНО
    const QList<int> sizes = splitter->sizes();
    QList<int>::const_iterator i;
    for (i = sizes.begin(); i != sizes.end(); ++i)
        ...
 
    // НЕ ПРАВИЛЬНО
    QList<int>::const_iterator i;
    for (i = splitter->sizes().begin();
            i != splitter->sizes().end(); ++i)
        ...

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

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

[править] Конструкция foreach

Если Вы хотите перебрать все элементы контейнера по порядку, то можете использовать конструкцию Qt foreach. Данная конструкция - это дополнение Qt к языку C++, реализованное с помощью средств препроцессора.

Ее синтаксис: foreach (variable, container) statement. В следующем примере показано использование конструкции 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();

Также, как в цикле for языка C++, переменная, используемая для перебора элементов контейнера может быть определена внутри выражения foreach:

    QLinkedList<QString> list;
    ...
    foreach (QString str, list)
        qDebug() << str;

И подобно любому циклу C++, Вы можете заключить тело цикла foreach в фигурные скобки и использовать break для прерывания цикла:

    QLinkedList<QString> list;
    ...
    foreach (QString str, list) {
        if (str.isEmpty())
            break;
        qDebug() << str;
    }

При использовании с QMap и QHash, foreach предоставляет доступ к парам значений (key, value). Если Вы хотите перебрать ключи и значения, то можете использовать итераторы (это работает быстрее) или написать код, подобный следующему:

    QMap<QString, int> map;
    ...
    foreach (QString str, map.keys())
        qDebug() << str << ":" << map.value(str);

Для многосвязных карт:

    QMultiMap<QString, int> map;
    ...
    foreach (QString str, map.uniqueKeys())
        foreach (int i, map.values(str))
            qDebug() << str << ":" << i;

При запуске foreach, Qt автоматически делает копию контейнера. Если Вы изменяете контейнер, который перебираете, это не будет влиять на выполнение цикла. (Если Вы не изменяли контейнер, копирование все еще имеет место, но, благодаря неявному совместному использованию данных, копирование контейнера осуществляется очень быстро.)

В дополнение к foreach, Qt также предоставляет псевдоключевое слово forever, обозначающее бесконечный цикл:

    forever {
        ...
    }

Если Вас беспокоит засорение пространства имен, то Вы можете отключить использование этих макросов, добавив в .pro-файл следующую строку:

    CONFIG += no_keywords

[править] Другие контейнероподобные классы

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

• QVarLengthArray<T, Prealloc> предоставляет низкоуровневый массив переменной длины. Он может использоваться вместо QVector в тех местах кода, в которых особенно важна скорость выполнения.
• QCache<Key, T> предоставляет кэш для хранения объектов некоторого типа T, ассоциированных с ключами типа Key.
• QPair<T1, T2> хранит пары элементов.

Дополнительные нешаблонные типы, дополняющие контейнерные шаблоны Qt, это - QBitArray, QByteArray, QString и QStringList.

[править] Сложности алгоритмизации

Сложности алгоритмизации заключаются в определении насколько быстра (или медленна) каждая из функций при большом количестве элементов в контейнере. Например, вставка элемента в QLinkedList - чрезвычайно быстрая операция назависимо от количества элементов в QLinkedList. В тоже время, вставка элемента в середину QVector, если он содержит очень много элементов, потенциально очень дорога, потому, что половину элементов придется переместить на одну позицию в памяти.

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

• Постоянное время: O(1). Мы говорим, что функция выполняется за постоянное время, если она требует для выполнения одного и того-же времени, независимо от того, сколько элементов содержится в контейнере. В качестве примера можно привести QLinkedList::insert().
• Логарифмическое время: O(log n). Функция, выполняющаяся за логарифмическое время, - это функция, время выполнения которой пропорционально логарифму от количества элементов в контейнере. В качестве примера можно привести qBinaryFind().
• Линейное время: O(n). Функция, выполняющаяся за линейное время, - это функция, время выполнения которой прямо пропорционально количеству элементов, хранящихся в контейнере. В качестве примера можно привести QVector::insert().
• Линейно-логарифмическое время: O(n log n). Функция, выполняющаяся за линейно-логарифмическое время, - это функция, время выполнения которой ассимптотически больше времени выполнения линейной функции, но меньше квадратичной функции.
• Квадратичное время: O(n_). Функция, выполняющаяся за квадратичное время, - это функция, время выполнения которой пропорционально квадрату количества элементов, хранящихся в контейнере.

В следующей таблице приведена алгоритмическая сложность простых классов-контейнеров Qt:

В этой таблице, "Amort." указано для обозначения "усредненного поведения". Например, "Amort. O(1)" обозначает, что, если Вы вызываете данную функцию единожды, то можете получить время выполнения, равное O(n), но при многократном вызове (например, n раз), усредненная величина будет равна O(1).

В следующей таблице приведена алгоритмическая сложность ассоциативных контейнеров и наборов Qt:

В QVector, QHash и QSet, время выполнения усредняется до O(log n). С помощью вызова QVector::reserve(), QHash::reserve() или QSet::reserve(), с ожидаемым количество элементов в списке, до вставка элементов, оно может быть сведено к O(1). В следующем разделе этот вопрос обсуждается более глубоко.

[править] Стратегии увеличения размера

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

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() для освобождения дополнительной занятой памяти.