C ++ и аннулирование итератора

Question

Итак, я прохожу Accelerated C ++ и не совсем уверен насчет аннулирования итераторов в C ++. Может быть, дело в том, что проблема в том, как эти итераторы построены, никогда не объясняется.

Вот один пример:

Вектор с {1,2,3}

Если мой итератор включен {2}, и я вызываю удаление {2}, мой итератор недействителен. Зачем? В моей голове {3} смещено вниз, так что место в памяти, где было {2}, так что итератор все еще указывает на допустимый элемент. Единственный способ, которым я бы видел, что это не так, - это если бы итераторы были сделаны заранее для каждого элемента, и каждый итератор имел некоторый тип поля, содержащего адрес следующего элемента в этом контейнере.

Мой другой вопрос связан с таким утверждением, как «делает недействительными все другие итераторы». Хм, когда я перебираю свой векторный контейнер, я использую один итератор. Все ли эти элементы в векторе неявно имеют свой собственный итератор, или я что-то упустил?

Answer 1

В моей голове {3} смещено вниз, так что место в памяти, где было {2}, поэтому итератор все еще указывает на допустимый элемент.

Что может иметь место. Но в равной степени верно и то, что весь вектор перемещается в памяти, что заставляет всех итераторов указывать на уже не существующие области памяти. C ++ просто не дает никаких гарантий в любом случае. (см. Комментарии для обсуждения.)

Все ли эти элементы в векторе неявно имеют свой собственный итератор, связанный с ними, или я что-то упустил?

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

vector<int> vec;
// …

for (vector<int>::iterator i(vec.begin()), end(vec.end()); i != end; ++i) {
    if (some_condition)
        vec.erase(i); // invalidates `i` and `end`.
}

(Не говоря уже о том, что эта копия конечного итератора на самом деле не нужна в STL на современных компиляторах.)

Answer 2

Следующий отчет о дефектах C ++ (исправленный в C ++ 0x) содержит краткое обсуждение значения «invalidate»:

http://www.open -std.org / jtc1 / sc22 / wg21/docs/lwg-defects.html#414

int A[8] = { 1,3,5,7,9,8,4,2 };
std::vector<int> v(A, A+8);

std::vector<int>::iterator i1 = v.begin() + 3;
std::vector<int>::iterator i2 = v.begin() + 4;
v.erase(i1);

Какие итераторы аннулированы v.erase (i1): i1, i2, оба или ни один?

Во всех существующих реализациях, о которых я знаю, статус i1 и i2 одинаков: оба они будут итераторами, указывающими на некоторые элементы вектора (хотя и не на те же элементы, что были раньше).Вы не получите крушения, если будете их использовать.В зависимости от того, что именно вы подразумеваете под «недействительным», вы можете сказать, что ни один из них не был признан недействительным, потому что они все еще указывают на что-то, или вы можете сказать, что оба были недействительными, потому что в обоих случаях элементы, на которые они указывают, были изменены изпод итератором.

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

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

Фактически, этот отчет о дефектах относится именно к тому случаю, о котором вы говорите.Поскольку стандарт C ++ 03 фактически говорит , по крайней мере, в этом пункте ваш итератор не признан недействительным.Но это считалось ошибкой.

Answer 3

Скорее всего, ваш итератор на самом деле указывает на 3 - но это не точно.

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

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

Answer 4

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

Answer 5

Изображение «в вашем уме» - это деталь реализации, и, возможно, ваш итератор не реализован таким образом.Вероятно, так и есть, но, возможно, это не так.

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

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

Answer 6

от SGI http://www.sgi.com/tech/stl/Vector.html

[5] Итераторы вектора становятся недействительными, когда его память перераспределяется. Кроме того, вставка или удаление элемента в середине вектора делает недействительными все итераторы, которые указывают на элементы после точки вставки или удаления. Из этого следует, что вы можете предотвратить аннулирование итераторов вектора, если вы используете Reserve () для предварительного выделения столько памяти, сколько будет использовать вектор, и если все вставки и удаления находятся в конце вектора.

Таким образом, вы можете стереть, начиная с конца

int i;
vector v;
for ( i = v.size(), i >=0, i--)
{
   if (v[i])
      v.erase(v.begin() + i);
}

ИЛИ использовать итератор, возвращаемый вектором erase ()

std::vector<int> v; 
for (std::vector<int>::iterator it = v.begin(); it != v.end(); )
         it = v.erase(it);