Меняет ли вставка / стирание элемента из std :: map последовательность итераций?
Скажем, у меня есть следующий код:
typedef std::map< int, std::string >::iterator Iterator;
Iterator iter = myMap.begin();
while (iter != myMap.end())
{
Iterator current = iter;
++iter;
maybeDeleteElement( current ) // may call erase.
}
При условии std::map реализован в виде красно-черного дерева, гарантируется ли, что каждый элемент на карте будет посещен ровно один раз? Или изменение карты вызовет перебалансировку дерева и, следовательно, изменение последовательности итераций?
Примечание. Вопрос не в том, будут ли признаны недействительными какие-либо итераторы. Но итератор, оставшийся в силе, не обязательно означает, что его увеличение даст вам тот же следующий элемент, что и раньше.
Решение
В std::map элементы будут посещаться по порядку.
Если вы храните итератор, который ссылается на элемент, который не удален и, следовательно, не признан недействительным, итератор все равно будет ссылаться на этот же элемент. (Если это был конечный итератор, он остается конечным итератором, поскольку он не считается недействительным).
Когда вы продвигаете этот итератор, он переходит к следующему элементу по порядку после элемента, на который вы ссылаетесь.
Для вашего конкретного примера, да, каждый элемент будет посещен ровно один раз, потому что все удаления элементов были элементами, которые находятся до текущего состояния итератора вашего цикла.
Если вы вставляете элементы впереди любого итератора, который вы используете для итерации, то в конечном итоге вы достигнете их, когда будете выполнять итерацию вперед с вашим итератором. Если вы удаляете элементы перед тем итератором, который вы используете для итерации, они больше не будут частью будущих элементов, которых вы достигнете, если итерируете с этим итератором.
Если вы вставляете или удаляете элементы перед текущим местоположением итератора, если только вы не начинаете вызывать -- или аналогичные функции, ваша текущая итерация будет продолжаться, не замечая, что они исчезли.
Это потому что ++ на действительном итераторе в упорядоченном контейнере гарантированно возвращается следующий элемент в заказе, а операции с другими итераторами, которые не делают недействительным итератор, не изменяют инварианты этого итератора (например, к какому элементу они относятся).
Другие решения
Да, вставка / стирание может изменить последовательность итераций. Это не происходит в вашем примере, так как вы стираете уже пройденные итераторы, но если вы стираете / вставляете расположенные элементы впереди вашего текущего итератора, тогда он изменит остальную часть последовательности.
Вот краткий код, который отображает такое поведение:
int main (){
map<int,int> mapa;
for(int i = 0; i < 5; ++i) mapa[i] = i;
bool add = false;
for(auto it = mapa.begin(); it != mapa.end(); ++it){
int x = it->second;
printf("%d\n", x);
if(add) mapa.erase(x+1);
add = !add;
}
return 0;
}
Пример выше напечатает 0 1 3 4 (вместо 0 1 2 3 4). Кроме того, если вы удалите текущий итератор, его ссылка на следующий элемент будет признана недействительной, и ваша программа потерпит крах на следующей итерации.
Кроме того, вы также можете проверить вставку, подставив if(add) выше с:
if(add) mapa[x+5] = x+5;
else mapa[x-20] = x-20;
В этом примере будут напечатаны дополнительные элементы {6, 8, 11, 16}, а не отрицательные, поскольку они вставляются в позицию, предшествующую вашей текущей.
Стирание элемента из map не делает недействительными итераторы, поэтому я ожидаю, что он будет продолжать итерацию правильно.
Да, последовательность итераций меняется. Это связано с §23.2.4.1 / 10 и / 11:
(p10) Фундаментальное свойство итераторов ассоциативных контейнеров заключается в том, что они перебирают контейнеры в не убывающем порядке ключей, где не убывающие определяются путем сравнения, использованного для их построения. Для любых двух разыменованных итераторов i и j, таких, что расстояние от i до j положительное,
value_comp(*j, *i) == false(P11)
Для ассоциативных контейнеров с уникальными ключами выполняется более сильное условие,value_comp(*i, *j) != false.
Если после вставки новый элемент был добавлен в начале последовательности итерации, независимо от упорядочения элементов (чтобы не изменять последовательность перед любой существующей позицией итератора), вышеуказанное требование будет нарушено.
Несмотря на вашу записку, для erase на случай, если этот вопрос именно так о недействительности итератора, потому что если ни один итератор не признан недействительным, порядок обязательно остается прежним. Это потому что map является отсортированным контейнером, поэтому независимо от того, какие внутренние изменения могут произойти, порядок итераций должен оставаться точно таким же.
Чтобы обратиться конкретно к вашему примеру, он будет проходить каждый элемент ровно один раз, потому что вы сохраняете итератор, чтобы проверить и увеличить свой итератор обхода.
В случае вставки, если вы вставите перед текущей точкой итерации, этот элемент не будет посещен. Вставка после текущего итератора приведет к прохождению нового элемента.