Здравствуйте, nobody1985, Вы писали:

N>Почему у map::erase ( range version ) линейная сложность?

Скорее всего потому, что сложность балансировки дерева после удаления больше чем одного элемента равно по сложности балансировке всего дерева. Поэтому удаление реализовано поэлементно.