Почему std:: unordered map имеет резервный метод?

Согласно этому вы не можете зарезервировать место для std::map:

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

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

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

1 9
c++ visual-c++ stdmap

1 ответ:

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

Ведро-это:

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

Одно ведро содержит переменное количество элементов. Это число основано на load_factor. Когда load_factor достигает a определенный порог, контейнер увеличивает количество ведер и перерисовывает карту.

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

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

Смотрите также: предварительное выделение ведер в C++ unordered_map

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

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

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

Согласно этому ответу , точно извлекая размер выделенного пространства в an 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;
}

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

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

Снимок А: 

┌──────────────┬──────────────┬──────────────┐
|     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, которая, как обсуждалось ранее, полностью перестраивает карту.

14