Почему vector:: iterator недействителен при перераспределении?

Ответ 1

Просто добавьте ссылку на оправдание, связанное с производительностью: при разработке С++, Stroustrup считал жизненно важным, чтобы классы шаблонов, такие как std::vector подход к характеристикам производительности встроенных массивов:

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

...

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

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

Bjarne Stroustrup, Дизайн и эволюция С++, стр .342.

Ответ 2

Поскольку для итераторов это необходимо, им нужно будет сохранить указатель на векторный объект. Для каждого доступа к данным им нужно будет следовать указателю на вектор, а затем следовать указателю в нем в текущее местоположение массива данных, а затем добавить смещение * размер элемента. Это будет намного медленнее и потребуется больше памяти для члена size_type.

Конечно, это хороший компромисс, и было бы неплохо иметь возможность выбирать его, когда захотите, но он медленнее и громоздко, чем использование прямого массива (C-style). std::vector безжалостно анализировался для производительности при введении STL, и нормальная реализация оптимизирована для пространства и скорости по этому коэффициенту удобства/надежности, так же как эквивалент массива operator[] работает так же быстро, как массивы, но менее безопасен, чем at().

Ответ 3

Вы можете добавить безопасность, обернув стандартный std::vector<T>::iterator, но вы не можете добавить скорость, обернув extension::vector<T>::safe_iterator. Это общий принцип и объясняет многие варианты дизайна С++.

Ответ 4

Есть много причин для принятия этих решений. Как указывали другие, самая основная реализация iterator для вектора - простой указатель на элемент. Чтобы иметь возможность обрабатывать push_back, итераторы должны были бы быть изменены для обработки указателя на вектор и позицию, при доступе через оператора, векторный указатель был бы разыменован, указатель на полученные данные и добавленная позиция, с дополнительным разыменованием.

Хотя это не самая эффективная реализация, это не является ограничивающим фактором. Реализация итераторов по умолчанию в библиотеках VS/Dinkumware (даже в версии) проверяются итераторами, которые управляют эквивалентным объемом информации.

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

Ответ 5

Вам нужно будет сохранить как смещение, так и указатель на сам векторный объект.

Как указано, итератором может быть только указатель, который занимает меньше места.

Ответ 6

TL; DR - потому что вы торгуете простыми правилами для недействительности для более сложных действий на расстоянии.

Обратите внимание, что "сохранить указатель на векторный объект" вызовет новые случаи недействительности. Например, сегодня swap сохраняет достоверность итератора, если указатель (или ссылка) на вектор хранится внутри итераторов, он больше не может. Все операции, которые перемещают сами векторные метаданные (векторы-векторы?), Могут привести к недействительности итераторов.

Вы торгуете: "Итератор становится недействительным, когда указатель/ссылка на элемент недействителен" для "итератор становится недействительным, когда указатель/ссылка на вектор недействителен".

Аргументы производительности не имеют большого значения, потому что предлагаемая альтернативная реализация даже не верна.

Ответ 7

Я итератор не был недействителен, должен ли он указывать на тот же элемент или на ту же позицию после вставки перед ним? Другими словами, даже если не было проблем с производительностью, нетривиально решить, какое альтернативное определение использовать.