Изменяет ли размер вектора недействительными итераторы?

Ответ 1

Отредактировано с более тщательной формулировкой

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

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

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

Один из способов избежать этого перераспределения (и недействительности указателя) состоит в том, чтобы сначала вызвать vector::reserve(), чтобы выделить достаточно места, чтобы это копирование не было необходимым. В вашем случае, если вы вызвали a.reserve(3) до первой операции push_back(), тогда внутренний массив был бы достаточно большим, чтобы push_back можно было выполнить без необходимости перераспределения массива, и поэтому ваши итераторы останутся действительными.

Ответ 2

Итераторы векторов становятся недействительными только тогда, когда вектор выполняет перераспределение.

Вызов push_back(4) вызывает вектор для выделения нового блока памяти - это то, что заставляет ваш итератор становиться недействительным, Когда вы также используете push_back(3), для push_back(4) не выполняется перераспределение, поэтому итератор остается в силе.

Ответ 3

Да, любое действие, которое может изменить размер вектора, может привести к недействительности итераторов.

Изменить: включает операции (например, erase(), resize()), которые уменьшают размер контейнера. erase() не делает недействительными все итераторы, но делает недействительными любые итераторы, ссылающиеся на любую точку после стираемого элемента (ов). resize() определяется в терминах insert() и erase(), поэтому он имеет тот же потенциал.

Ответ 4

Правила для недействительности итератора специфичны для контейнера.

Теперь недействительность может иметь 2 значения с вектором:

• Invalidation = точка вне диапазона, определяемая [begin, end]
• Invalidation = указывает на другой объект из оригинала

Как вы можете видеть, вторая намного более строгая:

std::vector<int> myVector;
myVector.push_back(0);
myVector.push_back(1);

std::vector<int>::iterator it = myVector.begin(); // it points to 0
myVector.erase(it); // it points to 1
myVector.erase(it); // it == myVector.end()

В этом случае он "действителен" тем, что он всегда находится в инклюзивном диапазоне [begin, end] и поэтому может быть безопасно использован для любой операции на myVector. С другой стороны, выражение (* it) продолжает меняться: сначала оно возвращает 0, затем 1, затем имеет поведение undefined...

В общем, люди предпочтут говорить о втором требовании, а недействительность итератора просто означает, что (* it) может не дать тот же результат, что и раньше.

Теперь, когда это сказано, существует несколько способов сделать недействительным итератор на векторе (на самом деле это менее устойчивая структура STL).

Во время добавления элементов:

• Это может вызвать перераспределение (1), если myVector.size() == myVector.capacity(), поскольку проверка этого является подверженной ошибкам, мы обычно считаем, что любое добавление приведет к аннулированию итераторов
• Если вы хотите быть "придирчивым" и знаете, что перераспределение не запускается, вам все равно придется беспокоиться о insert. Вставка элемента делает недействительными итераторы, указывающие на текущую позицию и все последующие, поскольку элементы сдвинуты на один шаг ближе к концу вектора.

Во время удаления элементов:

• Нет перераспределения, даже если буфер теперь намного больше, чем необходимо. Это можно сделать, хотя, используя усадку, чтобы соответствовать идиоме (2).
• Все итераторы, указывающие на удаленный элемент, становятся недействительными. В частности, предыдущий "конечный" итератор теперь выходит за пределы диапазона [начало, конец] и не может безопасно использоваться в алгоритмах STL, например.

(1) Внутренняя структура std::vector представляет собой массив из T, это связано с совместимостью с C-программами (с использованием & myVector.front() в качестве адреса массива) и потому, что он гарантирует смежность и минимальные накладные расходы (т.е. объем пространства, занимаемого векторными собственными данными, и объем пространства, занимаемого объектом)

В любой момент вы можете узнать, сколько объектов может удерживать вектор с использованием метода .capacity().

Если вы хотите вставить объект, и вектор не имеет необходимой емкости, запускается вызов метода .reserve(size_t). Этот метод, если количество требуемых элементов превосходит текущую емкость, вызывает перераспределение.

Затем вектор выделяет новый массив элементов (его размер обычно равен 2 * n + 1, где n - текущая емкость), копирует элементы текущего массива в новый массив, отбрасывает текущий массив.

Поскольку он отбрасывает текущий массив, ваши итераторы недействительны, так как векторные итераторы обычно являются простыми указателями (для эффективности).

Обратите внимание, что если итераторы были реализованы как: ссылка на вектор + счет, а разыменование было фактически * (& m_vector.front() + n) перераспределение не приведет к их аннулированию... но они будут меньше эффективным.

(2) Усадка для установки: предупреждение, это вызывает COPY элементов и отменяет итераторы.

// myVector has 10 elements, but myVector.capacity() == 1000
myVector.swap(std::vector<int>(myVector));

Сначала создается временный вектор, который выделяет столько памяти, сколько необходимо (с минимальным значением в зависимости от библиотеки) и копирует элементы myVector. Затем операция свопинга обменивает буферы из myVector и этой копии, и, таким образом, myVector теперь заполняет буфер с минимальным объемом памяти. В конце операции временное уничтожается и память, которую он удерживает, освобождается.

Ответ 5

Для справок в будущем все типы таких лакомых кусочков STL, как это, находятся на веб-сайте SGI: http://www.sgi.com/tech/stl/Vector.html

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

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

См. статью в википедии в контейнерах Standard_Template_Library для начальной точки. Если у вас есть деньги, я настоятельно рекомендую Scott Meyer "Эффективный STL: 50 конкретных способов улучшить использование стандартной библиотеки шаблонов".

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