C++ unordered_map插入元素(insert插入元素)詳解

2020-07-16 10:04:31
unordered_map 容器的成員函數 insert() 提供的能力和 map 谷器的這個函數相同。可以通過複製或移動來插入一個元素,可以使用也可以不使用提示符來指明插入的位置。可以插入初始化列表中指定的元素或由兩個疊代器指定範圍內的元素。下面有一些範例,先看第一種情況:
std:: unordered_map<std:: string, size_t> people { {"Jim", 33}, { "Joe", 99}};// Name,age
std::cout <<"people container has " << people.bucket_count()<<" buckets.n"; // 8 buckets
auto pr = people.insert (std::pair<string, size_t> {"Jan", 44});// Move insert
std:: cout << "Element " << (pr.second ? "was" : "was not") << " inserted." << std::endl;
第一條語句用兩個初始元素生成了一個容器,它的格子個數是預設的。第二條語句呼叫 people 的成員函數 bucket_count() 來獲取格子個數;注釋中展示的是在筆者系統上執行程式碼後返回的值,但在你的系統上可能會有些不同。這個 insert() 呼叫是一個有右值參照引數的版本,所以 pair 物件會被移到容器中。這個函數返回了一個 pair 物件,它的成員變數 first 是一個疊代器,它指向插入的新元素;如果元素沒有被插入,它指向的是阻止插入的元素。Pair 的成員變數 second 是一個布林值,如果物件插入成功,它的值為 true。

看下面這些語句:
std::pair<std::string, size_t> Jim {"Jim", 47};
pr = people.insert(Jim);
std::cout << "nElement " << (pr.second ? "was" : "was not") << " inserted. " << std::endl;
std::cout << pr.first->first << " is " « pr.first->second << std::endl;
// 33
因為引數是左值,所以會呼叫有 const 參照引數的 insert() 版本,如果插入成功,它會將元素複製到容器中。這個插入操作不會成功,因為容器中已經有鍵值為 string("Jim") 的元素,所以最後一條語句輸出的年齡為 33。
auto count = people.size();
std::pair<std::string, size_t> person {"Joan", 33};
auto iter = people.insert(pr.first,person);
std::cout << "nElement." << (people.size () > count ? "was" : "was not") << " inserted." << std::endl;
這裡,insert() 的第一個引數是一個疊代器,它是上一個 insert() 呼叫返回的 pair 物件的成員變數 first,用來作為標識元素插入位置的指示符;容器不一定會使用這個指示符。insert 的第二個引數是待插入的元素。這個版本的 insert() 函數不會返回一個 pair 物件,但會返回一個指向插入元素或阻止插入操作的元素的疊代器。這段程式碼中使用容器的成員函數 size() 返回的元素個數來判斷元素是否插入成功。

也可以插入初始化列表中的內容:
people.insert({{"Bill", 21}, {"Ben", 22}});//Inserts the two elements in the list
這個版本的 insert() 不會有返回值,可以插入元素段的 insert() 版本也沒有返回值:
std::unordered_map<std::string, size_t> folks; // Empty container
folks.insert(std::begin(people), std::end(people));// Insert copies of'all people elements
疊代器所定義的來自於 people 容器的元素和 folks 中的元素是同種型別,people 可以是任意型別的容器,只要它的元素型別符合 folks 的要求。

可以呼叫 unordered_map 容器的成員函數 emplace() 或 emplace_hint() 在容器的適當位置生成元素。例如:
auto pr = people. emplace ("Sue", 64);// returns pair<iterator, bool>
auto iter = people.emplace_hint(pr.first, "Sid", 67);// Returns iterator
people.emplace_hint(iter, std::make_pair("Sam", 59));//Uses converting pair<string, size_t>
emplace() 可以用引數在容器的適當位置生成物件,它會返回一個包含疊代器和布林值的 pair 物件,這和 insert() 返回的 pair 物件有同樣的意義。emplace_hint() 的第一個引數是一個作為提示符的疊代器,後面的引數被用來生成元素,它返回的疊代器指向被插入元素或阻止插入的元素。

為了可以用 unordered_map 物件的內容替換這個容器的內容,unordered_map 容器實現了賦值運算子;
folks = people; // Replace folks elements by people elements
顯然,引數所包含的元素的型別必須和當前容器相同。

調整格子個數

在維持當前載入因子的前提下,如果插入元素數超過了格子可以滿足的個數,容器將不得不增加格子的個數。那麼為了將元素重新分配到新的格子中,元素會被再次雜湊。這時,這個容器當前存在的任何疊代器都會失效。在任何時候都可以呼叫成員函數 rehash() 來改變格子的個數:
people.rehash(15); // Make bucket count 15
rehash() 的引數可以比當前格子數多或少。這條語句會將格子的個數變為 15,只要它不導致當前因子超過最大載入因子。容器中的所有元素都會被重新雜湊分配到新的格子中,而且當前所有的疊代器都會失效。如果指定的格子個數導致載入因子超過最大載入因子,那麼格子會自動增加來避免超出最大值。

如果確定會增加格子的個數,可以使用 bucket_count() 返回的值:
people.rehash((5*people.bucket_count())/4); // Increase bucket count by 25%
另一種方式是增加最大載入因子,也就是增加每個格子所包含的元素個數:
people.max_load_factor(1.2*people.max_load_factor()); // 工ncrease max load factor by 20%
為了改變最大載入因子,可以以新的最大載入因子為引數呼叫容器的 max_load_factor(); 如果無引數地呼叫這個函數,它會返回當前的最大載入因子,可以用它來設定新的值。

可以發現,呼叫 unordered_map 的成員函數 load_factor() 時返回的當前載入因子是一個浮點值:
float lf = people.load_factor();
也可以選擇設定格子的個數,使它們在容納給定個數的元素的同時將負載因子維持在最大數之內:
size_t max_element_count {100};
people.reserve(max_element_count);
這裡設定了格子的個數,使它可以容納 100 個元素而不超過最大載入因子的限制。這會導致容器中的內容被重新雜湊,從而使所有的當前疊代器失效。當然,也可以不考慮載入因子和格子個數來生成和使用 unordered_map 容器。容器自己會處理這些事情。

對於現實世界中的應用來說,效能是很重要的,而容器就是影響效能的一個重要因素。當每個格子中的元素不超過一個時,存取速度是最快的,但實際上這是不現實的,因為這需要很多記憶體而且會有很多的空格子。增大最大載入因子可以使每個格子容納更多的元素,從而使格子的總數越少。所以從記憶體使用上來說,這是最有效率的。然而,每個格子中的元素越多,會導致存取元素的速度越慢。這需要根據每個程式的具體情況來選擇。或許最重要的事是要避免反複雜湊容器的內容。如果可以預估出要儲存的元素的個數,就可以設定格子的個數或者設定合適的載入因子,從而減少再次雜湊的可能。