STL вектор против стирания карты
https://stackoverflow.com/questions/52714
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
В STL почти все контейнеры имеют функцию стирания.Вопрос, который у меня возник, заключается в векторе, функция erase возвращает итератор, указывающий на следующий элемент в векторе.Контейнер map этого не делает.Вместо этого он возвращает пустоту.Кто-нибудь знает, почему существует эта несогласованность?
Решение
Видишь http://www.sgi.com/tech/stl/Map.html
Карта обладает важным свойством, заключающимся в том, что вставка нового элемента в карту не делает недействительными итераторы, которые указывают на существующие элементы.Удаление элемента с карты также не делает недействительными никакие итераторы, за исключением, конечно, итераторов, которые на самом деле указывают на удаляемый элемент.
Причина возврата итератора при стирании заключается в том, что вы можете выполнять итерации по списку, удаляя элементы по ходу работы.Если удаление элемента не делает недействительными существующие итераторы, нет необходимости делать это.
Другие советы
erase возвращает iterator в C++11.Это связано с отчет о дефекте 130:
В таблице 67 (23.1.1) сказано, что container::erase(итератор) возвращает итератор.В таблице 69 (23.1.2) говорится, что в дополнение к этому требованию ассоциативные контейнеры также сообщают, что container::erase(итератор) возвращает void.Это не дополнение;это изменение требований, которое приводит к тому, что ассоциативные контейнеры перестают соответствовать требованиям к контейнерам.
Комитет по стандартам согласился с этим:
LWG соглашается с тем, что возвращаемым типом должен быть iterator, а не void .(Алекс Степанов тоже согласен.)
(LWG = Библиотечная рабочая группа).
Несоответствие связано с использованием. vector это последовательность, имеющая порядок расположения элементов.Хотя верно, что элементы в map также упорядочены в соответствии с некоторым критерием сравнения, этот порядок неочевиден из структуры.Не существует эффективного способа перехода от одного элемента к следующему (эффективность = постоянное время).На самом деле, перебирать карту довольно дорого;либо создание итератора, либо сам итератор включает в себя прохождение по всему дереву.Это не может быть сделано в O(n), если только не используется стек, и в этом случае требуемое пространство больше не является постоянным.
В общем, дешевого способа вернуть "следующий” элемент после удаления просто не существует.Для последовательностей существует является способ.
Кроме того, Роб прав.Нет необходимости, чтобы Карта возвращала итератор.
Кроме того, STL, поставляемый с MS Visual Studio C ++ (Dinkumware IIRC), предоставляет реализацию map с erase функция, возвращающая итератор к следующему элементу.
Они отмечают, что это не соответствует стандартам.
Я понятия не имею, является ли это ответом, но одна из причин может быть связана со стоимостью поиска следующего элемента.Перебор по карте по своей сути "медленный".
