Kako se elementi čuvaju u kontejneru std::unordered_map?

std::unordered_map в C++ реализован как хеш-таблица. Элементы хранятся в бакетах (корзинах), каждый из которых содержит цепочку элементов с одинаковым хешем (обычно связный список или другой контейнер).

Основные моменты хранения:

• Ключи хешируются с помощью хеш-функции (по умолчанию std::hash<Key>).
• Хеш определяет индекс бакета, куда помещается элемент.
• В бакете элементы хранятся в виде списка для разрешения коллизий.
• При добавлении элемента вычисляется хеш, выбирается бакет, и элемент добавляется в цепочку.
• При поиске сначала вычисляется хеш, выбирается бакет, затем перебираются элементы в бакете для поиска по ключу.

Такой подход обеспечивает амортизированное время доступа близкое к O(1), но порядок элементов не гарантируется и может меняться при перераспределении (rehash).