Можно ли зарезервировать элементы (узлы) для std::unordered_map?
Скажите, пожалуйста, есть ли способ заставить std::unordered_map зарезервировать не только слоты (buckets), но и узлы?
Ответы (1 шт):
Нет.
Резервирование служит для уменьшения количества реаллокаций. Работает для контейенров типа vector, когда при добалвении очередного элемента старые элементы перемещаются в бОльшую выделенную область. Оно является оптимизацией, позволяющей сразу выделить такую область.
Для unordered_map стандарт требует, чтобы при удалении любого элемента инвалидировались только итераторы и ссылки на него, но никакие другие итераторы и ссылки, и при добавлении тоже ничего не инвалидировалось. Соотвественно контейнер, которому резервирование помогло бы избежать реаллокацию, там нельзя всунуть: реаллокаций в любом случае не будет, ибо они запрещены.
По факту там (одно или дву)связный список в каждой корзине. При этом, оптимистично ожидается, что в корзине обычно не более одного элемента, для этого корзин сильно больше, чем нужно, и многие пустуют. Соотвественно, попытки предвыделять узлы, или иметь более одного элемента в узле были бы пессимизацией.
Вообще задачу оптимизации выделения unordered_map решить можно либо своим аллокатором, либо отказом от unordered_map (в пользу других типов хеш-таблиц, например)