C/C++编程：std :: unordered_map

傷城~ 2022-05-18 03:22 116阅读 0赞

#  #

> 无序映射是关联容器，用于存储由键值和映射值的组合形成的元素，并允许基于其键快速检索各个元素
> 
>  *  在内部，元素并不以任何特别顺序排序，而是组织进桶中。元素被放进哪个桶完全依赖其值的哈希。这允许对单独元素的快速访问，因为哈希一旦确定，就准确指代元素被放入的桶。
>  *  尽管unordered\_map容器通过其*键*访问单个元素的速度要比map容器快，但是通过它们的子集进行范围迭代通常效率较低
>  *  `std::unordered_set` 满足[容器 (Container) ][_Container_]、[知分配器容器 (AllocatorAwareContainer) ][_AllocatorAwareContainer_]、[无序关联容器 (UnorderedAssociativeContainer) ][_UnorderedAssociativeContainer_]的要求。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70][]

# 成员函数 #

## std :: [unordered\_map][unordered_map] :: unordered\_map ##

<table> 
 <tbody> 
  <tr> 
   <th>empty (1)</th> 
   <td> <pre><code>explicit unordered_map ( size_type n = /* see below */,
                         const hasher&amp; hf = hasher(),
                         const key_equal&amp; eql = key_equal(),
                         const allocator_type&amp; alloc = allocator_type() );
explicit unordered_map ( const allocator_type&amp; alloc );
</code></pre> </td> 
  </tr> 
  <tr> 
   <th>range (2)</th> 
   <td> <pre><code>template &lt;class InputIterator&gt;
  unordered_map ( InputIterator first, InputIterator last,
                  size_type n = /* see below */,
                  const hasher&amp; hf = hasher(),
                  const key_equal&amp; eql = key_equal(),
                  const allocator_type&amp; alloc = allocator_type() );
</code></pre> </td> 
  </tr> 
  <tr> 
   <th>copy (3)</th> 
   <td> <pre><code>unordered_map ( const unordered_map&amp; ump );
unordered_map ( const unordered_map&amp; ump, const allocator_type&amp; alloc );
</code></pre> </td> 
  </tr> 
  <tr> 
   <th>move (4)</th> 
   <td> <pre><code>unordered_map ( unordered_map&amp;&amp; ump );
unordered_map ( unordered_map&amp;&amp; ump, const allocator_type&amp; alloc );
</code></pre> </td> 
  </tr> 
  <tr> 
   <th>initializer list (5)</th> 
   <td> <pre><code>unordered_map ( initializer_list&lt;value_type&gt; il,
                size_type n = /* see below */,
                const hasher&amp; hf = hasher(),
                const key_equal&amp; eql = key_equal(),
                const allocator_type&amp; alloc = allocator_type() );</code></pre> </td> 
  </tr> 
 </tbody> 
</table>

> 构造一个[unordered\_map][unordered_map 1]容器对象，根据使用的构造函数版本初始化其内容：  
> 
> 
> （1）空容器构造函数（默认构造函数）
> 
> 构造一个空的[unordered\_map][unordered_map 1]对象，该对象不包含任何元素且[大小][Link 1]为零。  
> 它可以使用特定的*hasher*，*key\_equal*和*allocator*对象以及最少数量的哈希桶来构造容器。
> 
> （2）范围构造器
> 
> 构造一个[unordered\_map][unordered_map 1]对象，该对象包含\[first，last）范围内每个元素的副本。
> 
> （3）复制构造函数（并用分配器复制）
> 
> 该对象被初始化为具有与*ump* [unordered\_map][unordered_map 1]对象相同的内容和属性。
> 
> （4）移动构造函数（并使用分配器移动）
> 
> 对象获取右值*ump*的内容。
> 
> （5）初始化列表
> 
> 用列表的内容初始化容器。

// constructing unordered_maps
    #include <iostream>
    #include <string>
    #include <unordered_map>
    
    typedef std::unordered_map<std::string,std::string> stringmap;
    
    stringmap merge (stringmap a,stringmap b) {
      stringmap temp(a); temp.insert(b.begin(),b.end()); return temp;
    }
    
    int main ()
    {
      stringmap first;                              // empty
      stringmap second ( {
       {"apple","red"},{"lemon","yellow"}} );       // init list
      stringmap third ( {
       {"orange","orange"},{"strawberry","red"}} );  // init list
      stringmap fourth (second);                    // copy
      stringmap fifth (merge(third,fourth));        // move
      stringmap sixth (fifth.begin(),fifth.end());  // range
    
      std::cout << "sixth contains:";
      for (auto& x: sixth) std::cout << " " << x.first << ":" << x.second;
      std::cout << std::endl;
    
      return 0;
    }

## std :: [unordered\_map][unordered_map] :: operator = ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1][]

// assignment operator with unordered_map
    #include <iostream>
    #include <string>
    #include <unordered_map>
    
    typedef std::unordered_map<std::string,std::string> stringmap;
    
    stringmap merge (stringmap a,stringmap b) {
      stringmap temp(a); temp.insert(b.begin(),b.end()); return temp;
    }
    
    int main ()
    {
      stringmap first, second, third;
      first = {
       {"AAPL","Apple"},{"MSFT","Microsoft"}};  // init list
      second = {
       {"GOOG","Google"},{"ORCL","Oracle"}};   // init list
      third = merge(first,second);                      // move
      first = third;                                    // copy
    
      std::cout << "first contains:";
      for (auto& elem: first) std::cout << " " << elem.first << ":" << elem.second;
      std::cout << std::endl;
    
      return 0;
    }

#include <unordered_map>
    #include <iostream>
     
    void display_sizes(const std::unordered_map<int, int> &nums1,
                       const std::unordered_map<int, int> &nums2,
                       const std::unordered_map<int, int> &nums3)
    {
        std::cout << "nums1: " << nums1.size() 
                  << " nums2: " << nums2.size()
                  << " nums3: " << nums3.size() << '\n';
    }
     
    int main()
    {
        std::unordered_map<int, int> nums1 {
       {3, 1}, {4, 1}, {5, 9}, 
                                            {6, 1}, {7, 1}, {8, 9}};
        std::unordered_map<int, int> nums2; 
        std::unordered_map<int, int> nums3;
     
        std::cout << "Initially:\n";
        display_sizes(nums1, nums2, nums3);
     
        // 复制赋值从 nums1 复制数据到 nums2
        nums2 = nums1;
     
        std::cout << "After assigment:\n"; 
        display_sizes(nums1, nums2, nums3);
     
        // 移动赋值从 nums1 移动数据到 nums3,
        // 一同修改 nums1 和 nums3
        nums3 = std::move(nums1);
     
        std::cout << "After move assigment:\n"; 
        display_sizes(nums1, nums2, nums3);
    }

![2021030913014620.png][]

## std::unordered\_map::empty ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 2][]

#include <unordered_map>
    #include <iostream>
    #include <utility>
     
    int main()
    {
        std::unordered_map<int, int> numbers;
        std::cout << "Initially, numbers.empty(): " << numbers.empty() << '\n';
     
        numbers.emplace(42, 13);
        numbers.insert(std::make_pair(13317, 123));  
        std::cout << "After adding elements, numbers.empty(): " << numbers.empty() << '\n';
    }

## std::unordered\_map::size ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 3][]

#include <unordered_map>
    #include <iostream>
     
    int main()
    { 
        std::unordered_map<int,char> nums {
       {1, 'a'}, {3, 'b'}, {5, 'c'}, {7, 'd'}};
     
        std::cout << "nums contains " << nums.size() << " elements.\n";
    }

![20210309132645275.png][]

## std::unordered\_map::max\_size ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 4][]

#include <iostream>
    #include <unordered_map>
     
    int main()
    {
        std::unordered_map<char,char> s;
        std::cout << "Maximum size of a 'unordered_map' is " << s.max_size() << "\n";
    }

![20210309132734892.png][]

## std::unordered\_map::clear ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 5][]

#include <algorithm>
    #include <iostream>
    #include <unordered_map>
     
    int main()
    {
        std::unordered_map<int, char> container{
       {1, 'x'}, {2, 'y'}, {3, 'z'}};
     
        auto print = [](std::pair<const int, char>& n) { 
            std::cout << " " << n.first << '(' << n.second << ')'; 
        };
     
        std::cout << "Before clear:";
        std::for_each(container.begin(), container.end(), print);
        std::cout << "\nSize=" << container.size() << '\n';
     
        std::cout << "Clear\n";
        container.clear();
     
        std::cout << "After clear:";
        std::for_each(container.begin(), container.end(), print);
        std::cout << "\nSize=" << container.size() << '\n';
    }

![20210309132829329.png][]

## std::unordered\_map::insert ##

若容器尚未含有带等价关键的元素，则插入元素到容器中。

#include <iostream>
    #include <string>
    #include <unordered_map>
    
    int main ()
    {
      std::unordered_map<std::string,double>
                  myrecipe,
                  mypantry = {
       {"milk",2.0},{"flour",1.5}};
    
      std::pair<std::string,double> myshopping ("baking powder",0.3);
    
      myrecipe.insert (myshopping);                        // copy insertion
      myrecipe.insert (std::make_pair<std::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
    
      std::cout << "myrecipe contains:" << std::endl;
      for (auto& x: myrecipe)
        std::cout << x.first << ": " << x.second << std::endl;
    
      std::cout << std::endl;
      return 0;
    }

#include <string>
    #include <iostream>
    #include <unordered_map>
     
    int main ()
    {
        std::unordered_map<int, std::string> dict = {
       {1, "one"}, {2, "two"}};
        dict.insert({3, "three"});
        dict.insert(std::make_pair(4, "four"));
        dict.insert({
       {4, "another four"}, {5, "five"}});
     
        bool ok = dict.insert({1, "another one"}).second;
        std::cout << "inserting 1 -> \"another one\" " 
                  << (ok ? "succeeded" : "failed") << '\n';
     
        std::cout << "contents:\n";
        for(auto& p: dict)
            std::cout << " " << p.first << " => " << p.second << '\n';
    }

![20210309133403324.png][]

##  ##

## std::unordered\_map::emplace ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 6][]

#include <iostream>
    #include <utility>
    #include <string>
    #include <unordered_map>
     
    int main()
    {
        std::unordered_map<std::string, std::string> m;
     
        // 使用 pair 的移动构造函数
        m.emplace(std::make_pair(std::string("a"), std::string("a")));
     
        // 使用 pair 的转换移动构造函数
        m.emplace(std::make_pair("b", "abcd"));
     
        // 使用 pair 的模板构造函数
        m.emplace("d", "ddd");
     
        // 使用 pair 的逐片构造函数
        m.emplace(std::piecewise_construct,
                  std::forward_as_tuple("c"),
                  std::forward_as_tuple(10, 'c'));
        // C++17 起，能使用 m.try_emplace("c", 10, 'c');
     
        for (const auto &p : m) {
            std::cout << p.first << " => " << p.second << '\n';
        }
    }

![20210309161941391.png][]

[_Container_]: https://zh.cppreference.com/w/cpp/named_req/Container
[_AllocatorAwareContainer_]: https://zh.cppreference.com/w/cpp/named_req/AllocatorAwareContainer
[_UnorderedAssociativeContainer_]: https://zh.cppreference.com/w/cpp/named_req/UnorderedAssociativeContainer
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: /images/20220518/8d74ad5dd4e34fa7a52dd18fcd1b3d81.png
[unordered_map]: http://www.cplusplus.com/reference/unordered_map/unordered_map/
[unordered_map 1]: http://www.cplusplus.com/unordered_map
[Link 1]: http://www.cplusplus.com/unordered_map::size
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]: /images/20220518/b48aa98cc84d468cb78f9a1bfaf01c77.png
[2021030913014620.png]: /images/20220518/2f2d32befa064188ab7680f3e7d3b39e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 2]: /images/20220518/801b005a07354dfa9a6acd62a9b16405.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 3]: /images/20220518/44942fe7c127423bbda1d79061473f8c.png
[20210309132645275.png]: /images/20220518/cd75c451d8ce4664a2b6cb07e6bbb866.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 4]: /images/20220518/3196d65564264588aeac850791017465.png
[20210309132734892.png]: /images/20220518/4f6c2685e5f24a47849bb4e0a74425db.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 5]: /images/20220518/ce929efbb7e541bfbd617556bd39c949.png
[20210309132829329.png]: /images/20220518/7a011bfdef9f41b7903755951ae13c94.png
[20210309133403324.png]: /images/20220518/ec296fcd7fd84a668562e4ce2b90faa5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 6]: /images/20220518/5768f34fd7cb41228718152f2b953202.png
[20210309161941391.png]: /images/20220518/a3e29e1e718045ad9df71edfc8192bbf.png