C ++: Как неупорядоченные контейнеры предотвращают дублирование?

Question

Давайте возьмем unordered_set для примера. Предикат по умолчанию для определения, равны ли два элемента, равен std::equal_to<T>(t1,t2), то есть просто t1==t2. Теперь давайте предположим, что для этого типа T я реализовал operator==(), так что не все переменные-члены являются частью этого сравнения, то есть два разных элемента T t1, t2 могут быть равны при сравнении.

Если базовый hashtable вычисляет разные значения ha sh для каждого из этих t1 и t2, когда он даже выполняет проверку t1==t2 на дублирование ключей? и если есть больше проверок, как оно остается в среднем постоянным?

Answer 1

Я думаю, что ключевым моментом, который вам не хватает, является то, что вы поставляете два функтора в неупорядоченный контейнер, и они должны работать вместе.

Есть функция ha sh, которая вычисляет число из объект.

Есть функция сравнения, которая сравнивает два объекта на "эквивалентность".

Как сказал @Eljay в своем комментарии, для двух объектов, которые сравнивают "эквивалент" (функция сравнения возвращает true), функция ha sh должна возвращать то же значение.

Если ваши функции не предоставляют эту гарантию, контейнеры не будут работать правильно.

Относительно хорошая ссылка (хотя и не является достоверной)

std :: unordered_set : соответствует требованиям UnorderedAssociativeContainer.
UnorderedAssociativeContainer : параметризованы с помощью Key / Hash / Pred.
С требованием:
* Если два ключа равны согласно Pred.
* Ха sh должен возвращать одинаковое значение для обеих клавиш.

Answer 2

Для неупорядоченных ассоциативных контейнеров требуется, чтобы любые два равных ключа также имели одинаковое значение ha sh. From [unord.req] :

Объект контейнера типа Hash, обозначаемый hash, называется функцией ha sh контейнера. Объект контейнера типа Pred, обозначенный pred, называется предикатом равенства ключей контейнера.

Два значения k1 и k2 считаются эквивалентными, если предикат равенства ключей контейнера pred(k1, k2) является действительным и возвращает true при передаче этих значений. Если k1 и k2 эквивалентны, функция ha sh контейнера должна возвращать одинаковое значение для обоих.

Ваши реализации operator== и std::hash должны быть согласованными. Если это не так, вы не выполнили предварительные условия, необходимые для использования вашего класса в качестве ключа в неупорядоченном ассоциативном контейнере.

Answer 3

Если базовая хеш-таблица вычисляет разные значения ha sh для каждого из этих t1 и t2, когда она даже выполняет проверку t1 == t2 на дублирование ключей?

Когда функция ha sh заставляет вновь вставленный элемент помещаться в непустое ведро. Будет проведено сравнение между ранее существовавшими элементами в этом сегменте, чтобы обеспечить уникальность.

как он остается в среднем постоянным?

Предполагая, что га * Функция 1026 * равномерно распределяет случайные ключи в сегменты, увеличивая количество блоков по мере увеличения количества элементов.

как std :: ha sh узнает, как реализовать openrator == ()

Кто бы ни писал специализацию std :: ha sh для вашего класса, он должен знать, как вы реализуете оператор ==.

Функция ha sh должна выдавать то же самое га sh для всех сравниваемых элементов. Если этого не произойдет, то поведение программы будет неопределенным. Стандартные ссылки: [unord.req] , [defns.required.behavior]