Какой наихудший сценарий для unordered_map?
Я нашел много постов о сложности map а также unordered_map, Он сказал, что unordered_map имеет сложность в худшем случае O(N), Для моей цели у меня будет вход в виде отсортированных значений, таких как 1 2 5 6 9 11 12.., Мне нужно вставить или найти и удалить значение. Мне придется делать вставку / удаление довольно часто. Я думал об использовании set которая имеет log (n) сложность во всех случаях. А потом я наткнулся на unordered_map, который имеет наилучшую O (1) сложность. Но я должен понимать, что в моем сценарии я столкнусь с наихудшим сценарием unordered_map? И какой будет сценарий?
РЕДАКТИРОВАТЬ: В моем случае все значения будут уникальными.
Решение
unordered_map худший случай обычно происходит, когда хеш-функция создает коллизии для каждой вставки в карту.
Я сказал «обычно», потому что стандарт определяет сложность наихудшего случая, а не когда и как это произойдет, поэтому Теоретически ответ на ваш вопрос заключается в том, что это определенная реализация.
Поскольку все ваши значения уникальны и, по-видимому, являются целыми числами (которые обеспечивают очень хорошее хеширование, возможно, оптимальное — это опять-таки зависит от реализации), вы не столкнетесь с этим наихудшим сценарием. insert / find / delete будет O (1), так что это выглядит как разумный выбор.
Другие решения
В зависимости от реализации алгоритма хеширования упорядоченный набор данных может привести к множеству коллизий при использовании unordered_map. Поскольку ваши данные упорядочены, может быть более выгодно использовать набор деревьев (при условии, что вы не хотите добавлять дублирующиеся данные).