C++ unordered_map獲取(存取)元素詳解

2020-07-16 10:04:29
對於 unordered_map,可以在下標運算子中使用鍵來獲取它所對應物件的參照。例如:
people["Jim"] = 22; //Set Jim's age to 22;
people["May"] = people["Jim"]; //Set May's age to Jim's
++people ["Joe"] ; //Increment Joe's age
people ["Kit"] = people ["Joe"]; // Set Kit's age to Joe's
這和 map 容器的操作是一樣的。在下標中使用不存在的鍵時,會以這個鍵為新鍵生成一個新的元素,新元素中物件的值是預設的。如果容器中不存在”Kit”,上面最後一條語句會生成一個以“kit”為鍵、年齡值為 0 的元素;最後"Joe”所關聯的物件會被複製到"Kit"。

成員函數 at() 會返回引數所關聯物件的參照,如果鍵不存在,會拋出一個 out_of_range 異常。所以當我們不想生成有預設物件的元素時,應該選擇使用 at() 而不是下標運算子。你可能已經發現成員函數 find() 和 equal_range() 的工作方式和之前描述的 map 是一樣的。

unordered_map 的疊代器是可以使用的,因此可以用基於範圍的 for 迴圈來存取它的元 素,例如:
for(const auto& person : people)
    std::cout << person.first << " is "<< person.second <<std::endl;
這樣就可以列出 people 容器中的全部元素。

存取格子

可以存取 unordered_map 的個別格子及其包含的元素。可以用這個容器的成員函數 begin() 和 end() 的過載版來做到這一點,它們可以返回容器元素的疊代器。格子的索引從 0 開始,可以通過將索引值傳給容器的成員函數 begin() 來獲取給定位置的格子中第一個元素的疊代器。例如:
auto iter = people.begin(1); // Returns an iterator for the 2nd bucket
將索引值傳給容器的成員函數 cbegin() 會返回一個 const 疊代器,它指向位於索引位置的格子中的第一個元素。這個容器的成員函數 end() 和 cend() 也有這樣的版本,它們接受一個索引值,分別返回一個疊代器和一個 const 疊代器,它們指向位於指定位置的格子中的最後一個元素的下一個位置。可以輸出特定格子中的元素,也就是說,需要使用迴圈:
size_t index{1};
std::cout <<"The elements in bucket["<< index << "] are:n";
for(auto iter = people.begin(index); iter != people.end(index); ++iter)
    std::cout <<iter->first << " is " <<iter->second <<std::endl;
我們已經看到 unordered_map 的成員函數 bucket_count() 返回的格子個數。bucket_size() 可以返回引數指定的格子中的元素個數。bucket() 返回的是格子的索引值,包含和傳入的引數鍵匹配的元素。可以用不同的方式來組合使用它們。例如:
string key {"May"};
if(people.find(key) != std::end(people))
    std::cout << "The number of elements in the bucket containing " << key << " is "<< people.bucket_size(people.bucket(key)) << std:: endl;
bucket_size() 的引數是 bucket() 返回的索引值。當鍵在容器中時,這段程式碼才會執行輸語句。輸出記錄了包含鍵的格子中的元素個數。下面有一個範例,可以讓我們深入了解在新增元素時,我們系統中的 unorderect_map 是如何做的:
// Analyzing how and when the number of buckets in an unordered_map container increases
#include <iostream>                              // For standard streams
#include <iomanip>                               // For stream manipulators
#include <string>                                // For string class
#include <unordered_map>                         // For unordered_map container
#include <vector>                                // For vector container
#include <algorithm>                             // For max_element() algorithm

using std::string;
using std::unordered_map;

// Outputs number of elements in each bucket
void list_bucket_counts(const std::vector<size_t>& counts)
{
    for(size_t i {}; i < counts.size(); ++i)
    {
        std::cout << "bucket[" << std::setw(2) << i << "] = " << counts[i] << "  ";
        if((i + 1) % 6 == 0) std::cout << 'n';
    }
    std::cout << std::endl;
}

int main()
{
    unordered_map<string, size_t> people;
    float mlf {people.max_load_factor()};                         // Current maximum load factor
    size_t n_buckets {people.bucket_count()};                     // Number of buckets in container

    std::vector<size_t> bucket_counts (people.bucket_count());    // Records number of elements per bucket
    string name {"Name"};                                         // Key - with value appended
    size_t value {1};                                             // Element value
    size_t max_count {8192};                                      // Maximum number of elements to insert
    auto lf = people.load_factor();                               // Current load factor
    bool rehash {false};                                          // Records when rehash occurs

    while(mlf <= 1.5f)                                            // Loop until max load factor is 1.5
    {
        std::cout << "nn***************New Container***************"
              << "nNumber of buckets: " << n_buckets << "  Maximum load factor: " << mlf << std::endl;
        // Insert max elements in container
        for(size_t n_elements {}; n_elements < max_count; ++n_elements)
        {
            lf = people.load_factor();                               // Record load factor
            people.emplace("name" + std::to_string(++value), value);
            auto new_count = people.bucket_count();                  // Current bucket count
            if(new_count > n_buckets)                                // If bucket count increases...
            {                                                        // Output info
                std::cout << "nBucket count increased to " << new_count<< ". Load factor was " << lf << " and is now " << people.load_factor()<< "nMaximum elements in a bucket was "<< *std::max_element(std::begin(bucket_counts), std::end(bucket_counts)) << std::endl;
                if(n_buckets <= 64)
                {
                    std::cout << "Bucket counts before increase were: " << std::endl;
                    list_bucket_counts(bucket_counts);
                }
                n_buckets = new_count;                                  // Update bucket count
                bucket_counts = std::vector < size_t > (n_buckets);     // New vector for counts
                rehash = true;                                          // Record rehash occurred
            }

            // Record current bucket counts
            for(size_t i {}; i < n_buckets; ++i)
                bucket_counts[i] = people.bucket_size(i);

            if(rehash)                                                // If the container was rehashed...
            {                                                         // ...output info
                rehash = false;                                         // Reset rehash indicator
                std::cout << "nRehashed container. Bucket count is " << n_buckets << ". Element count is " << people.size()<< "nMaximum element count in a bucket is now "<< *std::max_element(std::begin(bucket_counts), std::end(bucket_counts)) << std::endl;
                if(n_buckets <= 64)                                     // If no more than 64 buckets...
                {
                    std::cout << "nBucket counts after rehash are:n";
                    list_bucket_counts(bucket_counts);
                }
            }
        }
        std::cout << "Final state for this container is:n"<< "Bucket count: " << people.bucket_count() << "  Element count: " << people.size()<< "  Maximum element count in a bucket: "<< *std::max_element(std::begin(bucket_counts), std::end(bucket_counts)) << std::endl;
        value = 1;                                                  // Reset key suffix
        people = unordered_map<string, size_t>();                   // New empty container
        n_buckets = people.bucket_count();
        bucket_counts = std::vector < size_t >(n_buckets);          // New vector for bucket counts
        mlf += 0.25f;                                               // Increase max load factor...
        people.max_load_factor(mlf);                                // ...and set for container
    }
}
上述程式會記錄元素個數增加時的載入因子和格子個數。通過這種方式,可以了解容器在什麼條件下是以何種方式增加格子的。因為這段程式碼的執行會花費相當長的時間,所以我們需要耐心等待一下。如果覺得花費的時間太長了,可以減小變數 max 的值。

這個範例以一個空的 unordered_map 容器開始,然後插入max 所指定的有限個新元素。然後通過在引數“name”的後面追加 value 遞增後 to_string() 返回的字串來構造唯一的鍵。 to_string() 函數定義在 string 標頭檔案中,可以將任意數值型別轉換為 string 物件。

每個格子中的元素個數記錄在一個 vector 容器中。外層的 while 迴圈會一直進行下去,只要最大載入因子小於等於 1.5。巢狀的 for 迴圈會向 unordered_map 容器中插入 max_count 個元素。無論什麼時候格子個數改變,都會呼叫輔助函數 list_bucket_counts() 來輸出每個格子中的元素個數。

為了避免大量輸出導致無法管理,只輸出 64 個或更少的格子。當插入 max_count 個元素後,會使用更大的載入因子來生成 unordered_map,對這個新容器繼續重複內會回圈。這樣就展示了最大載入因子如何影響格子個數的增加程度,從而導致元素被重新雜湊。

對於執行結果,由於執行過程會佔用太多的空間,我們可以簡單概括下發生了什麼。預設的格子數是 8。在新增了 8 個元素後,格子數從 8 增加到了 64,這是一個非常大的變化。當格子的最大元素個數是 2,但只有一個格子包含兩個元素時;元素的總個數是 9。輸出顯示當載入因子接近 1.0 時,會觸發格子個數的增加,格子個數下一次會乘以因子 8,從 64 到 512 (因執行系統而異)。格子個數的因子會緩慢增加到 2,所以格子個數的序列是 8、64、512、1024、2048、4096、8192。隨著格子個數的增加,觀察有多少空格子是很有意思的。

在我自己的系統上,所有格子的最大元素數目是 8,一點兒也不令人驚訝的是它也是最大的載入因子。在載入因子最大為 1.5 時,從一個格子中得到了 7 個元素。每次格子個數的增加都會導致容器中的所有元素被重新雜湊分配到新的位置。可以很容易地對程式做一下調整,使它能夠輸出在格子增加前後的元素,這樣就能夠知道元素是如何被移動的。這顯然會涉及相當大的開銷,所以在儲存的元素增加時,開始得到正確的格子數就變得更重要。

從系統上的輸出可以了解到容器是如何將原始雜湊值對映到格子的索引上的。格子數總是為 2 的冪。這樣就允許格子的索引是來自於原始雜湊值的固定位序列:8 個格子需要 3 位,64 個需要 6 位,512 個需要 9 位,以此類推。這就使獲取格子的索引變得簡單和快速。也就解釋了為什麼在格子數增加後,需要重新對元素進行雜湊。從給定的雜湊值中取 6 位要比取 3 位更能表示不同的索引值,所以一個給定的原始雜湊值可能會被對映到不同的格子中。