3

Скажите, пожалуйста, есть ли способ заставить std::unordered_map зарезервировать не только слоты (buckets), но и узлы?

3
  • 1
    так весь смысл эффективного использования хеш таблиц в том, чтобы узлов на каждый хеш было не более 1 27 июл 2020 в 9:10
  • 1
    что именно вкладывается в понятие «зарезервировать узлы»? Может просто свой аллокатор сделать?
    – Fat-Zer
    27 июл 2020 в 14:23
  • бери какую-нибуть кастомную реализацию мапы. unordered_map хорошо показывается в отладчике, но на этом её хорошие качества и заканчиваются. 10 сен 2020 в 22:37

1 ответ 1

2

Нет.

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

Для unordered_map стандарт требует, чтобы при удалении любого элемента инвалидировались только итераторы и ссылки на него, но никакие другие итераторы и ссылки, и при добавлении тоже ничего не инвалидировалось. Соотвественно контейнер, которому резервирование помогло бы избежать реаллокацию, там нельзя всунуть: реаллокаций в любом случае не будет, ибо они запрещены.

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

Вообще задачу оптимизации выделения unordered_map решить можно либо своим аллокатором, либо отказом от unordered_map (в пользу других типов хеш-таблиц, например)

7
  • Из всего этого никак не следует того, что невозможно всунуть аллокацию памяти для конечных узлов заранее. То, что нельзя передвинуть элементы, никак не означает того, что нельзя заранее выделить под новые память. 10 сен 2020 в 22:42
  • Да, но из всего этого следует, что оно было бы бесполезно, и даже вредно 11 сен 2020 в 8:14
  • Это не бесполезно. Например для использования unordered map внутри глобального оператора new. И не вижу ничего вредного в том, чтобы использовать pool аллокатор для unordered map. 12 сен 2020 в 17:20
  • Резервировать заранее узлы таки бесполезно, потому что заранее неизвестно, в каких корзинах узлы. 13 сен 2020 в 16:58
  • Резервировать узлы вне корзин для того, чтобы не выделять память в определённый момент -- можно было бы, но это не делается. Избегание аллокаций в определённый момент не является целью reserve, это лишь сторонний эффект, цель же производительость, которой резервирование узлов не способстует 13 сен 2020 в 17:02

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.