Контейнеры состоят из нескольких «ковш», каждое из которых может содержать любое количество элементов. Например, на следующей диаграмме показано<unordered_set>с 7 ведрами, содержащими 5 элементов,<A>,<B>,<C>,<D>и<E>(это только для иллюстрации, контейнеры обычно имеют больше ведер).

Чтобы решить, в какое ведро поместить элемент, контейнер применяет хеш-функцию<Hash>к ключу элемента (для<unordered_set>и<unordered_multiset>ключ является целым элементом, но упоминается как ключ, так что та же терминология может использоваться для наборов и карт). Это возвращает значение типа<std::size_t>.<std::size_t>имеет гораздо больший диапазон значений, чем число ведер, так что контейнер применяет другое преобразование к этому значению, чтобы выбрать ведро для размещения элемента.

Получение элементов для данного ключа просто. Тот же процесс применяется к ключу, чтобы найти правильное ведро. Затем ключ сравнивают с элементами в ведре, чтобы найти любые элементы, которые соответствуют (используя предикат равенства<Pred>). Если хеш-функция сработала хорошо, элементы будут равномерно распределены между ведрами, поэтому необходимо будет изучить только небольшое количество элементов.

Более подробная информация о хеш-функциях и предикатах равенства содержится в следующем разделе.

Controlling the number of buckets

По мере добавления большего количества элементов в неупорядоченный ассоциативный контейнер количество элементов в ведрах будет увеличиваться, вызывая ухудшение производительности. Для борьбы с этим контейнеры увеличивают количество ведра по мере вставки элементов. Вы также можете сказать контейнеру изменить счет ведра (если требуется), позвонив<rehash>.

Стандарт оставляет большую свободу для исполнителя, чтобы решить, как количество ведер выбрано, но он делает некоторые требования, основанные на «факторе нагрузки» контейнера, среднем количестве элементов на ведро. Контейнеры также имеют «максимальный коэффициент нагрузки», который они должны стараться поддерживать ниже.

Вы не можете контролировать количество ведра напрямую, но есть два способа повлиять на него:

<max_load_factor>не позволяет установить максимальный коэффициент нагрузки самостоятельно, он просто позволяет датьподсказку. И даже в этом случае проект стандарта не требует от контейнера особого внимания к этому значению. Единственный раз, когда коэффициент нагрузкитребуется, чтобы быть меньше максимального, после вызова<rehash>. Но большинство реализаций будут стараться удерживать количество элементов ниже максимального коэффициента нагрузки и устанавливать максимальный коэффициент нагрузки таким же, как и или близкий к подсказке, если только подсказка не является необоснованно маленькой или большой.

Iterator Invalidation

Не уточняется, каким образом функции члена, отличные от<rehash>, влияют на количество ковшов, хотя<insert>разрешается обесценивать итераторы только тогда, когда вставка приводит к тому, что коэффициент нагрузки превышает или равен максимальному коэффициенту нагрузки. Для большинства реализаций это означает, что вставка изменит только количество ведер, когда это произойдет. Несмотря на то, что итераторы могут быть признаны недействительными по вызовам<insert>и<rehash>, указатели и ссылки на элементы контейнера никогда не признаются недействительными.

Аналогично использованию<reserve>для<vector>s, может быть хорошей идеей позвонить<rehash>, прежде чем вставлять большое количество элементов. Это приведет к дорогостоящей перетасовке и позволит вам хранить итераторы, зная, что они не будут признаны недействительными. Если вы вставляете<n>элементов в контейнер<x>, вы можете сначала позвонить:

x.rehash((x.size() + n) / x.max_load_factor() + 1);