Предварительно выделяющие ведра в C++ unordered_map

Question

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

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

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

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

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

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

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

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

Answer 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())).

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

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

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

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