Краткий ответ

reserve заранее увеличивает число бакетов так, чтобы контейнер мог вместить указанное количество элементов при текущем max_load_factor без вынужденных повторных рехеширований. Это обычно снижает суммарные издержки вставки, но не резервирует память под сами узлы элементов и не гарантирует заданное точное число бакетов.

Исторический контекст

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

Предварительное резервирование решает проблему серии дорогостоящих расширений при загрузке большого объёма данных, когда целевой размер известен заранее.

Постановка проблемы

Если вставлять элементы по одному в пустой std::unordered_map, контейнер время от времени увеличивает число бакетов. При каждом таком изменении существующие элементы могут быть перераспределены по новым бакетам, что даёт существенные дополнительные расходы.

Кроме того, рехеширование инвалидирует итераторы контейнера. Поэтому во время массовой загрузки оно может не только ухудшить производительность, но и нарушить логику кода, который хранит итераторы между вставками.

Подробное решение

Вызов reserve(n) просит контейнер подготовить вместимость как минимум для n элементов с учётом текущего значения max_load_factor. Реализация выбирает подходящее число бакетов, поэтому фактическая вместимость может оказаться больше запрошенной.

После этого вставка до примерно n элементов обычно не требует рехеширования, если значение max_load_factor не изменяется. Однако память под объекты элементов, как правило, выделяется отдельно при каждой вставке: reserve резервирует структуру бакетов, а не непрерывный массив узлов.

#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> users;
    users.reserve(100000);

    for (int id = 0; id < 100000; ++id)
        users.emplace(id, "user");
}

Вызов rehash(k) отличается тем, что задаёт минимальное число бакетов, а reserve(n) — минимальное число элементов, которое контейнер должен вместить при текущем коэффициенте загрузки. Для обычной подготовки к известному числу вставок следует использовать именно reserve.

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

Ситуация из практики

Сервис загружает из файла 500 тысяч записей в std::unordered_map. Без предварительной подготовки контейнер несколько раз увеличивает таблицу бакетов и перераспределяет уже загруженные элементы.

Вариант без reserve проще, но платит повторными рехешированиями. Вариант с вызовом reserve(500000) требует знать или оценить объём заранее, зато обычно уменьшает количество перераспределений и делает время загрузки более предсказуемым.

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

Что кандидаты часто упускают

Вопрос: гарантирует ли reserve(n) ровно n бакетов?

Ответ: нет. Аргумент означает требуемое число элементов, а не бакетов. Контейнер выбирает число бакетов так, чтобы вместить это количество при текущем max_load_factor; фактическое значение может быть больше и зависит от реализации.
Вопрос: означает ли успешный reserve отсутствие любых дальнейших выделений памяти?

Ответ: нет. Он подготавливает массив бакетов, но отдельные элементы std::unordered_map обычно размещаются в отдельных узлах. При последующих вставках память под ключи, значения и узлы всё ещё может выделяться.
Вопрос: что произойдёт, если после reserve уменьшить max_load_factor?

Ответ: прежней подготовленной вместимости может оказаться недостаточно при новом, более строгом ограничении загрузки. Следующая вставка способна вызвать рехеширование, поэтому reserve следует выполнять после настройки max_load_factor, если она изменяется.