Предварительное выделение ковшей в С++ unordered_map

Я использую unordered_map из gnu ++ 0x для хранения огромного количества данных. Я хочу предварительно выделить пространство для большого количества элементов, так как я могу связать используемое общее пространство.

То, что я хотел бы сделать, это позвонить:

std::unordered_map m;
m.resize(pow(2,x));

где x известно.

unordered_map не поддерживает это. Я предпочел бы использовать unordered_map, если это возможно, так как он в конечном итоге станет частью стандарта.

Некоторые другие ограничения:

Нужен надежный O (1) доступ и мутация карты. Желаемые функции хэша и сравнения уже нестандартны и несколько дороги. O (log n) (как и для std:: map) слишком дорого.

- > Дорогие хеш и сравнение также делают слишком дорогостоящим рост амортизации. Каждая дополнительная вставка требует O (n) операций от этих функций, что приводит к добавлению дополнительного квадратичного термина в время выполнения алгоритма, так как требования к экспоненциальному хранению требуют O (n) роста.

Ответ 1

m.rehash(pow(2,x));

если pow(2, x) - количество ведер, которые вы хотите предварительно распределить. Вы также можете:

m.reserve(pow(2,x));

но теперь pow(2, x) - количество элементов, которые вы планируете вставлять. Обе функции ничего не делают, кроме предустановленных ведер. Они не вставляют никаких элементов. И оба они предназначены для использования именно в вашем случае использования.

Примечание. Вы не можете получить точно pow(2, x) ковши. В некоторых реализациях будет использоваться только несколько ковшей, мощность которых равна 2. В других реализациях будет использоваться только простое количество ковшей. Третьи будут использовать только подмножество простых чисел для количества ведер. Но в любом случае реализация должна принять ваш намек на количество желаемых ведер, а затем внутренне округлить до следующего допустимого количества ведер.

Вот точная формулировка, которую использует последний (N4660) для указания аргумента rehash:

a.rehash(n): Постусловия: a.bucket_count() >= a.size() / a.max_load_factor() and a.bucket_count() >= n.

Это постусловие гарантирует, что bucket()_count() >= n и что load_factor() остается меньше или равно max_load_factor().

Впоследствии reserve(n) определяется в терминах rehash(n):

a.reserve(n): То же, что a.rehash(ceil(n / a.max_load_factor())).

Ответ 2

Я не думаю, что для неупорядоченной карты важно иметь предварительно выделенную память. Ожидается, что STL будет O (n) амортизированным временем вставки. Спасите себя от хлопот написания своего распределителя, пока вы не узнаете, что это, по-моему, бутылочная горловина вашего кода.

Ответ 3

Я бы предложил написать собственный распределитель для std::unordered_map, который выделяет память точно так, как вы хотите.

Ответ 4

Конструктор принимает параметр "size_type bucket_count" в соответствии с http://en.cppreference.com/w/cpp/container/unordered_map/unordered_map

поэтому самый простой способ сделать то, что говорит ваш пример:

std::unordered_map m{ pow(2,x) };

Это будет более эффективным, так как undefined сколько ведер будет зарезервировано при построении в противном случае, возможно, придется выделять и затем освобождать, когда вы вызываете резерв позже.

Ответ 5

Я думаю, что переосмыслить и зарезервировать обе работы, только если вы заранее знаете, сколько памяти будет иметь ваше отображаемое значение. Если сопоставленное значение является сложным или динамически изменяет размер (например, вектор), вам понадобится ваша собственная реализация. Например, если ваш размер памяти позволяет, вы можете зарезервировать самый большой контейнер, который может когда-либо существовать.