Если сам элемент хранится на карте (а не указатель), он будет удален при использовании стирания. Если сама карта сокращается после стирания, это может зависеть от реализации используемой вами карты спецификаций c.
Некоторые реализации могут повторно использовать ранее стертые записи таблицы для вновь вставленных элементов, хотя я думаю, что большинство реализаций этого не делают. Вы используете библиотеку STD?