Как работает hash_set :: upper_bound ()?
Как работает Visual C ++ stdext::hash_set<T>::upper_bound() Работа?
Как хеш-таблица может также сортировать элементы ?!
Я пытался прочитать исходный код, но трудно расшифровать код STL … и даже концептуально я не могу понять из этого: как хэш-таблица может сравнивать элементы?
Решение
Различные unordered_xxx Шаблоны используют хэш-функцию для сортировки объектов в сегменты. Объекты, входящие в один и тот же сегмент, сгруппированы так, что объекты, сравнивающие равные, являются смежными (где «сравнить равные» означаетa < b ложно и b < a ложно, или, для версии предиката, pr(a,b) ложно и pr(b,a) ложно «). lower_bound() возвращает итератор, который указывает на первый объект, который соответствует переданному значению; upper_bound() возвращает итератор, который следует за последним объектом, который соответствует переданному значению. Там нет глобальной сортировки.
Другие решения
Хеш-таблица не должна сохранять элементы отсортированными; он просто должен сравнить любой недавно вставленный элемент с текущим наибольшим значением и соответствующим образом обновить. Не нужно сортировать.
Что касается того, как он может сравнивать элементы: для этого и нужны операторы. Пока тип <T> реализует оператор ‘>’, он может быть отсортирован. Вы можете написать свой собственный оператор> для своего класса, хотя он должен поддерживать строгий порядок (например, при сравнении «abc» с «abcdef» вы должны решить, какой из них «больше» в этом случае).