Блог пользователя tamir

unordered_map & unordered_set
Автор tamir, 11 лет назад, По-русски

Привет! Объясните структуры данных unordered_map,unordered set(с примерами) и какую роль данные структуры данных играют в олимпиадном программировании. Я читал про них в сети, но большинство материала на английском языке. Я понял, что unordered_map не сортирует данные по ключу(как map) и доступ осуществляется быстрее чем в map из-за непонятных buckets (хэширования ключа?). С unorder_set тоже самое насчет доступа и неотсортированности. Спасибо за внимание!

  • Проголосовать: нравится
  • -14
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Я тоже такое видел, но забыл спросить

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

RTFM
и ещё

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Это хеш-таблицы. Ключи по умолчанию хешируются функтором std::hash<T>. Можно притворяться, что каждый доступ к элементу по ключу стоит столько же, сколько один вызов хеш-функции плюс O(1). Есть unordered_map, unordered_multimap, unordered_set и unordered_multiset, и разница между ними такая же, как между map, multimap, set и multiset. Разница же между первым набором и вторым набором, как уже замечено, в том, что это — хеш-таблицы с операциями за практически константное время и отсутствием сортировки, а то — сбалансированные бинарные деревья поиска (на практике — конкретно красно-чёрные деревья) с операциями за гарантированное логарифмическое время и автоматической сортировкой.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А можете объяснить как работает std::hash<T> и часто ли случаются коллизий? И как часто он используется в решений олимпиадных задач?

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

      hash, в случае строк я предполагаю, использует полиномиальное хеширование.

      Коллизии встречаются довольно редко, но даже если и случаются, обрабатываются правильно и на асимптотику почти никак не влияют. При желании почитай в википедии (желательно английской) про хеш-таблицы, там все хорошо описано.

      В олимпиадных задачах, на самом деле хеши применяются редко (как правило только в задачах на строки) и обычно пишутся самостоятельно. Например, std::hash (если я ничего не путаю) не поддерживает хеши на префиксах, и соответственно на подотрезках. Так что, я бы не стал на std::hash полагаться

      UPD. А еще и там много коллизий, как оказалось. Я был неправ тогда

      → Ответить