C++-map：unordered_map【内部实现了哈希表，因此其查找速度非常的快】【内部元素是无序的；遍历顺序与创建该容器时元素输入的顺序不一定相同】

悠悠 2023-09-25 13:38 7阅读 0赞

## 一、简介 ##

无序映射（Unordered maps）是用于存储*键值*和*映射值*组合成的元素的关联容器，并允许基于其键快速检索各个元素。在`unordered_map`中，键值通常用于唯一地标识元素，而映射值是具有与该键关联的内容的对象。键的类型和映射的值可能会有所不同。

C++ 11标准中加入了unordered系列的容器。unordered\_map记录元素的hash值，根据hash值判断元素是否相同。

*  map相当于java中的TreeMap；
 *  unordered\_map相当于HashMap；

无论从查找、插入上来说，unordered\_map的效率都优于hash\_map，更优于map；而空间复杂度方面，hash\_map最低，unordered\_map次之，map最大。

<table> 
 <tbody> 
  <tr> 
   <th></th> 
   <th>效率/空间占用 (大)</th> 
   <th>效率/空间占用 (中)</th> 
   <th>效率/空间占用 (小)</th> 
  </tr> 
  <tr> 
   <td>Find &amp; Insert</td> 
   <td>unordered_map</td> 
   <td>hash_map</td> 
   <td>map</td> 
  </tr> 
  <tr> 
   <td>Space</td> 
   <td>map</td> 
   <td>unordered_map</td> 
   <td>hash_map</td> 
  </tr> 
 </tbody> 
</table>

## 二、头文件 ##

在使用`unordered_map`时，需要引入头文件：

#include < unordered_map >

## 三、**map、unordered\_map、hash\_map** ##

### **1、unordered\_map与map的对比** ###

存储时是根据key的hash值判断元素是否相同，即unordered\_map内部元素是无序的，而map中的元素是按照二叉搜索树存储（用红黑树实现），进行中序遍历会得到有序遍历。所以使用时map的key需要定义operator<。而unordered\_map需要定义hash\_value函数并且重载operator==。但是很多系统内置的数据类型都自带这些。

**map**

1.  优点：
    
     *  有序性，这是`map`结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作；
     *  [红黑树][Link 1]，内部实现一个红黑树使得`map`的很多操作在O(lgn)的[时间复杂度][Link 2]下就可以实现，因此效率非常的高。
2.  缺点：空间占用率高，因为`map`内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间
3.  应用场景：对于那些有顺序要求的问题，用`map`会更高效一些

**unordered\_map**

1.  优点：因为内部实现了哈希表，因此其查找速度非常的快
2.  缺点：哈希表的建立比较耗费时间
3.  应用场景：对于查找问题，`unordered_map`会更加高效一些，因此遇到查找问题，常会考虑一下用`unordered_map`

**总结**

1.  内存占有率的问题就转化成红黑树 VS Hash表，还是`unordered_map`占用的内存要高；
2.  但是`unordered_map`执行效率要比`map`高很多；
3.  对于`unordered_map`或`unordered_set`容器，其遍历顺序与创建该容器时输入的顺序不一定相同，因为遍历是按照哈希表从前往后依次遍历的。

**NOTE：有如下结构体 library::book，你想用它作为 unordered\_map 的 key 值，你需要做两件事：重载 == 和 定义 hash\_value 函数。前者定义比较 key 值是否唯一，后者提供一个hash值，用于存储。**

namespace library
    {
        struct book
        {
            int id;
            std::string author;
            std::string title;
    
            // ....
        };
    
        bool operator==(book const& a, book const& b)
        {
            return a.id == b.id;
        }
    }
    // 定义函数
    namespace library
    {
        std::size_t hash_value(book const& b)
        {
            boost::hash<int> hasher;
            return hasher(b.id);
        }
    }
    // ----------------------------用法
    library::book knife(3458, "Zane Grey", "The Hash Knife Outfit");
    library::book dandelion(1354, "Paul J. Shanley",
        "Hash & Dandelion Greens");
    
    boost::hash<library::book> book_hasher;
    std::size_t knife_hash_value = book_hasher(knife);
    
    // If std::unordered_set is available:
    std::unordered_set<library::book, boost::hash<library::book> > books;
    books.insert(knife);
    books.insert(library::book(2443, "Lindgren, Torgny", "Hash"));
    books.insert(library::book(1953, "Snyder, Bernadette M.",
        "Heavenly Hash: A Tasty Mix of a Mother's Meditations"));
    
    assert(books.find(knife) != books.end());
    assert(books.find(dandelion) == books.end());

以上代码出自：[Extending boost::hash for a custom data type][Extending boost_hash for a custom data type]

### **2、unordered\_map与hash\_map对比：** ###

unordered\_map原来属于boost分支和std::tr1中，而hash\_map属于非标准容器。  
　　unordered\_map感觉速度和hash\_map差不多，但是支持string做key，也可以使用复杂的对象作为key。  
　　unordered\_map编译时gxx需要添加编译选项：--std=c++11

**unordered\_map模板：**

template < class Key,                                    // unordered_map::key_type
               class T,                                      // unordered_map::mapped_type
               class Hash = hash<Key>,                       // unordered_map::hasher
               class Pred = equal_to<Key>,                   // unordered_map::key_equal
               class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
               > class unordered_map;

## **四、迭代器：** ##

unordered\_map的迭代器是一个指针，指向这个元素，通过迭代器来取得它的值。

unordered_map<Key,T>::iterator it;
    (*it).first;             // the key value (of type Key)
    (*it).second;            // the mapped value (of type T)
    (*it);                   // the "element value" (of type pair<const Key,T>)

它的键值分别是迭代器的first和second属性。

it->first;               // same as (*it).first   (the key value)
    it->second;              // same as (*it).second  (the mapped value)

## **五、成员函数：** ##

=================迭代器=========================  
begin 　　返回指向容器起始位置的迭代器（iterator）  
end 　　 返回指向容器末尾位置的迭代器  
cbegin　 返回指向容器起始位置的常迭代器（const\_iterator）  
cend 　　 返回指向容器末尾位置的常迭代器  
=================Capacity================  
size 　　 返回有效元素个数  
max\_size 返回 unordered\_map 支持的最大元素个数  
empty 判断是否为空  
=================元素访问=================  
operator\[\] 　　 访问元素  
at 　　 　　　　访问元素  
=================元素修改=================  
insert 　　插入元素  
erase　　 删除元素  
swap 　　 交换内容  
clear　　 清空内容  
emplace 　构造及插入一个元素  
emplace\_hint 按提示构造及插入一个元素  
================操作=========================  
find 　　　　　　通过给定主键查找元素,没找到：返回unordered\_map::end  
count 　　　　　返回匹配给定主键的元素的个数  
equal\_range 　　返回值匹配给定搜索值的元素组成的范围  
================Buckets======================  
bucket\_count 　　　返回槽（Bucket）数  
max\_bucket\_count 返回最大槽数  
bucket\_size 　　　 返回槽大小  
bucket 　　　　　　返回元素所在槽的序号  
load\_factor　　　　 返回载入因子，即一个元素槽（Bucket）的最大元素数  
max\_load\_factor 　 返回或设置最大载入因子  
rehash　　　　　　 设置槽数  
reserve 　　　　　 请求改变容器容量

**插入元素示例：**

// unordered_map::insert
    #include <iostream>
    #include <string>
    #include <unordered_map>
    using namespace std;
    
    void display(unordered_map<string,double> myrecipe,string str)
    {
        cout << str << endl;
        for (auto& x: myrecipe)
            cout << x.first << ": " << x.second << endl;
        cout << endl;
    }
    
    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);                        // 复制插入
        myrecipe.insert (make_pair<string,double>("eggs",6.0)); // 移动插入
        myrecipe.insert (mypantry.begin(), mypantry.end());  // 范围插入
        myrecipe.insert ({
       {"sugar",0.8},{"salt",0.1}});    // 初始化数组插入(可以用二维一次插入多个元素，也可以用一维插入一个元素)
        myrecipe["coffee"] = 10.0;  //数组形式插入
    
        display(myrecipe,"myrecipe contains:");
    
        /****************查找*****************/
        unordered_map<string,double>::const_iterator got = myrecipe.find ("coffee");
    
        if ( got == myrecipe.end() )
            cout << "not found";
        else
            cout << "found "<<got->first << " is " << got->second<<"\n\n";
        /****************修改*****************/
        myrecipe.at("coffee") = 9.0;
        myrecipe["milk"] = 3.0;
        display(myrecipe,"After modify myrecipe contains:");
    
    
        /****************擦除*****************/
        myrecipe.erase(myrecipe.begin());  //通过位置
        myrecipe.erase("milk");    //通过key
        display(myrecipe,"After erase myrecipe contains:");
    
        /****************交换*****************/
        myrecipe.swap(mypantry);
        display(myrecipe,"After swap with mypantry, myrecipe contains:");
    
        /****************清空*****************/
        myrecipe.clear();
        display(myrecipe,"After clear, myrecipe contains:");
        return 0;
    }
    /*
    myrecipe contains:
    salt: 0.1
    milk: 2
    flour: 1.5
    coffee: 10
    eggs: 6
    sugar: 0.8
    baking powder: 0.3
    
    found coffee is 10
    
    After modify myrecipe contains:
    salt: 0.1
    milk: 3
    flour: 1.5
    coffee: 9
    eggs: 6
    sugar: 0.8
    baking powder: 0.3
    
    After erase myrecipe contains:
    flour: 1.5
    coffee: 9
    eggs: 6
    sugar: 0.8
    baking powder: 0.3
    
    After swap with mypantry, myrecipe contains:
    flour: 1.5
    milk: 2
    
    After clear, myrecipe contains:
    */

**遍历示例：**

// unordered_map::bucket_count
    #include <iostream>
    #include <string>
    #include <unordered_map>
    using namespace std;
    
    int main ()
    {
        unordered_map<string,string> mymap =
        {
            {"house","maison"},
            {"apple","pomme"},
            {"tree","arbre"},
            {"book","livre"},
            {"door","porte"},
            {"grapefruit","pamplemousse"}
        };
        /************begin和end迭代器***************/
        cout << "mymap contains:";
        for ( auto it = mymap.begin(); it != mymap.end(); ++it )
            cout << " " << it->first << ":" << it->second;
        cout << endl;
        /************bucket操作***************/
         unsigned n = mymap.bucket_count();
    
        cout << "mymap has " << n << " buckets.\n";
    
        for (unsigned i=0; i<n; ++i)
        {
            cout << "bucket #" << i << "'s size:"<<mymap.bucket_size(i)<<" contains: ";
            for (auto it = mymap.begin(i); it!=mymap.end(i); ++it)
                cout << "[" << it->first << ":" << it->second << "] ";
            cout << "\n";
        }
    
        cout <<"\nkey:'apple' is in bucket #" << mymap.bucket("apple") <<endl;
        cout <<"\nkey:'computer' is in bucket #" << mymap.bucket("computer") <<endl;
    
        return 0;
    }
    /*
    mymap contains: door:porte grapefruit:pamplemousse tree:arbre apple:pomme book:livre house:maison
    mymap has 7 buckets.
    bucket #0's size:2 contains: [book:livre] [house:maison]
    bucket #1's size:0 contains:
    bucket #2's size:0 contains:
    bucket #3's size:2 contains: [grapefruit:pamplemousse] [tree:arbre]
    bucket #4's size:0 contains:
    bucket #5's size:1 contains: [apple:pomme]
    bucket #6's size:1 contains: [door:porte]
    
    key:'apple' is in bucket #5
    
    key:'computer' is in bucket #6
    */

[C++STL : unordered\_map详解 - 知乎][C_STL _ unordered_map_ -]

[unordered\_map 简介\_菠萝开方的博客-CSDN博客\_unordered\_map][unordered_map _-CSDN_unordered_map]

[unordered\_map使用详解\_Blanche117的博客-CSDN博客\_unordered\_map][unordered_map_Blanche117_-CSDN_unordered_map]

[Link 1]: https://so.csdn.net/so/search?q=%E7%BA%A2%E9%BB%91%E6%A0%91&spm=1001.2101.3001.7020
[Link 2]: https://so.csdn.net/so/search?q=%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6&spm=1001.2101.3001.7020
[Extending boost_hash for a custom data type]: https://link.zhihu.com/?target=https%3A//www.boost.org/doc/libs/1_38_0/doc/html/hash/custom.html
[C_STL _ unordered_map_ -]: https://zhuanlan.zhihu.com/p/296360525
[unordered_map _-CSDN_unordered_map]: https://blog.csdn.net/qq_40838478/article/details/114664223
[unordered_map_Blanche117_-CSDN_unordered_map]: https://blog.csdn.net/weixin_45745854/article/details/122785542