Роль std :: unordered_set :: reserve для требования к памяти контейнера?

Question

Предположим, я использую std::unordered_set<MyClass>, и предположим, что sizeof(MyClass) велико, то есть намного больше , чем sizeof(size_t) и sizeof(void*).Я добавлю большое количество numberOfElementsToBeAdded элементов в неупорядоченный набор.

Начиная с https://stackoverflow.com/a/25438497/4237, я нахожу: «каждое выделение памяти может быть округлено до размера, удобного для управления библиотекой выделения памяти - например, следующая степень двух, которая приближается к 100% неэффективности в худшем случаеи 50% в среднем, поэтому давайте добавим 50%, только для узлов списка, так как сегменты, вероятно, являются степенями двух заданных size_t и указателя: 50% * size () * (sizeof (void *) + sizeof ((M ::)value_type)) "

Это заставляет меня сделать вывод, что фактическое потребление памяти будет между 1*numberOfElements*sizeof(MyClass) и (1+1)*numberOfElements*sizeof(MyClass), по модулю некоторой дополнительной памятью, которая здесь не представляет большого интереса, посколькупорядка sizeof(size_t).

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

std::unordered_set<MyClass> set;
set.reserve(numberOfElementsToBeAdded);
//Insert elements

Думая о параллельности вызова std :: vector:: резерв, я бы предположил, что это позволяет избежать потенциальных издержек и, таким образом, гарантирует потребление памяти примерно 1*numberOfElements*sizeof(MyClass) (по модулю некоторой дополнительной памяти, снова порядка sizeof(size_t)).

Могу ли я рассчитыватьв реализациях стандартной библиотеки, чтобы гарантировать, что вызов reserve, подобный этому, позволит избежать издержек на 0-100% (в среднем 50%), упомянутых в ответе выше?

Answer 1

С это std::unordered_set::reserve ссылка

Устанавливает количество ведер на количество, необходимое для размещения не менее count элементов ...

Есть еще кое-что, но суть в том, что std::unordered_set::reserve на самом деле не работает как std::vector::reserve. Для неупорядоченного набора он выделяет сегменты для хеш-таблицы, а не память для самих элементов.

Набор может помещать по одному элементу в корзину, но это не гарантируется.

Answer 2

При цитировании стандарта:

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

Важной частью является ** по крайней мере *. Я не думаю, что вы можете положиться на реализацию и быть уверенным, что она использует только меньше памяти. Я предполагаю, что независимо от того, если вы позвоните reserve, использование памяти для numElements будет одинаковым.