При переборе неупорядоченной карты значений std::unordered_map<Foo, Bar>
будет использоваться итератор, указывающий на значения в std::pair<Foo, Bar>
. Это создает впечатление, что std::unordered_map хранит свои значения внутри как std::pairs значений.
Если я не ошибаюсь, std::unordered_map работает, хешируя ключ и используя его для поиска. Итак, если внутренняя структура представляет собой что-то вроде списка пар, как узнать, какая пара имеет хешированный ключ? Разве не нужно будет хешировать всю пару, включая значение?
Если внутренняя структура не содержит пар, вызывает ли вызов std::unordered_map::begin() затем создание объекта std::pair с использованием данных на карте? Тогда каким образом изменение данных в паре также изменяет данные на самой карте?
Спасибо.
Спасибо за исправление, на самом деле я хотел спросить о std::unordered_map
, который, как мне кажется, хешируется.
почему бы не посмотреть на реализацию вашей цепочки инструментов, в заголовочном файле (файлах)
Проверьте реализацию вашего компилятора std::unordered_map
.
Немного упрощая, он должен выглядеть примерно так: std::vector<std::list<std::pair<KEY, VALUE>>>
Хэш предоставляет индекс в vector
, а затем он усердно копается в list
коллизиях. Если хеш-функция плохая, вы в основном получаете связанный список.
Зачем нужно хэшировать всю пару?
«Итак, если внутренняя структура представляет собой что-то вроде списка пар, как узнать, какая пара имеет хешированный ключ?» -- Извините, я не понимаю логики этого. Похоже на непреднамеренный аргумент соломенного человека. (Что, я полагаю, означает, что у этого есть предположение, которое вы должны подвергнуть сомнению.)
Моя "соломенная тарелка" точно была непреднамеренной. XD Я считаю, что мое неправильное предположение заключалось в том, как элементы хранились в неупорядоченной карте, что-то, что было прояснено.
Давайте представим, что карта действительно является одним вектором:
std::vector<std::pair<Foo, Bar>> container;
Легко представить, что перебор этого контейнера перебирает std::pair
s двух классов.
Настоящая неупорядоченная карта работает так же, за исключением того, что вместо вектора карта хранит std::pair<Foo, Bar>
s в хеш-таблице с дополнительными указателями, которые сшивают всю хэш-таблицу вместе, которые не отображаются через итераторы карты.
То, как ассоциативные контейнеры, такие как карты, нечетко объясняются и описываются — как поиск по ключу/значению — звучит так, как будто в картах ключи и значения хранятся отдельно: вот хеш-таблица ключей, и каждый ключ указывает на соответствующее ему значение. Однако это не так. Ключ и его значение хранятся вместе, тесно связаны в дискретных std::pair
объектах, а внутренняя структура карты упорядочивает их в хэш-таблице, которую итератор знает, как перебирать.
Итак, если внутренняя структура представляет собой что-то вроде списка пар, как узнать, какая пара имеет хешированный ключ?
Ни один. Неупорядоченную карту можно условно описать как:
std::vector<std::list<std::pair<Key, Value>>>
Хэш ключа — это индекс в векторе. Все Key
в i
-й позиции в этом векторе имеют одинаковое хеш-значение. Все ключи с одинаковым хешем хранятся в одном связанном списке.
std::unordered_map
использует хеширование (ключа).