#c #map
#c #словарь
Вопрос:
Мне интересно, почему операция удаления с карты внутри цикла в соответствии с предикатом сохраняет итератор в действительном состоянии, но не для вектора
Комментарии:
1. эмм … потому что стандарт указывает, что он должен соответствовать такому поведению. Если вы хотите знать, как выполнять чтение на деревьях (avl, rb) (возможно, начните со связанных списков).
Ответ №1:
Vector::erase делает недействительными итераторы для всех элементов, после первого элемента, который был удален. Это имеет смысл, поскольку вектор хранит свои данные в массиве. Когда элемент удаляется, все элементы после него должны быть сдвинуты вдоль, например
int test[] = {0, 1, 2, 3, 4, 5};
^
В приведенном выше примере у нас есть итератор, указывающий на значение 5, которое мы хотим, однако элемент 1 стирается, теперь у нас был бы:
0, 2, 3, 4, 5
^
Итератор указывает за конец массива, проблема.
С std::map данные хранятся в двоичном дереве, поэтому при удалении элемента изменяются указатели влево / вправо некоторых узлов, но их местоположение в памяти не изменяется. В результате все существующие итераторы, указывающие на элементы, которые не были удалены, все еще действительны.
Комментарии:
1. Я думаю, что ваш пример искажает ситуацию, удаляя последний элемент. То же самое относится к удалению элемента из середины массива (потому что (предполагая тривиальные итераторы указателей) гарантии достижимости нарушаются (вы случайно пропустите следующий элемент). Кроме того, реализации разрешено использовать нетривиальные типы итераторов, например, для отладки, и им разрешено вызывать еще более неопределенное поведение после удаления из вектора)
2. @sehe, я выбрал последний элемент, чтобы создать простой и понятный пример, но это хороший момент для элементов в середине.
Ответ №2:
эмм … простой ответ:
Потому что стандарт требует такого поведения.
Если вы хотите знать, как читать на деревьях (avl, rb) (возможно, начните со связанных списков)
Вы можете легко представить это в своем воображении, подумав, что происходит, когда вы удаляете элемент из середины вектора (т. Е. массива в стиле C; последующие элементы перемещаются), в отличие от удаления из списка / дерева (никакие элементы не перемещаются, обновляются только указатели ссылок).
Обратите внимание, что обход можно было бы сделать безопасным для векторов (используя порядковый индекс вместо итераторов), но суть не в этом: интерфейс итератора требует, чтобы приращение приводило к следующему допустимому итератору. Это не будет правдой (даже если в реализации используется «тривиальный» итератор T *) для вектора.
Ответ №3:
Смотрите http://www.sgi.com/tech/stl/Map.html
Карта обладает важным свойством, заключающимся в том, что вставка нового элемента в map не делает недействительными итераторы, которые указывают на существующие элементы. Удаление элемента из map также не делает недействительными никакие итераторы, за исключением, конечно, итераторов, которые фактически указывают на стираемый элемент.
На самом деле это функция. Это не делает их недействительными, потому что в этом нет необходимости. Для vector вам действительно нужно, поскольку, по крайней мере, все элементы справа от удаленного сдвигаются, а указатели меняются.