Сложность поиска для 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 стандарта C++11 на std::unordered_map::operator []
Сложность: в среднем O(1), в худшем случае O(size()
).
ПРИМЕЧАНИЕ:
Если ваш вопрос касается только сложности вычислений, то то, что написано выше, должно ответить на него. Вычислительная сложность операции, по сути, измеряется размером контейнера (количеством содержащихся в нем элементов).
Однако, если вы ищете способ выполнения поиска O(1) в контейнере, который использует строковые ключи и где сложность поиска постоянна относительно длины строки, а не к размеру контейнера, то ответ таков, что std::unordered_map
не будет соответствовать вашим требованиям.
Чтобы найти ключ, сначала необходимо создать его хэш; когда ключ является строкой, сама эта операция может быть линейной по размеру строки. Затем реализация должна сравнить ключ со всеми строковыми ключами в одном сегменте, и каждое из этих сравнений, в свою очередь, линейно зависит от размера этих строк.
person
Andy Prowl
schedule
17.04.2013