14-STL Container unordered_map

unordered_map

Implementation-Hash Table 存放 key-value pairs 的「無序」映射資料結構 #include <unordered_map> unordered_map containers do NOT allow for duplicate keys

search time O(1) -> Average O(n) -> Worst Case

Capacity

empty() size() max_size()

Iterators

begin() cbegin() end() cend()

Element access

[] or at()

unordered_map<string,int> mymap = {
                { "Mars", 6},
                { "Saturn", 8},
                { "Jupiter", 21 } };

  mymap["Mars"] = 7;
  mymap.at("Saturn") += 10;

Element lookup

find() Searches the container for an element with k as key returns an iterator to it if found, otherwise it returns an iterator to unordered_map::end iterator find ( const key_type& k )

unordered_map<string,int> mymap = {
                { "Mars", 6},
                { "Saturn", 8},
                { "Jupiter", 21 } };

auto itr_got = mymap.find("Saturn");

count("Mars") Searches the container for elements whose key is k and returns the number of elements found. Return value 1 if an element with a key is found, or zero otherwise. (因為map不能有重複的kay)

Modifiers

insert()

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main ()
{
  unordered_map<string,double>
              myrecipe,
              mypantry = {{"milk",2.0},{"flour",1.5}};

  pair<string,double> myshopping ("baking powder",0.3);

  myrecipe.insert (myshopping);                        // copy insertion
  myrecipe.insert (make_pair<string,double>("eggs",6.0)); // move insertion
  myrecipe.insert (mypantry.begin(), mypantry.end());  // range insertion
  myrecipe.insert ( {{"sugar",0.8},{"salt",0.1}} );    // initializer list insertion

  cout << "myrecipe contains:" << endl;
  for (auto& x: myrecipe)
    cout << x.first << ": " << x.second << endl;

  cout << endl;
  return 0;
}

erase()

  mymap.erase ( mymap.begin() );      // erasing by iterator
  mymap.erase ("France");             // erasing by key
  mymap.erase ( mymap.find("China"), mymap.end() ); // erasing by range

clear() swap()

Buckets

bucket_count() Returns the number of buckets. A bucket is a slot in the container's internal hash table to which elements are assigned based on the hash value of their key. The number of buckets influences directly the load factor of the container's hash table3

// unordered_map::insert
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

// unordered_map::bucket_count

int main ()
{
  std::unordered_map<std::string,std::string> mymap = {
            {"house","maison"},
            {"apple","pomme"},
            {"tree","arbre"},
            {"book","livre"},
            {"door","porte"},
            {"grapefruit","pamplemousse"}
  };

  unsigned n = mymap.bucket_count();

  std::cout << "mymap has " << n << " buckets.\n";

  for (unsigned i=0; i<n; ++i) {
    std::cout << "bucket #" << i << " contains: ";
    for (auto it = mymap.begin(i); it!=mymap.end(i); ++it)
      std::cout << "[" << it->first << ":" << it->second << "] ";
    std::cout << "\n";
  }

  return 0;
}

Possible output:

mymap has 7 buckets.
bucket #0 contains: [tree:arbre] 
bucket #1 contains: [book:livre] [apple:pomme] 
bucket #2 contains: [door:porte] 
bucket #3 contains: 
bucket #4 contains: [house:maison] 
bucket #5 contains: 
bucket #6 contains: [grapefruit:pamplemousse]

max_bucket_count() Returns the maximum number of buckets that the unordered_map container can have.

bucket_size Returns the number of elements in bucket n. int bucket_size ( size_type n ) const;

int main ()
{
  unordered_map<string,string> mymap = {
    {"us","United States"},
    {"uk","United Kingdom"},
    {"fr","France"},
    {"de","Germany"}
  };

  unsigned nbuckets = mymap.bucket_count();

  cout << "mymap has " << nbuckets << " buckets:\n";

  for (unsigned i=0; i<nbuckets; ++i) {
    cout << "bucket #" << i << " has " << mymap.bucket_size(i) << " elements.\n";
  }

  return 0;
}

bucket() Returns the bucket number where the element with key k is located. mymap.bucket (x.first)

Hash policy

load_factor The load factor is the ratio between the number of elements in the container (its size) and the number of buckets (bucket_count):

load_factor = size / bucket_count

Returns the current load factor in the unordered_map container. float load_factor() const noexcept;

max_load_factor()

float max_load_factor() const noexcept; returns the current maximum load factor for the unordered_map container.

void max_load_factor ( float z ); sets z as the new maximum load factor for the unordered_map container. 此時bucket_count會進行變動

rehash() Sets the number of buckets in the container to n or more. void rehash( unsigned int n );

If n is greater than the current number of buckets in the container (bucket_count) a rehash is forced. The new bucket count can either be equal or greater than n.

If n is lower than the current number of buckets in the container (bucket_count) the function may have no effect on the bucket count and may not force a rehash.

A rehash is the reconstruction of the hash table: All the elements in the container are rearranged according to their hash value into the new set of buckets

reserve() Sets the number of buckets containing at least n elements. void reserve ( int n );

Observers hash_function() Returns the hash function object used by the unordered_map container.

typedef unordered_map<string,string> stringmap;

int main ()
{
  stringmap mymap;
  stringmap::hasher fn = mymap.hash_function();
  cout << "this: " << fn ("this") << endl;
  cout << "thin: " << fn ("thin") << endl;
  return 0;
}

Pin-Jiun / Programming-Language-CPP