Есть ли способ реализовать метод вставки для вектора, совместимого со стандартами?

Во-первых, предположим, что A - это тип с:

• Потенциально метательный конструктор/оператор присваивания.
• Нет конструктора/назначения перемещения.

Это распространенный пример типа С++ 03 RAII. Теперь позвольте мне привести стандарт С++ 14 (отрезанные нерелевантные части):

§23.2.1 Общие требования к контейнерам

¹¹ Если не указано иное (см.... и 23.3.6.5), все типы контейнеров, определенные в этом Статья удовлетворяет следующим дополнительным требованиям:

• если исключение генерируется функцией insert() или emplace() при вставке одного элемента, эта функция не имеет эффектов.

§23.3.6.5 vector модификаторы

iterator insert(const_iterator position, const T& x);
...

¹ Примечания: Вызывает перераспределение, если новый размер больше старой. Если перераспределение не происходит, все итераторы и ссылки до точки вставки остаются в силе. Если исключение выбрано иначе, чем конструктор копирования, переместите конструктор, оператор присваивания или оператор присваивания перемещения T или любой из операций InputIterator, никаких эффектов нет. Если исключение вызывается при вставке одного элемента в конец, а T - CopyInsertable или is_nothrow_move_constructible<T>::value - true, эффектов нет. В противном случае, если исключение вызывается конструктором перемещения не CopyInsertable T, эффекты не заданы.

² Сложность: сложность линейна по числу вставленных элементов плюс расстояние до конца вектора.

Теперь рассмотрим следующее:

std::vector<A> v(5);
v.reserve(10);
v.insert(begin() + 2, A());

Ясно, что мы вставляем один элемент, поэтому применяется §23.2.1 - 11, и либо операция выполнена успешно, либо v не изменяется. Статья 23.3.6.5 ничего не меняет об этом. Исключение выбрано конструктором копирования. Мы не вставляем в конце. Конструктор перемещения не используется.

Но теперь рассмотрим этот возможный сценарий при реализации insert , если не произойдет перераспределение:

01234_____ initial state
0123_4____ making space by copying
012_34____ continued
012?34____ continued, but copy operation threw

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

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

• insert(pos, value) становится невыносимо медленным из-за постоянных перераспределений.
• Требование о сложности не выполняется (для перераспределения всегда требуются операции n).

• Можно утверждать, что "вызывает перераспределение, если новый размер больше старой емкости". подразумевает, что перераспределение не допускается, если новый размер не превышает старую емкость.

  Чтобы поддержать это, учтите, что если реализация может перераспределяться в любое время, пользователь не может знать. Это гарантирует гарантию сохранения итераторов ( "Если перераспределение не происходит, все итераторы и ссылки до точки вставки остаются в силе." ) Бесполезная информация и заставляет вас задаться вопросом, почему оба предложения были вставлены в стандарт в первую очередь.

1 и 2 - довольно суровые наблюдения, но если 3 истинно, то (насколько я могу видеть) просто невозможно быть совместимым со стандартом.

Итак, есть ли способ реализации метода insert для вектора, совместимого со стандартами? Или это стандартный дефект?

---

Демонстрация этой проблемы можно увидеть здесь: http://coliru.stacked-crooked.com/a/afd2e838c34c8fcc