Удалить с помощью итератора на карте C ++ STL
Мне любопытно обоснование следующего кода. Для данной карты я могу удалить диапазон до, но не включая, end() (очевидно) используя следующий код:
map<string, int> myMap;
myMap["one"] = 1;
myMap["two"] = 2;
myMap["three"] = 3;
map<string, int>::iterator it = myMap.find("two");
myMap.erase( it, myMap.end() );
Это стирает последние два элемента, используя диапазон. Однако, если бы я использовал версию erase с одним итератором, я наполовину ожидал myMap.end() не приводить ни к каким действиям, поскольку итератор был явно в конце коллекции. Это отличается от поврежденного или недействительного итератора, который явно приведет к неопределенному поведению.
Тем не менее, когда я делаю это:
myMap.erase( myMap.end() );
Я просто получаю ошибку сегментации. Я бы не подумал, что карте сложно проверить, равен ли итератор end() и не предпринимать действий в этом случае. Есть ли какая-то тонкая причина этого, по которой я скучаю? Я заметил, что даже это работает:
myMap.erase( myMap.end(), myMap.end() );
(т.е. ничего не делает)
Причина, по которой я спрашиваю, состоит в том, что у меня есть некоторый код, который получает действительный итератор в коллекцию (но который может быть end()) и я хотел просто передать это в стирание, а не проверять сначала так:
if ( it != myMap.end() )
myMap.erase( it );
что кажется мне немного неуклюжим. Альтернатива — переписать код, чтобы я мог использовать перегрузку стирания по типу ключа, но я бы не стал переписывать слишком много, если смогу помочь.
Решение
Ключ в том, что в стандартной библиотеке диапазоны, определяемые двумя итераторами, являются полуоткрытыми диапазонами. В математической записи [a,b) Они включают в себя первый, но не последний итератор (если оба одинаковы, диапазон пуст). В то же время, end() возвращает итератор, который один за последним элемент, который идеально соответствует обозначению полуоткрытого диапазона.
Когда вы используете версию диапазона erase он никогда не будет пытаться удалить элемент, на который ссылается последний итератор. Рассмотрим модифицированный пример:
map<int,int> m;
for (int i = 0; i < 5; ++i)
m[i] = i;
m.erase( m.find(1), m.find(4) );
В конце исполнения на карте будут храниться две клавиши 0 а также 4, Обратите внимание, что элемент, указанный вторым итератором, был не стерли из контейнера.
С другой стороны, одна операция итератора удалит элемент, на который ссылается итератор. Если код выше был изменен на:
for (int i = 1; i <= 4; ++i )
m.erase( m.find(i) );
Элемент с ключом 4 будут удалены. В вашем случае вы попытаетесь удалить конечный итератор, который не ссылается на допустимый объект.
Я бы не подумал, что для map сложно проверить, равен ли итератор end (), и не выполнить действие в этом случае.
Нет, это не сложно сделать, но функция была разработана с другим контрактом: вызывающая сторона должна передать итератор в элемент в контейнере. Одной из причин этого является то, что в C ++ большинство функций разработано таким образом, чтобы нести минимально возможную стоимость, позволяя пользователю сбалансировать безопасность / производительность на своей стороне. Пользователь может проверить итератор перед вызовом erase, но если бы этот тест был внутри библиотеки, то пользователь не сможет отказаться от тестирования, когда он знает, что итератор действителен.
Другие решения
n3337 23.2.4 Таблица 102
a.erase( q1, q2)
стирает все элементы в диапазон [q1, q2). Возвращает q2.
Так, iterator возвращаясь из map::end() не находится в диапазоне в случае myMap.erase(myMap.end(), myMap.end());
a.erase(q)
стирает элемент, на который указывает q. Возвращает итератор, указывающий на элемент, следующий сразу за q перед удалением элемента. Если такого элемента не существует, возвращает a.end ().
Я бы не подумал, что карте сложно проверить,
итератор равен end () и не предпринимает никаких действий в этом случае. Есть
какая-то тонкая причина этого, по которой я скучаю?
Причина та же, что std::vector::operator[] не могу проверить, что индекс находится в диапазоне, конечно.
Когда вы используете два итератора для указания диапазона, диапазон состоит из элементов от элемента, на который указывает первый итератор, но не включая элемент, на который указывает второй итератор. Так erase(it, myMap.end()) говорит стереть все из it до но не включая end(), Вы также можете передать итератор, который указывает на «реальный» элемент в качестве второго, и элемент, на который указывает этот итератор, не будет удален.
Когда вы используете erase(it) он говорит, чтобы стереть элемент, который it указывает на. end() итератор не указывает на допустимый элемент, поэтому erase(end()) не делает ничего толкового. Библиотека могла бы диагностировать эту ситуацию, и библиотека отладки сделает это, но это накладывает затраты на каждый вызов erase чтобы проверить, на что указывает итератор. Стандартная библиотека не налагает такую стоимость на пользователей. Ты сам по себе. <g>