C++中的map问题+unordered_map问题

不念不忘少年蓝@ 2022-12-07 15:27 187阅读 0赞

**目录**

4.map问题+unordered\_map问题

4.1 map

4.1.1 map的使用

4.1.2 构造map

4.1.3 往map中插入元素

4.1.4 在map中查找元素

4.1.5 删除与清空map中元素

4.1.6 查看map大小

4.1.7 map的基础操作函数总结

4.2 unordered\_map

4.2.1 创建unordered\_map容器

4.2.2 unordered\_map容器的成员方法

4.2.3 unordered\_map实例演示代码

4.2.4 unordered\_map遍历

4.3 map和unordered\_map对比

--------------------

# 4.map问题+unordered\_map问题 #

## 4.1 map ##

map是STL的一个关联容器，它提供一对一的hash。第一个可以称为关键字(key)，每个关键字只能在map中出现一次；第二个可能称为该关键字的值(value)。map以模板(泛型)方式实现，可以存储任意类型的数据，包括使用者自定义的数据类型。Map主要用于资料一对一映射(one-to-one)的情況，map內部的实现自建一颗红黑树，这颗树具有对数据自动排序的功能。在map内部所有的数据都是有序的。

### 4.1.1 map的使用 ###

*  使用map得包含map类所在的头文件：\#include <map>  //注意，STL头文件没有扩展名.h
 *  map对象是模板类，需要关键字和存储对象两个模板参数：std:map<**int**, string> personnel;这样就定义了一个用int作为索引,并拥有相关联的指向string的指针.
 *  为了使用方便，可以对模板类进行一下类型定义，**typedef **map<**int**,CString> UDT\_MAP\_INT\_CSTRING;UDT\_MAP\_INT\_CSTRING enumMap；

### 4.1.2 构造map ###

我们通常用如下方法构造一个map：**map<int, string> mapStudent;**

### 4.1.3 往map中插入元素 ###

map<int, string> mapStudent;
        //插入第一种 用insert函數插入pair
        mapStudent.insert(pair<int, string>(000, "zhangsan"));
        //插入第二种 用insert函数插入value_type数据
        mapStudent.insert(map<int, string>::value_type(001, "lisi"));
        // 插入第三种 用"array"方式插入
        mapStudent[002] = "wangwu";
        mapStudent[003] = "liuqi";

以上三种用法，虽然都可以实现数据的插入，但是它们是有区别的，当然了第一种和第二种在效果上是完成一样的，用insert函数插入数据，在数据的 插入上涉及到集合的唯一性这个概念，即**当map中有这个关键字时，insert操作是不能在插入数据的**，但是用数组方式就不同了，它可以覆盖以前该关键字对应的值。

我们怎么知道insert语句是否插入成功的问题了，可以用pair来获得是否插入成功，程序如下：

// 构造定义，返回一个pair对象
    pair<iterator,bool> insert (const value_type& val);
     
    pair<map<int, string>::iterator, bool> Insert_Pair;
     
    Insert_Pair = mapStudent.insert(map<int, string>::value_type (001, "student_one"));
     
    if(!Insert_Pair.second)
        cout << ""Error insert new element" << endl;

我们通过pair的第二个变量来知道是否插入成功，它的第一个变量返回的是一个map的迭代器，如果插入成功的话Insert\_Pair.second应该是true的，否则为false。

### 4.1.4 在map中查找元素 ###

当所查找的关键key出现时，它返回数据所在对象的位置，如果沒有，返回iter与end函数的值相同。

// find 返回迭代器指向当前查找元素的位置否则返回map::end()位置
    iter = mapStudent.find("123");
     
    if(iter != mapStudent.end())
           cout<<"Find, the value is"<<iter->second<<endl;
    else
       cout<<"Do not Find"<<endl;

### 4.1.5 删除与清空map中元素 ###

//迭代器刪除
    iter = mapStudent.find("123");
    mapStudent.erase(iter);
     
    //用关键字刪除
    int n = mapStudent.erase("123"); //如果刪除了會返回1，否則返回0
     
    //用迭代器范围刪除 : 把整个map清空
    mapStudent.erase(mapStudent.begin(), mapStudent.end());
    //等同于mapStudent.clear()

### 4.1.6 查看map大小 ###

在往map里面插入了数据，我们怎么知道当前已经插入了多少数据呢，可以用size函数，用法如下：

int nSize = mapStudent.size();

### 4.1.7 map的基础操作函数总结 ###

C++ maps是一种关联式容器，包含“关键字/值”对

*       **begin**()         返回指向map头部的迭代器
 *       **clear**(）        删除所有元素
 *       **count**()         返回指定元素出现的次数
 *       **empty**()         如果map为空则返回true
 *       **end**()           返回指向map末尾的迭代器
 *       **equal\_range**()   返回特殊条目的迭代器对
 *       **erase**()         删除一个元素
 *       **find**()          查找一个元素
 *       **get\_allocator**() 返回map的配置器
 *       **insert**()        插入元素
 *       **key\_comp**()      返回比较元素key的函数
 *       **lower\_bound**()   返回键值>=给定元素的第一个位置
 *       **max\_size**()      返回可以容纳的最大元素个数
 *       **rbegin**()        返回一个指向map尾部的逆向迭代器
 *       **rend**()          返回一个指向map头部的逆向迭代器
 *       **size**()          返回map中元素的个数
 *       **swap**()           交换两个map
 *       **upper\_bound**()    返回键值>给定元素的第一个位置
 *       **value\_comp**()     返回比较元素value的函数

## 4.2 unordered\_map ##

hash\_map ≈ unordered\_map，最初的 C++ 标准库中没有类似 hash\_map 的实现，但不同实现者自己提供了非标准的 hash\_map。 因为这些实现不是遵循标准编写的，所以它们在功能和性能保证方面都有细微差别。从 C++ 11 开始，hash\_map 实现已被添加到标准库中。但为了防止与已开发的代码存在冲突，决定使用替代名称 unordered\_map。这个名字其实更具描述性，因为它暗示了该类元素的无序性。

### 4.2.1 创建unordered\_map容器 ###

**头文件：**

#include <unordered_map>

**（1）默认构造函数，可以创建空的 unordered\_map 容器**

std::unordered_map<std::string, std::string> umap;

**（2）在创建 unordered\_map 容器的同时，可以完成初始化操作**

std::unordered_map<std::string, std::string> umap{
        {"Python教程","http://c.biancheng.net/python/"},
        {"Java教程","http://c.biancheng.net/java/"},
        {"Linux教程","http://c.biancheng.net/linux/"} };

**（3）可以调用 unordered\_map 模板中提供的复制（拷贝）构造函数，将现有 unordered\_map 容器中存储的键值对，复制给新建 unordered\_map 容器**

std::unordered_map<std::string, std::string> umap2(umap);

**（4）C++ 11 标准中还向 unordered\_map 模板类增加了移动构造函数，即以右值引用的方式将临时 unordered\_map 容器中存储的所有键值对，全部复制给新建容器。**

//返回临时 unordered_map 容器的函数
    std::unordered_map <std::string, std::string > retUmap(){
        std::unordered_map<std::string, std::string>tempUmap{
            {"Python教程","http://c.biancheng.net/python/"},
            {"Java教程","http://c.biancheng.net/java/"},
            {"Linux教程","http://c.biancheng.net/linux/"} };
        return tempUmap;
    }
    //调用移动构造函数，创建 umap2 容器
    std::unordered_map<std::string, std::string> umap2(retUmap());

### 4.2.2 unordered\_map容器的成员方法 ###

unordered\_map 既可以看做是关联式容器，更属于自成一脉的无序容器。因此在该容器模板类中，既包含一些在学习关联式容器时常见的成员方法，还有一些属于无序容器特有的成员方法。

<table> 
 <tbody> 
  <tr> 
   <th>成员方法</th> 
   <th>功能</th> 
  </tr> 
  <tr> 
   <td>begin()</td> 
   <td>返回指向容器中第一个键值对的正向迭代器。</td> 
  </tr> 
  <tr> 
   <td>end()&nbsp;</td> 
   <td>返回指向容器中最后一个键值对之后位置的正向迭代器。</td> 
  </tr> 
  <tr> 
   <td>cbegin()</td> 
   <td>和 begin() 功能相同，只不过在其基础上增加了 const 属性，即该方法返回的迭代器不能用于修改容器内存储的键值对。</td> 
  </tr> 
  <tr> 
   <td>cend()</td> 
   <td>和 end() 功能相同，只不过在其基础上，增加了 const 属性，即该方法返回的迭代器不能用于修改容器内存储的键值对。</td> 
  </tr> 
  <tr> 
   <td>empty()</td> 
   <td>若容器为空，则返回 true；否则 false。</td> 
  </tr> 
  <tr> 
   <td>size()</td> 
   <td>返回当前容器中存有键值对的个数。</td> 
  </tr> 
  <tr> 
   <td>max_size()</td> 
   <td>返回容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同。</td> 
  </tr> 
  <tr> 
   <td>operator[key]</td> 
   <td>该模板类中重载了 [] 运算符，其功能是可以向访问数组中元素那样，只要给定某个键值对的键 key，就可以获取该键对应的值。注意，如果当前容器中没有以 key 为键的键值对，则其会使用该键向当前容器中插入一个新键值对。</td> 
  </tr> 
  <tr> 
   <td>at(key)</td> 
   <td>返回容器中存储的键 key 对应的值，如果 key 不存在，则会抛出 out_of_range 异常。&nbsp;</td> 
  </tr> 
  <tr> 
   <td>find(key)</td> 
   <td>查找以 key 为键的键值对，如果找到，则返回一个指向该键值对的正向迭代器；反之，则返回一个指向容器中最后一个键值对之后位置的迭代器（如果 end() 方法返回的迭代器）。</td> 
  </tr> 
  <tr> 
   <td>count(key)</td> 
   <td>在容器中查找以 key 键的键值对的个数。</td> 
  </tr> 
  <tr> 
   <td>equal_range(key)</td> 
   <td>返回一个 pair 对象，其包含 2 个迭代器，用于表明当前容器中键为 key 的键值对所在的范围。</td> 
  </tr> 
  <tr> 
   <td>emplace()</td> 
   <td>向容器中添加新键值对，效率比 insert() 方法高。</td> 
  </tr> 
  <tr> 
   <td>emplace_hint()</td> 
   <td>向容器中添加新键值对，效率比 insert() 方法高。</td> 
  </tr> 
  <tr> 
   <td>insert()&nbsp;</td> 
   <td>向容器中添加新键值对。</td> 
  </tr> 
  <tr> 
   <td>erase()</td> 
   <td>删除指定键值对。</td> 
  </tr> 
  <tr> 
   <td>clear()&nbsp;</td> 
   <td>清空容器，即删除容器中存储的所有键值对。</td> 
  </tr> 
  <tr> 
   <td>swap()</td> 
   <td>交换 2 个 unordered_map 容器存储的键值对，前提是必须保证这 2 个容器的类型完全相等。</td> 
  </tr> 
  <tr> 
   <td>bucket_count()</td> 
   <td>返回当前容器底层存储键值对时，使用桶（一个线性链表代表一个桶）的数量。</td> 
  </tr> 
  <tr> 
   <td>max_bucket_count()</td> 
   <td>返回当前系统中，unordered_map 容器底层最多可以使用多少桶。</td> 
  </tr> 
  <tr> 
   <td>bucket_size(n)</td> 
   <td>返回第 n 个桶中存储键值对的数量。</td> 
  </tr> 
  <tr> 
   <td>bucket(key)</td> 
   <td>返回以 key 为键的键值对所在桶的编号。</td> 
  </tr> 
  <tr> 
   <td>load_factor()</td> 
   <td>返回 unordered_map 容器中当前的负载因子。负载因子，指的是的当前容器中存储键值对的数量（size()）和使用桶数（bucket_count()）的比值，即 load_factor() = size() / bucket_count()。</td> 
  </tr> 
  <tr> 
   <td>max_load_factor()</td> 
   <td>返回或者设置当前 unordered_map 容器的负载因子。</td> 
  </tr> 
  <tr> 
   <td>rehash(n)</td> 
   <td>将当前容器底层使用桶的数量设置为 n。</td> 
  </tr> 
  <tr> 
   <td>reserve()</td> 
   <td>将存储桶的数量（也就是 bucket_count() 方法的返回值）设置为至少容纳count个元（不超过最大负载因子）所需的数量，并重新整理容器。</td> 
  </tr> 
  <tr> 
   <td>hash_function()</td> 
   <td>返回当前容器使用的哈希函数对象。</td> 
  </tr> 
 </tbody> 
</table>

### 4.2.3 unordered\_map实例演示代码 ###

#include <iostream>
    #include <string>
    #include <unordered_map>
    using namespace std;
    int main()
    {
        //创建空 umap 容器
        unordered_map<string, string> umap;
        //向 umap 容器添加新键值对
        umap.emplace("Python教程", "http://c.biancheng.net/python/");
        umap.emplace("Java教程", "http://c.biancheng.net/java/");
        umap.emplace("Linux教程", "http://c.biancheng.net/linux/");
        //输出 umap 存储键值对的数量
        cout << "umap size = " << umap.size() << endl;
        //使用迭代器输出 umap 容器存储的所有键值对
        for (auto iter = umap.begin(); iter != umap.end(); ++iter) {
            cout << iter->first << " " << iter->second << endl;
        }
        return 0;
    }
    
    
    /*
    执行结果：
    umap size = 3
    Python教程 http://c.biancheng.net/python/
    Linux教程 http://c.biancheng.net/linux/
    Java教程 http://c.biancheng.net/java/
    */

### 4.2.4 unordered\_map遍历 ###

for (const auto &[k, v] : map)
        {
            cout << k << "===" << v << endl;
        }
    
    //使用迭代器（使用auto）
    
        for (auto iter = map.begin(); iter != map.end(); ++iter)
        {
            cout << iter->first << "===" << iter->second << endl;
        }
    
    //迭代器(已知数据类型的情况下)
        unordered_map<int, int>::iterator iter;
        for (iter = map.begin(); iter != map.end(); ++iter)
        {
            cout << iter->first << "===" << iter->second << endl;
        }

## 4.3 map和unordered\_map对比 ##

**（1）需要引入的头文件不同**

*  map: \#include < map >
 *  unordered\_map: \#include < unordered\_map >

**（2）内部实现机理不同**  
        map： map内部实现了一个红黑树（红黑树是非严格平衡二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉搜索树（又名二叉查找树、二叉排序树，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值）存储的，使用中序遍历可将键值按照从小到大遍历出来。  
unordered\_map: unordered\_map内部实现了一个哈希表（也叫散列表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用），因此，其元素的排列顺序是无序的。

**（3）优缺点以及适用处**

**map：**

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

**unordered\_map：**

*  优点： 因为内部实现了哈希表，因此其查找速度非常的快
 *  缺点： 哈希表的建立比较耗费时间
 *  适用处：对于查找问题，unordered\_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered\_map

**总结：**

*  内存占有率的问题就转化成红黑树 VS hash表 , 还是unorder\_map占用的内存要高。但是unordered\_map执行效率要比map高很多
 *  对于unordered\_map或unordered\_set容器，其遍历顺序与创建该容器时输入的顺序不一定相同，因为遍历是按照哈希表从前往后依次遍历的