Принимает ли std :: unordered_set амортизированное постоянное время поиска для любого объекта независимо от предиката?
В std::unordered_setмы предоставляем предикат, чтобы указать, равны ли два объекта A и B или нет. Мой вопрос, предположим, что нам нужно O(k) время, чтобы определить, равны ли А и В или нет. Ли unordered_set::find по-прежнему берут амортизированное постоянное время или амортизируется O(k) время?
Решение
Средняя постоянная сложность поиска гарантируется std::unordered_map относится только к количеству элементов на карте. Если карта содержит хотя бы один элемент с таким же хеш-значением *), она должна выполнить хотя бы одно полное сравнение ключа. Если это сравнение O (k), то, очевидно, поиск также становится O (k), но это должно иметь значение только для довольно больших k.
*) Я полагаю, что в большинстве реализаций это не просто один и тот же хэш, но если в одном сегменте есть элемент.
Другие решения
Других решений пока нет …