Привет! Объясните структуры данных unordered_map,unordered set(с примерами) и какую роль данные структуры данных играют в олимпиадном программировании. Я читал про них в сети, но большинство материала на английском языке. Я понял, что unordered_map не сортирует данные по ключу(как map) и доступ осуществляется быстрее чем в map из-за непонятных buckets (хэширования ключа?). С unorder_set тоже самое насчет доступа и неотсортированности. Спасибо за внимание!
Я тоже такое видел, но забыл спросить
RTFM
и ещё
Здесь я был уже — не очень понятно(
Это хеш-таблицы. Ключи по умолчанию хешируются функтором
std::hash<T>
. Можно притворяться, что каждый доступ к элементу по ключу стоит столько же, сколько один вызов хеш-функции плюс O(1). Естьunordered_map
,unordered_multimap
,unordered_set
иunordered_multiset
, и разница между ними такая же, как междуmap
,multimap
,set
иmultiset
. Разница же между первым набором и вторым набором, как уже замечено, в том, что это — хеш-таблицы с операциями за практически константное время и отсутствием сортировки, а то — сбалансированные бинарные деревья поиска (на практике — конкретно красно-чёрные деревья) с операциями за гарантированное логарифмическое время и автоматической сортировкой.А можете объяснить как работает
std::hash<T>
и часто ли случаются коллизий? И как часто он используется в решений олимпиадных задач?hash, в случае строк я предполагаю, использует полиномиальное хеширование.
Коллизии встречаются довольно редко, но даже если и случаются, обрабатываются правильно и на асимптотику почти никак не влияют. При желании почитай в википедии (желательно английской) про хеш-таблицы, там все хорошо описано.
В олимпиадных задачах, на самом деле хеши применяются редко (как правило только в задачах на строки) и обычно пишутся самостоятельно. Например, std::hash (если я ничего не путаю) не поддерживает хеши на префиксах, и соответственно на подотрезках. Так что, я бы не стал на std::hash полагаться
UPD. А еще и там много коллизий, как оказалось. Я был неправ тогда