Насколько я понимаю, std:::map реализована через сбалансированные деревья; unordered_map - через хэш.
Согласно
замечательной таблице имеем, что в случае std::map операции поиска/записи занимают O(log N) и в среднем, и в худшем случаях; во втором случае, они занимают O(1) в среднем и O(N) в худшем. То, как будет работать хэш, во многом зависит от качества хэш-функции. Мне кажется, вам надо посмотреть именно в сторону
Ещё один момент, связанный с хэшем - число "корзин". У меня в реализации unordered_map стоит 10 по умолчанию (задаётся в конструкторе), и эта реализация, похоже,
перераспределяет корзины динамически при достижении определённого числа добавленных элементов.
Вот здесь показано, что правильно инициализированный unordered_map должен так же быстро работать для вставки, как и для извлечения.