1

Почему std::unordered_set принимает функцию сравнения двух элементов на равенство, а не отношение меньше? Ведь в таком случае можно вывести при необходимости равенство как !(a<b)&&!(b<a), а также отсортировать ключи с одинаковым значением хеш-функции, чтобы потом выполнять не линейный поиск в бакете, а бинарный.

4
  • отсортировать ключи с одинаковым значением хеш-функции никак не получится, поскольку речь идет об std::unordered_set, который хранит только уникальные элементы (их значения не могут быть одинаковыми), а сравнение на равенства двух элементов исходит из логики того, что иное сравнение не нужно в контейнере 2 дек 2018 в 11:10
  • @ARHovsepyan значения элементов могут быть одинаковыми, смотрите мой предыдущий вопрос 2 дек 2018 в 11:12
  • Не понимаю на что мне смотреть, если по факту std::unordered_set не является контейнером std::unordered_multiset... Из них только второй может иметь элементы с одинаковым значением. А если вы все таки хотите доказывать обратное, Бог вам в помощь... 2 дек 2018 в 11:31
  • Значения хэша могут быть одинаковым, но значения обьектов разные, а отсортировать их как вы собираетесь непонятно... 2 дек 2018 в 11:41

1 ответ 1

1

Отношение "меньше" более строгое (строгое слабое упорядочение, поищите в Гугле - RuSO не разрешает ссылку вставить...), чем отношение равенства (ну, например, детскую игру "бумага-ножницы-камень" знаете? Равенство есть, а нормального отношения "меньше" - нет). Это наложило бы лишнее ограничение на хранимые данные, при том, что выигрыша в скорости практически не дало бы (подробнее всю математику хеширования см. в книгах Кнута, например, или Кормена - здесь всю ее расписывать смысла нет).

При хорошей хеш-функции получаем время поиска O(1), ну, а если функция такая, что вопрос уже встает о том, чтобы искать значение бинарным поиском - то проще использовать обычный set...

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.