Как std::unordered_map находит значения?

При переборе неупорядоченной карты значений 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 использует хеширование (ключа).
Jarod42 25.12.2022 00:40

Спасибо за исправление, на самом деле я хотел спросить о std::unordered_map, который, как мне кажется, хешируется.

zantezuke 25.12.2022 00:40

почему бы не посмотреть на реализацию вашей цепочки инструментов, в заголовочном файле (файлах)

pm100 25.12.2022 00:42

Проверьте реализацию вашего компилятора std::unordered_map.

digito_evo 25.12.2022 00:43

Немного упрощая, он должен выглядеть примерно так: std::vector<std::list<std::pair<KEY, VALUE>>> Хэш предоставляет индекс в vector, а затем он усердно копается в list коллизиях. Если хеш-функция плохая, вы в основном получаете связанный список.

user4581301 25.12.2022 00:43

Зачем нужно хэшировать всю пару?

harold 25.12.2022 00:47

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

JaMiT 25.12.2022 00:49

Моя "соломенная тарелка" точно была непреднамеренной. XD Я считаю, что мое неправильное предположение заключалось в том, как элементы хранились в неупорядоченной карте, что-то, что было прояснено.

zantezuke 25.12.2022 01:23
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
8
136
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Давайте представим, что карта действительно является одним вектором:

std::vector<std::pair<Foo, Bar>> container;

Легко представить, что перебор этого контейнера перебирает std::pairs двух классов.

Настоящая неупорядоченная карта работает так же, за исключением того, что вместо вектора карта хранит std::pair<Foo, Bar>s в хеш-таблице с дополнительными указателями, которые сшивают всю хэш-таблицу вместе, которые не отображаются через итераторы карты.

То, как ассоциативные контейнеры, такие как карты, нечетко объясняются и описываются — как поиск по ключу/значению — звучит так, как будто в картах ключи и значения хранятся отдельно: вот хеш-таблица ключей, и каждый ключ указывает на соответствующее ему значение. Однако это не так. Ключ и его значение хранятся вместе, тесно связаны в дискретных std::pair объектах, а внутренняя структура карты упорядочивает их в хэш-таблице, которую итератор знает, как перебирать.

Итак, если внутренняя структура представляет собой что-то вроде списка пар, как узнать, какая пара имеет хешированный ключ?

Ни один. Неупорядоченную карту можно условно описать как:

std::vector<std::list<std::pair<Key, Value>>>

Хэш ключа — это индекс в векторе. Все Key в i-й позиции в этом векторе имеют одинаковое хеш-значение. Все ключи с одинаковым хешем хранятся в одном связанном списке.

Другие вопросы по теме