Ответ 1
Сложность поиска std::map - O (log N) (логарифмический размер контейнера).
В абзаце 23.4.4.3/4 стандарта С++ 11 на std::map::operator []:
Сложность: логарифмическая.
Сложность поиска std::unordered_map - это O (1) (постоянная) в среднем случае, а O (N) (линейная ) в худшем случае.
В абзаце 23.5.4.3/4 стандарта С++ 11 на std::unordered_map::operator []
Сложность: средний случай O (1), наихудший случай O (
size()).
Примечание:
Если ваш вопрос связан только с вычислительной сложностью, то то, что написано выше, должно ответить на него. Фактически, вычислительная сложность операции измеряется в терминах размера контейнера (количество содержащихся в нем элементов).
Однако, если вы ищете способ выполнить поиск O (1) в контейнере, который использует строковые ключи, и где сложность поиска постоянна по отношению к длине строки, а не к размеру контейнер, то ответ заключается в том, что std::unordered_map не соответствует вашим требованиям.
Чтобы найти ключ, сначала необходимо создать хэш; когда ключ является строкой, эта операция сама по себе может быть линейной по размеру строки. Затем реализация должна сравнить ключ со всеми строковыми ключами в одном и том же ведре, и каждое из этих сравнений, в свою очередь, линейно по размеру этих строк.