Почему у std :: unordered_map есть резервный метод?

Question

По this Вы не можете зарезервировать место для std::map:

Нет, члены карт хранятся во внутренней памяти в виде древовидной структуры. Невозможно построить дерево до тех пор, пока вы не узнаете ключи и значения , которые должны быть сохранены.

Отсюда понятно, почему std::map бы не хватает reserve() метод, который он делает на cppreference.com. Тем не менее, std::unordered_mapделает есть метод reserve(), но когда я пытаюсь использовать его с operator[], insert() или emplace() все они идут выделить память, несмотря на меня, назвав reserve() первым.

Что случилось с этим? Почему reserve() не резервирует требуемое пространство? И если это так, как с картой, которую вы не можете заранее выделить памятью, то почему у std::unordered_map даже есть метод reserve()?

Answer 1

Контейнер unordered_map имеет метод reserve, поскольку он выполнен с использованием ведер, а не дерева, как в map.

ведро является:

слот в контейнера внутренней хэш-таблицы, в которой элементы назначаются на основе хэш-значения их ключа. Ковши пронумерованы от 0 до (bucket_count-1). (source)

В одном ведре содержится переменное количество предметов. Этот номер основан на load_factor. Когда load_factor достигает определенного порога, контейнер увеличивает количество ведер и перефразирует карту.

Когда вы звоните reserve(n), контейнер создает достаточное количество ведер для хранения не менее n элементов.

Это отличие от rehash(n), который непосредственно устанавливает количество ведер до n и запускает перестройку всей хеш-таблицы.

Смотрите также: Pre-allocating buckets in a C++ unordered_map

Редактировать в ответ на комментарии

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

Для справки, вопрос сводится к тому:

Не могли бы вы объяснить, если резервирование ковши для п элементов такое же, как выделение памяти для п элементов?

В соответствии с this answer, точно извлечением размера выделенного пространства в качестве unordered_map является сложным и ненадежным.Поэтому я решил использовать диагностические инструменты Visual Studio 2015.

Во-первых, мой тест выглядит следующим образом:

#include <unordered_map> 
#include <cstdint> 

struct Foo 
{ 
    Foo() : x(0.0f), y(0.0f), z(0.0f) { } 

    float x; 
    float y; 
    float z; 
}; 

int32_t main(int32_t argc, char** argv) 
{ 
    std::unordered_map<uint32_t, Foo> mapNoReserve; 
    std::unordered_map<uint32_t, Foo> mapReserve; 

    // --> Snapshot A 

    mapReserve.reserve(1000); 

    // --> Snapshot B 

    for(uint32_t i = 0; i < 1000; ++i) 
    { 
     mapNoReserve.insert(std::make_pair(i, Foo())); 
     mapReserve.insert(std::make_pair(i, Foo())); 
    } 

    // -> Snapshot C 

    return 0; 
} 

Где комментарии показывают, я сделал снимок памяти.

Результаты были следующими:

Снимок A:

┌──────────────┬──────────────┬──────────────┐ 
|  Map  | Size (Bytes) | Bucket Count | 
|--------------|--------------|--------------| 
| mapNoReserve | 64   | 8   | 
| mapReserve | 64   | 8   | 
└──────────────┴──────────────┴──────────────┚ 

Снимок B:

┌──────────────┬──────────────┬──────────────┐ 
|  Map  | Size (Bytes) | Bucket Count | 
|--------------|--------------|--------------| 
| mapNoReserve | 64   | 8   | 
| mapReserve | 8231   | 1024   | 
└──────────────┴──────────────┴──────────────┚ 

Снимок C:

┌──────────────┬──────────────┬──────────────┐ 
|  Map  | Size (Bytes) | Bucket Count | 
|--------------|--------------|--------------| 
| mapNoReserve | 24024  | 1024   | 
| mapReserve | 24024  | 1024   | 
└──────────────┴──────────────┴──────────────┚ 

Интерпретация:

Как видно из снимка, очевидно, что обе карты увеличиваются в размерах, как только мы начинаем добавлять элементы к ним, даже один, который называется reserve.

Так что reserve предлагает выгоду, хотя память все еще выделена? Я бы сказал «да» по двум причинам: (1) он заранее распределяет память для ведер, и (2) он может предотвратить необходимость в rehash, который, как обсуждалось ранее, полностью перестраивает карту.