Как уже сказали выше — хеш таблица. Если заглянуть в реализацию std::unordered_map, то там все элементы выстроены в список, а в таблице хранятся итераторы на элементы этого списка. Такая структура позволяет и проитерироваться по всем элементам таблицы, и удалить элемент за константное время.
