我正在使用來自gnu ++ 0x的unordered_map來存儲大量數據。我想爲大量元素預先分配空間，因爲我可以限制使用的總空間。在C++中預分配桶unordered_map
我想什麼能夠做的就是調用：
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）個增長，所以算法的運行時間會產生額外的二次項。
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()))。
我會建議編寫std::unordered_map的自己的分配器，它按照你想要的方式準確地分配內存。
我認爲這對無序地圖有預先分配的內存很重要。 STL預計爲O（n）攤銷插入時間。在我看來，除非你知道這是你的代碼的瓶頸，否則就省去編寫自己的分配器的麻煩。
的STL保證O（n）的攤銷插入時間，但本實施的常用方法是通過一個常數因子，以增加桶的數量，然後重新散列每個現有元件。如果您在地圖中存儲n個元素，則會發生O（log n）次。當n大於2時，這會對插入的次數增加一個額外的因子。我試圖削減這個因素。 – JAD 2011-05-11 19:01:17
「這增加了大量的額外因素」不，這增加了2.一個額外的因素你明白怎麼操作平攤工作？這個答案的唯一真正原因是錯誤的，因爲它不能「保證」O（n）攤銷插入時間，它只提供預期的O（n）攤銷插入時間，隨機插入元素的概率很高。如果您知道存儲桶將調整到的確切大小以及將要使用的哈希函數，則仍然可以欺騙哈希表並針對每個插入強制執行N次碰撞。 – codetaku 2015-08-14 15:58:04
我覺得翻版和儲備都只有工作，如果你事先知道有多少內存映射你的價值會抓住。如果映射的值很複雜或者在大小上動態變化（例如向量），則需要您自己的實現。例如，如果你的內存大小允許，你可以保留可能存在的最大容器。
所做的某些點沒有意義，或者你沒有使自己的理解。例如「如果映射的值動態改變大小（例如矢量）」。不管你在向量中有多少元素（或者任何容器或類），sizeof（std :: vector
構造函數參數「SIZE_TYPE BUCKET_COUNT」根據http://en.cppreference.com/w/cpp/container/unordered_map/unordered_map
所以最簡單的方法做你的示例代碼說的話是：
std::unordered_map m{ pow(2,x) };
這將是更有效，因爲它是不確定的有多少否則桶將在施工中預留，之後您可能需要分配然後釋放資源。
您正在使用的暗示，彷彿是在： 迭代器的std ::設置::插入（迭代器提示，常量VALUE_TYPE和值）; http://en.cppreference.com/w/cpp/container/set/insert，看起來言語不當。 – 2017-07-19 03:48:27