За счёт чего последовательное добавление элементов в std::vector имеет амортизированную константную сложность, хотя отдельная операция иногда занимает линейное время?
Добавление в конец std::vector имеет амортизированную сложность O(1), потому что контейнер увеличивает вместимость не на один элемент, а блоками. Когда свободное место заканчивается, создаётся новый буфер, элементы перемещаются или копируются, и отдельная операция может стоить O(n), но суммарная стоимость таких перераспределений при n добавлениях остаётся O(n). Поэтому средняя стоимость одного добавления в длинной последовательности — O(1).
std::vector решает задачу динамического массива: нужен непрерывный участок памяти с быстрым индексированием, но заранее известный размер может отсутствовать. Простое увеличение буфера ровно на один элемент требовало бы перераспределять и копировать весь массив почти при каждом добавлении, что дало бы квадратичную суммарную сложность.
Амортизированный анализ позволяет оценивать не отдельную операцию, а серию операций. Такой подход сохраняет преимущества непрерывного массива, не требуя заранее знать точное количество элементов.
У vector есть размер и вместимость. Пока размер меньше вместимости, новый элемент размещается в уже выделенной памяти, поэтому добавление обычно занимает O(1).
Когда вместимость исчерпана, контейнер выделяет новый непрерывный буфер, переносит туда существующие элементы, добавляет новый элемент и освобождает старый буфер. Эта конкретная операция требует O(n) времени и обычно делает ранее полученные итераторы, указатели и ссылки на элементы недействительными.
Если бы вместимость увеличивалась только на единицу, последовательность из n добавлений потребовала бы примерно 1 + 2 + ... + n перемещений, то есть O(n²). Геометрическое увеличение вместимости меняет эту оценку.
Пусть при необходимости перераспределения вместимость увеличивается примерно в некоторое постоянное число раз больше текущей. Точный коэффициент и стратегия роста не гарантируются стандартом C++, но принципиально важно, что перераспределения происходят всё реже по мере роста контейнера.
При n добавлениях каждый элемент участвует в ограниченном числе крупных переносов. Суммарное количество перемещений или копирований оказывается O(n), а сами n вставок дают ещё O(n) работы. Средняя стоимость одной операции поэтому равна O(1), хотя гарантии для конкретной операции остаются: она может иметь сложность O(n).
Метод reserve позволяет заранее выделить вместимость. Это не меняет асимптотику добавлений без перераспределения, но устраняет неожиданные перераспределения до указанного размера и уменьшает число переносов. Слишком большой резерв, однако, может привести к лишнему потреблению памяти и ухудшить эффективность кэша.
Итоговая оценка зависит также от типа элемента. Перенос каждого элемента должен быть достаточно дешёвым для стандартной модели оценки; если пользовательский тип выполняет дорогостоящую работу в конструкторе перемещения или копирования, реальное время добавления включает эту стоимость. Кроме того, при исключении во время переноса действуют гарантии исключений, зависящие от свойств типа элемента.
Минимальный пример показывает различие между размером и вместимостью:
После reserve(1000) добавления до размера 1000 не должны требовать перераспределения, если вместимость не уменьшается контейнером. Это не означает, что размер сразу становится равным 1000: размер растёт только при фактическом добавлении элементов.
Сервис собирает до нескольких десятков тысяч измерений перед пакетной отправкой. Возможны три варианта: использовать std::list, выбрать std::deque или оставить std::vector без предварительной настройки.
std::list избегает перераспределения непрерывного буфера, но платит отдельными выделениями памяти, дополнительными указателями и плохой локальностью данных. std::deque обычно удобен для роста с обоих концов, но не предоставляет единого непрерывного массива элементов. Обычный vector без reserve корректен, однако может выполнять лишние переносы и временно потреблять больше памяти при расширении.
Если верхняя граница пакета известна, выбирается vector с reserve: сохраняются компактное хранение и быстрый последовательный обход, а перераспределения исключаются в пределах ожидаемого размера. Если граница неизвестна, всё равно выбирается vector, поскольку его амортизированная сложность остаётся O(1), а память и время переносятся только при редких расширениях. В результате обработка пакета использует непрерывный буфер и не зависит от квадратичного сценария последовательного роста.
Нет. Стандарт гарантирует свойства контейнера и его операций, но не фиксирует конкретную формулу роста вместимости. Реализация может выбирать стратегию с учётом требований к памяти, производительности и особенностей платформы.
Следовательно, нельзя делать переносимые выводы вроде точного удвоения вместимости или заранее рассчитывать число перераспределений по конкретному коэффициенту. Для контроля минимально необходимого объёма применяется reserve, но фактическая вместимость после него также может быть больше запрошенной.
Нет. Он резервирует вместимость только не меньше указанного значения на данный момент. Если затем размер превысит эту вместимость, произойдёт новое перераспределение.
Кроме того, вызов reserve с большим значением сам может немедленно выделить память и переместить существующие элементы. Поэтому резерв следует выбирать по обоснованной оценке, а не использовать без ограничений для любого возможного максимума.
Потому что амортизированная оценка распределяет редкую дорогую работу между большим числом дешёвых операций. Обычное добавление использует свободную ячейку, а добавление после исчерпания вместимости переносит все существующие элементы и потому имеет линейную стоимость.
Это различие важно в системах с жёсткими ограничениями по задержке: даже редкая операция O(n) может вызвать недопустимый пик времени. В таком случае заранее резервируют память, используют подходящий размер буфера или выбирают структуру с другими гарантиями, понимая, что это может ухудшить локальность, потребление памяти или удобство доступа.