Посмотрите ключ на std::map O (1)? Я думал, что это было, пока я не подумал об этом больше. Он основан на реализации дерева, поэтому время поиска должно быть O (log N), правильно?
И, возможно ли, чтобы O (1) смотрел на строковый ключ, std::unordered_map возможно?
Сложность поиска 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 не соответствует вашим требованиям.
Чтобы найти ключ, сначала необходимо создать хэш; когда ключ является строкой, эта операция сама по себе может быть линейной по размеру строки. Затем реализация должна сравнить ключ со всеми строковыми ключами в одном и том же ведре, и каждое из этих сравнений, в свою очередь, линейно по размеру этих строк.
Да, действительно, std::map будет O(log N) а std::unordered_map будет иметь среднюю сложность с постоянным временем и O(N) в худшем случае, если слишком много коллизий хешей.
Согласно cppReference, std :: map обычно реализуется с использованием красно-черных деревьев. Красно-черные деревья имеют свойство вставлять, удалять и находить операции, которые занимают O (LogN) время, поэтому в std :: map сложность времени равна O (LogN) каждого элемента.
Если вы ищете структуру данных с операциями доступа O (1), рассмотрите std :: unodered_map, который реализован с использованием хеширования.