Работа std :: map & lt; t1, t2 & gt; :: erase (позиция итератора)?
Я читаю на cplusplus.com что операция по удалению элемента в std::map путем передачи итератора в качестве аргумента является постоянным временем.
Если я не ошибаюсь (и, пожалуйста, исправьте меня, если я ошибаюсь), итераторы в основном являются указателями на элементы на карте с помощью ++ оператор просто возвращает порядковый преемник текущего элемента, я думаю, что таким образом достигается отсортированный результат при обходе std::map,
Теперь, если карта представляет собой красно-черное дерево, не должно ли удаление элемента (с использованием его адреса) быть логарифмической операцией времени, мне интересно, как они это делают в постоянное время (если только для этого нет слишком расточительной памяти) ,
Решение
Для начала, я бы с осторожностью отнесся к любой информации, которую вы получаете от cplusplus.com; Известно, что на сайте есть ошибки.
Посещение cppreference.com, мы получаем, что сложность амортизированный постоянное время Это означает, что любая последовательность из n erase Операции должны занимать время O (n), даже если отдельная операция стирания требует времени больше, чем O (1).
Оказывается, что время, необходимое для вставки или удаления из красного / черного дерева, в итоге вычисляется следующим образом: каждая вставка или удаление занимает время O (log n), чтобы найти позицию для узла, но затем выполняет только амортизированное O ( 1) работа по вставке или удалению элемента. Это означает, что в работе по вставке или удалении узла из красно-черного дерева преобладает работа, необходимая для выяснения, куда направляется этот узел, а не работа, необходимая для восстановления баланса дерева впоследствии. В результате, если у вас уже есть указатель на красное / черное дерево и вы хотите удалить этот элемент, вам нужно только выполнить амортизированную работу O (1), чтобы удалить элемент. Каждое отдельное удаление может занять немного времени (не более O (log n)), но за поток из n операций общая выполненная работа составляет не более O (n).
Обратите внимание, что стандарт не требует, чтобы std::map используйте красное / черное дерево. Он может использовать другой тип структуры данных (скажем, Splay Tree, козёл отпущения, или детерминированный skiplist), что также гарантирует на этот раз сложность. Интересно, что не все сбалансированные структуры дерева двоичного поиска могут поддерживать амортизированное удаление O (1). AVL дерево, например, не имеет этой гарантии.
Надеюсь это поможет!
Другие решения
Если вы передаете в карту итератор для удаления элемента, то амортизируется постоянное время в соответствии с http://www.cplusplus.com/reference/map/map/erase/.
Амортизированное постоянное время означает «среднее время, затрачиваемое на операцию, если вы выполняете много операций». Следовательно, может быть некоторая операция, которая занимает больше времени, чем постоянное время, но если вы выполняете одну и ту же операцию много раз, она амортизируется как постоянная.