Я обнаружил, что этот код C++:
vector<int> a;
a.push_back(1);
a.push_back(2);
vector<int>::iterator it = a.begin();
a.push_back(4);
cout << *it;
вывести какое-то большое случайное число; но если вы добавите a.push_back(3) между 3-й и 4-й строками, будет напечатано 1. Можете ли вы объяснить это мне?
Отредактировано с более тщательной формулировкой
да, изменение размера вектора может сделать недействительными все итераторы, указывающие на вектор.
Вектор реализуется путем внутреннего выделения массива, в котором хранятся данные. Когда вектор растет, этому массиву может не хватить места, и когда это происходит, вектор выделяет новый, больший массив, копирует в него данные, а затем удаляет старый массив.
Таким образом, ваши старые итераторы, указывающие на старую память, больше недействительны. Однако если размер вектора изменяется вниз (например, на pop_back()), используется тот же массив. Массив никогда не уменьшается автоматически.
Один из способов избежать этого перераспределения (и аннулирования указателя) — сначала вызвать vector::reserve(), чтобы выделить достаточно места, чтобы в этом копировании не было необходимости. В вашем случае, если вы вызвали a.reserve(3) перед первой операцией push_back(), то внутренний массив будет достаточно большим, чтобы можно было выполнять push_back без перераспределения массива, и поэтому ваши итераторы останутся действительными.
std::vector() вы не можете узнать, применимы ли эти условия. Таким образом, единственный способ убедиться, что итераторы остаются в силе после push_back(), — это вручную зарезервировать достаточно места заранее.
- person dmckee --- ex-moderator kitten; 26.10.2009
resize(), а ранее мы вызывали reserve().
- person jalf; 26.10.2009
insert (и, следовательно, по ссылке push_back) вызывает перераспределение, если новый размер превышает емкость. Затем далее говорится, что если перераспределения не происходит, итераторы до точки вставки (все итераторы к элементам для push_back) остаются действительными. К сожалению, стандарт, похоже, ничего не говорит об обратном, т.е. он не говорит, что если новый размер не превышает емкость, то перераспределение не происходит, если это не подразумевается где-то еще.
- person CB Bailey; 26.10.2009
reserve есть примечание, которое гарантирует, что после вызова reserve никакая вставка не приведет к перераспределению, если только эта вставка не приведет к тому, что размер вектора превысит размер, переданный в вызов reserve. Это по-прежнему не является гарантией того, что вставка, сохраняющая размер меньше емкости, не вызовет перераспределения. Это немного другое.
- person CB Bailey; 26.10.2009
capacity() определен для возврата общего количества элементов, которые вектор может содержать без необходимости перераспределения. Я не думаю, что предполагаемый комитет требовал в этом контексте иметь такое значение, чтобы векторы могли перераспределяться, когда в этом нет необходимости. Таким образом, вектор может перераспределяться только в том случае, если новый размер превышает емкость, что является вашей второй (более сильной) гарантией.
- person Steve Jessop; 27.10.2009
Итераторы вектора становятся недействительными только тогда, когда вектор выполняет перераспределение.
Вызов push_back(4) приводит к тому, что вектор выделяет новый блок памяти, поэтому ваш итератор становится недействительным. Когда вы также используете push_back(3), для push_back(4) не выполняется перераспределение, поэтому итератор остается действительным.
Да, любое действие, которое может изменить размер вектора, может сделать итераторы недействительными.
Изменить: это включает операции (например, erase(), resize()), которые уменьшают размер контейнера. erase() не делает недействительными все итераторы, но делает недействительными любые итераторы, ссылающиеся на любую точку после стертого элемента(ов). resize() определяется в терминах insert() и erase(), поэтому у него такой же потенциал.
Правила аннулирования итератора специфичны для контейнера.
Теперь инвалидация может иметь 2 значения с вектором:
Как видите, второй гораздо строже:
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, затем имеет неопределенное поведение...
В общем, люди скорее будут говорить о втором требовании, и отмена итератора просто означает, что (*он) может не дать такой же результат, как раньше.
Теперь, когда это сказано, есть несколько способов аннулировать итератор в векторе (фактически это менее стабильная структура STL).
При добавлении элементов:
insert. Вставка элемента делает недействительными итераторы, указывающие на эту текущую позицию и все последующие, поскольку элементы сдвигаются на один шаг к концу вектора.При удалении элементов:
(1) Внутренняя структура std::vector представляет собой массив T, это связано с совместимостью с C-программами (с использованием &myVector.front() в качестве адреса массива) и потому, что это гарантирует непрерывность и минимум пространство накладных расходов (т. е. объем пространства, занимаемый собственными данными вектора, по сравнению с объемом пространства, занимаемым объектом)
В любой момент вы можете узнать, сколько объектов может содержать вектор, используя метод .capacity().
Когда вы хотите вставить объект, а вектор не имеет необходимой емкости, срабатывает вызов метода .reserve(size_t). Этот метод, если количество требуемых элементов превышает текущую емкость, инициирует перераспределение.
Затем вектор выделяет новый массив элементов (его размер обычно равен 2*n+1, где n — текущая емкость), копирует элементы текущего массива в новый массив, отбрасывает текущий массив.
Поскольку он отбрасывает текущий массив, ваши итераторы становятся недействительными, поскольку векторные итераторы обычно представляют собой простые указатели (для эффективности).
Обратите внимание, что если бы итераторы были реализованы как: ссылка на вектор + счетчик, а разыменование было бы на самом деле *(&m_vector.front() + n), перераспределение не сделало бы их недействительными... но они были бы менее эффективными.
(2) Уменьшить размер: предупреждение, это вызывает КОПИЮ элементов и делает недействительными итераторы.
// myVector has 10 elements, but myVector.capacity() == 1000
myVector.swap(std::vector<int>(myVector));
Сначала он создает временный вектор, который будет выделять столько памяти, сколько необходимо (минимум зависит от библиотеки), и копирует элементы myVector. Затем операция подкачки обменивает буферы из myVector и этой копии, и, таким образом, myVector теперь содержит буфер с минимально необходимым объемом памяти. В конце операции временная память уничтожается, а память, которую она содержит, освобождается.
Для справки в будущем, все подобные лакомые кусочки STL можно найти на веб-сайте SGI: http://www.sgi.com/tech/stl/Vector.html
Если вам нужно, чтобы итераторы оставались действительными после добавления или удаления коллекции, рассмотрите другой вид коллекции, например список.
Однако лучше всего определить из матрицы функции, которые вы хотите получить от коллекции (произвольный доступ и т. д.), а затем выбрать правильный контейнер.
См. статью в Википедии о контейнерах Standard_Template_Library для отправной точки. Если у вас есть деньги, я настоятельно рекомендую книгу Скотта Мейера «Эффективный STL: 50 конкретных способов улучшить использование стандартной библиотеки шаблонов».
Извиняюсь за отсутствие вспомогательных ссылок, я здесь новичок, и мне не хватает репутации, чтобы публиковать это более чем с одной.
