Стоимость std::vector:: push_back либо преуспевает, либо не действует?

Если я правильно понимаю, std::vector::insert не гарантирует фиксацию или откат для std::vector (по очевидным причинам это делает для std::list) в случае, если исключение выбрасывается во время копирования или перемещения из-за высокой стоимости проверки на исключения. Недавно я заметил, что push_back гарантирует успешную установку в конце или ничего не происходит.

Мой вопрос следующий. Предположим, что при a push_pack вектор должен быть изменен (происходит перераспределение). В этом случае все элементы должны быть скопированы в новый контейнер через семантику копирования или перемещения. Предполагая, что конструктор перемещения не гарантирован noexcept, std::vector будет использовать семантику копирования. Таким образом, чтобы гарантировать вышеприведенное поведение push_pack, std::vector должен проверить успешное копирование, а если нет, откат через своп начального вектора. Это то, что происходит, и если да, то это не так дорого? Или, поскольку перераспределение происходит редко, можно сказать, что амортизированная стоимость низкая?

Ответ 1

В С++ 98/03 мы (очевидно) не имели семантики перемещения, а только копировали семантику. И в С++ 98/03, push_back имеет сильную гарантию. Одна из сильных мотиваций на С++ 11 заключалась в том, чтобы не нарушать существующий код, основанный на этой сильной гарантии.

Правила С++ 11:

Если is_nothrow_move_constructible<T>::value истинно, переместите, else
Если is_copy_constructible<T>::value истинно, copy, else
Если is_move_constructible<T>::value истинно, переместите, else
Код плохо сформирован.

Если мы имеем дело с 1 или 2, у нас есть сильная гарантия. Если мы в случае 3, у нас есть только основная гарантия. Поскольку в С++ 98/03 мы всегда были в случае 2, у нас была обратная совместимость.

Случай 2 не дорогой, чтобы поддерживать сильную гарантию. Один выделяет новый буфер, предпочтительно используя RAII-устройство, такое как второй вектор. Копирует в нее, и только если все это удастся, замените *this на устройство RAII. Это самый дешевый способ сделать что-либо, независимо от того, хотите ли вы получить сильную гарантию, и получите его бесплатно.

Случай 1 также недорого для поддержания сильной гарантии. Лучший способ, которым я знаю, - сначала скопировать/переместить новый элемент в середину нового распределения. Если это удастся, переместите элементы из старого буфера и замените.

Подробнее, чем вы, возможно, хотите

libС++ выполняет все 3 случая с одним и тем же алгоритмом. Для этого используются два инструмента:

std::move_if_noexcept
Контейнер, не содержащий std vector, где данные смежны, но может начинаться с ненулевого смещения от начала выделенного буфера. libС++ вызывает эту вещь split_buffer.

Предполагая, что случай перераспределения (случай отсутствия перераспределения тривиален), split_buffer строится со ссылкой на этот распределитель vector и с удвоенной емкостью этого vector и с его исходным позиционным набором до this->size() (хотя split_buffer все еще empty()).

Затем новый элемент копируется или перемещается (в зависимости от того, с какой перегрузкой push_back мы говорим) с split_buffer. Если это не удается, деструктор split_buffer отменяет выделение. Если это удается, то split_buffer теперь имеет size() == 1, а split_buffer имеет место для ровно this->size() элементов до его первого элемента.

Затем элементы перемещаются/копируются в обратном порядке от this до split_buffer. move_if_noexcept используется для этого, у которого есть тип возврата либо T const&, либо T&& точно так, как нам нужно, в соответствии с указанными выше тремя случаями. При каждом успешном перемещении/копировании split_buffer выполняет push_front. В случае успеха split_buffer теперь имеет size() == this->size()+1, а его первый элемент находится на нулевом смещении от начала выделенного буфера. Если какой-либо переход/копирование завершается с ошибкой, деструктор split_buffer уничтожает все, что находится в split_buffer, и освобождает буфер.

Далее split_buffer и this заменяют свои буферы данных. Это операция noexcept.

Наконец, split_buffer уничтожает, уничтожает все его элементы и освобождает свой буфер данных.

Никаких попыток уловов. Никаких дополнительных расходов нет. И все работает, как указано С++ 11 (и суммировано выше).

Ответ 2

Это то, что происходит, и это может быть дорого. Было решило, что сильная гарантия push_back более важна, чем производительность из семантики перемещения.

Ответ 3

Перераспределение дорогостоящее, да. Поэтому стоимость перераспределения амортизируется по многим вызовам std::vector::push_back.

Чаще всего это делается путем выделения нового блока размера, заданного путем умножения старого размера на некоторый постоянный коэффициент (например, 1,5 или 2) - например, 1,2,4,8,16,32,...

При перераспределении std::vector выделяет новый блок, копирует элементы, уничтожает старые элементы и освобождает старый блок. В случае неудачи (исключение) мы можем просто прервать процесс копирования и начать уничтожать скопированные элементы, поэтому стоимость в худшем случае равна 2*(n-1)+d, где d - стоимость освобождения (мы скопируем n-1 элементы, при копировании n-го элемента генерируется исключение, поэтому мы уничтожаем элементы n-1 и освобождаем новый блок)

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

Вы можете уменьшить влияние перераспределения производительности на использование другого контейнера (например, std::deque, где проблема не существует) или с помощью std::vector::reserve заранее (для этого требуется знание оценки для подсчета элементов).