STL вектор против удаления карты

Question

В STL почти все контейнеры имеют функцию стирания. У меня вопрос в векторе, функция стирания возвращает итератор, указывающий на следующий элемент в векторе. Контейнер карты не делает этого. Вместо этого он возвращает пустоту. Кто-нибудь знает, почему существует это несоответствие?

Answer 1

См. http://www.sgi.com/tech/stl/Map.html

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

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

Answer 2

erase возвращает iterator в C ++ 11. Это связано с сообщением о дефекте 130 :

Таблица 67 (23.1.1) говорит, что container :: erase (итератор) возвращает итератор. Таблица 69 (23.1.2) говорит, что в дополнение к этому требованию ассоциативные контейнеры также говорят, что container :: erase (iterator) возвращает void. Это не дополнение; это изменение требований, которое приводит к тому, что ассоциативные контейнеры не отвечают требованиям для контейнеров.

Комитет по стандартам принял это:

LWG соглашается, что возвращаемый тип должен быть итератором, а не void. (Алекс Степанов тоже согласен.)

(LWG = Библиотека рабочей группы).

Answer 3

Несоответствие связано с использованием. vector - последовательность, имеющая порядок элементов. Хотя верно, что элементы в map также упорядочены согласно некоторому критерию сравнения, это упорядочение не очевидно из структуры. Не существует эффективного способа перехода от одного элемента к другому (эффективный = постоянное время). На самом деле, перебирать карту довольно дорого; создание итератора или самого итератора предполагает обход полного дерева. Это невозможно сделать в O ( n ), если только не используется стек, и в этом случае требуемое пространство больше не является постоянным.

В общем, просто нет дешевого способа вернуть «следующий» элемент после стирания. Для последовательностей есть способ.

Кроме того, Роб прав. Для карты нет необходимости возвращать итератор.

Answer 4

Кроме того, STL, поставляемый с MS Visual Studio C ++ (Dinkumware IIRC), обеспечивает реализацию карты с функцией erase, возвращающей итератор для следующего элемента.

Они отмечают, что это не соответствует стандартам.

Answer 5

Я не знаю, является ли это ответом, но одна из причин может быть связана со стоимостью поиска следующего элемента. Итерация по карте по сути "медленная".