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