Поиск std :: unordered_set по хеш-значению и предикату - PullRequest
3 голосов
/ 13 октября 2010

Как я могу найти std :: unordered_set, зная значение хеша и имея некоторый объект предиката? (Предикат, определяющий эквивалентность по pred(x) && pred(y), что означает x == y.)

1 Ответ

3 голосов
/ 13 октября 2010

Ну, вы можете игнорировать значение хеша и повторять все unsorted_set тестирование предиката. Не идеальная эффективность, так как вы бы предпочли итерировать только одну корзину, но она выполняет то, что вы просите.

Стандартный unordered_set имеет интерфейс begin(size_t) для получения итератора для определенного сегмента (по номеру) и интерфейс bucket_count() для получения количества сегментов.

Все объекты с заданным хешем гарантированно появляются в одном и том же сегменте, поэтому итерации, что тестирование предиката достаточно для того, что вы хотите сделать.

На самом деле я не вижу ничего в стандарте, чтобы гарантировать правильную последовательность для повторения hash_value % bucket_count(). Есть функция для получения корзины для данного объекта , но не для получения корзины для данного хеш-значения . Попробуйте это в своей реализации, хотя: я думаю, что это разумное предположение, и, возможно, я просто не смог найти решающее ограничение в стандарте.

В итоге, я думаю, вы хотите что-то вроде:

size_t bucket = hash_value % myset.bucket_count();
find_if(myset.begin(bucket), myset.end(bucket), pred);

но я не уверен.

...