Как растет вектор? - часть 3

Таблица 6.3. Время в секундах для вставки 10 000 элементов

Отсюда следует, что вектор лучше подходит для типов данных малого размера, нежели список, и наоборот. Эта разница объясняется необходимостью выделения памяти и копирования в нее старых элементов. Однако размер данных – не единственный фактор, влияющий на эффективность. Сложность типа данных также ухудшает результат. Почему?

Вставка элемента как в список, так и в вектор, требует вызова копирующего конструктора, если он определен. (Копирующий конструктор инициализирует один объект значением другого. В разделе 2.2 приводится начальная информация, а в разделе 14.5 о таких конструкторах рассказывается подробно). Это и объясняет различие в поведении простых и сложных объектов при вставке в контейнер. Объекты простого класса вставляются побитовым копированием (биты одного объекта пересылаются в биты другого), а для строк и сложных классов это производится вызовом копирующего конструктора.

Вектор должен вызывать их для каждого элемента при перераспределении памяти. Более того, освобождение памяти требует работы деструкторов для всех элементов (понятие деструктора вводится в разделе 2.2). Чем чаще происходит перераспределение памяти, тем больше времени тратится на эти дополнительные вызовы конструкторов и деструкторов.

Конечно, одним из решений может быть переход от вектора к списку, когда эффективность вектора становится слишком низкой. Другое, более предпочтительное решение состоит в том, чтобы хранить в векторе не объекты сложного класса, а указатели на них. Такая замена позволяет уменьшить затраты времени на 10 000 вставок с 6.70 секунд до 0.82 секунды. Почему? Емкость возросла с 1 до 256, что существенно снизило частоту перераспределения памяти. Кроме того, копирующий конструктор и деструктор не вызываются больше для каждого элемента при копировании прежнего содержимого вектора.

Функция reserve() позволяет программисту явно задать емкость контейнера[11]. Например: