Почему std::unordered_set повторно хешируется, даже если предел коэффициента загрузки не нарушен?

Согласно cppreference,

Повторное хэширование происходит только в том случае, если новое количество элементов больше max_load_factor()*bucket_count().

Кроме того, [unord.req]/15 имеет аналогичные правила. :

Элементы insert и emplace не должны влиять на достоверность итераторов, если (N+n) <= z * B, где N — количество элементов в контейнере до операции вставки, n — количество вставленных элементов, B — количество сегментов контейнера, а z — количество элементов в контейнере. максимальный коэффициент загрузки контейнера.

Однако рассмотрим следующий пример:

#include <unordered_set>
#include <iostream>

int main()
{
    std::unordered_set<int> s;
    s.emplace(1);
    s.emplace(42);
    std::cout << s.bucket_count() << ' ';
    std::cout << (3 > s.max_load_factor() * s.bucket_count()) << ' ';
    s.emplace(2);
    std::cout << s.bucket_count() << ' ';
}

С GCC 8.0.1 он выводит

3 0 7

Это означает, что после замены 2 происходит перефразирование, хотя новое количество элементов (3) не больше max_load_factor()*bucket_count() (обратите внимание, что второй результат равен 0). Почему это происходит?


c++ hash stl unordered-set
person xskxzr    schedule 17.03.2018    source источник

Ответы (3)


arrow_upward
3
arrow_downward

Вы путаете тот факт, что bucket_count() изменилось с аннулированием итераторов. Итераторы становятся недействительными только в случае повторного хеширования, которое не будет единицей, если новое количество элементов меньше или равно max_load_factor()*bucket_count() (кстати, если size()>max_load_factor()*bucket_count() повторное хеширование может происходить, но не обязательно).

Поскольку в вашем примере это было не так, перефразирования не произошло, и итераторы остаются действительными. Однако для размещения нового элемента количество ведер пришлось увеличить.

Я немного поэкспериментировал (расширяя ваш код) с clang Mac OSX, который сохранял итераторы действительными даже после rehash(size()) (что действительно изменило ассоциацию корзины элемента, проверенную непосредственно путем повторения корзин и печати их содержимого).

person Walter    schedule 17.03.2018
comment
Если вы измените 42 на 41 в моем примере и выведете s.bucket(41) до и после s.emplace(2), вы наблюдаете два разных результата< /а>. Не означает ли это, что действительно есть перефразирование? - person xskxzr; 17.03.2018
comment
Индекс сегмента (который возвращает bucket()) может/изменяется, даже если сам сегмент остается прежним. - person Walter; 17.03.2018
comment
Посмотрите на это, индекс корзины 1 и корзины 40 одинаковы до s.emplace(2), но становятся отличается после s.emplace(2), как вы это объясните? - person xskxzr; 18.03.2018

arrow_upward
2
arrow_downward

Из 26.2.7 Неупорядоченные ассоциативные контейнеры

Количество сегментов автоматически увеличивается по мере добавления элементов в неупорядоченный ассоциативный контейнер, чтобы среднее количество элементов на сегмент не превышало предела.

b.load_factor()           Returns the average number of elements per bucket.

b.max_load_factor()       Returns a positive number that the container attempts 
                          to keep the load factor less than or equal to. The container
                          automatically increases the number of buckets as necessary
                          to keep the load factor below this number.

Я согласен, первая часть описания max_load_factor предполагает, что коэффициент загрузки может достигать этого значения, но во второй части и в предыдущей цитате четко указано, что коэффициент загрузки будет ниже этого значения. Итак, вы нашли ошибку в cppreference.

В вашем коде без перефразирования после третьей вставки s.load_factor будет равно s.max_load_factor().

РЕДАКТИРОВАТЬ: Чтобы ответить на изменения в вопросе, который я проверил, доступная мне реализация VS unordered_set, она реализована как

// hash table -- list with vector of iterators for quick access

а затем вы запрашиваете итератор, используя, например. lower_bound, вы получаете итератор для элемента списка, который не становится недействительным при повторном хешировании. Итак, это согласуется с [unord.req]/15.

person Yola    schedule 17.03.2018
comment
Но [unord.req]/15 согласуется с описанием cppreference. - person xskxzr; 17.03.2018
comment
@xskxzr да, и итераторы не становятся недействительными после этой операции. Интересное открытие :) - person Yola; 17.03.2018

arrow_upward
2
arrow_downward

Условие перефразирования изменено с выпуска 2156. Перед изменением перефразирование происходит, когда новое количество элементов не меньше max_load_factor()*bucket_count(), а после изменения оно становится "больше".

GCC 8.0.1 не реализует это изменение. Уже есть отчет об ошибке, и он был исправлен в GCC. 9.

person xskxzr    schedule 23.02.2019