c++的STL中的map(哈希表)与unordered_map

谁践踏了优雅 2022-10-25 05:58 216阅读 0赞

map:  
unordered\_map:  
map： map内部实现了一个红黑树，该结构具有自动排序的功能，因此map内部的所有元素都是有序的  
unordered\_map:unordered\_map内部实现了一个哈希表，因此其元素的排列顺序是杂乱的，无序的

Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一 种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的，后边我们会见识到有序的好处。

**1、map简介**  
map是一类关联式容器。它的特点是增加和删除节点对迭代器的影响很小，除了那个操作节点，对其他的节点都没有什么影响。  
对于迭代器来说，可以修改实值，而不能修改key。

**2、map的功能**  
自动建立Key－value的对应。key 和 value可以是任意你需要的类型。  
根据key值快速查找记录，查找的复杂度基本是Log(N)，如果有1000个记录，最多查找10次，1,000,000个记录，最多查找20次。  
快速插入Key -Value 记录。  
快速删除记录  
根据Key 修改value记录。  
遍历所有记录。

**3、使用map**  
使用map得包含map类所在的头文件  
\#include  
\#include<bits/stdc++.h>  
map对象是模板类，需要关键字和存储对象两个模板参数：  
**std:map<int,string> personnel;**

**4、map的构造函数**  
map共提供了6个构造函数，这块涉及到内存分配器这些东西，略过不表，在下面我们将接触到一些map的构造方法，这里要说下的就是，我们通常用如下方法构造一个map：

map<int, string> mapStudent;

**5、数据的插入**  
在构造map容器后，我们就可以往里面插入数据了。这里讲三种插入数据的方法：

第一种：用insert函数插入pair数据

using namespace std;  
      
    int main()  
      
    {
          
      
        map<int, string> mapStudent;  
      
        mapStudent.insert(map<int, string>::value_type (1, "student_one"));  
      
        mapStudent.insert(map<int, string>::value_type (3, "student_two"));  
      
        mapStudent.insert(map<int, string>::value_type (2, "student_three"));  
      
        map<int, string>::iterator iter;  
      
        for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)  
      
           cout<<iter->first<<' '<<iter->second<<endl;  
      
    }

**使用迭代器后，是按照字典序来输出的**

![在这里插入图片描述][20210306171554951.png]

//数据的插入--第一种：用insert函数插入pair数据  
    将2个数据组合成一组数据，当需要这样的需求时就可以使用pair，
    如stl中的map就是将key和value放在一起来保存。
    另一个应用是，当一个函数需要返回2个数据的时候，可以选择pair。
    pair的实现是一个结构体，主要的两个成员变量是first second 因为是使用struct不是class，
    所以可以直接使用pair的成员变量。

第二种：用insert函数插入value\_type数据，下面举例说明

//第二种：用insert函数插入value_type数据，下面举例说明  
      
    #include <map>  
      
    #include <string>  
      
    #include <iostream>  
      
    using namespace std;  
      
    int main()  
      
    {
          
      
        map<int, string> mapStudent;  
      
        mapStudent.insert(map<int, string>::value_type (1, "student_one"));  
      
        mapStudent.insert(map<int, string>::value_type (2, "student_two"));  
      
        mapStudent.insert(map<int, string>::value_type (3, "student_three"));  
      
        map<int, string>::iterator iter;  
      
        for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)  
      
           cout<<iter->first<<' '<<iter->second<<endl;  
      
    }

第三种：用数组方式插入数据，下面举例说明

//第三种：用数组方式插入数据，下面举例说明  
      
    #include <map>  
      
    #include <string>  
      
    #include <iostream>  
      
    using namespace std;  
      
    int main()  
      
    {
          
      
        map<int, string> mapStudent;  
      
        mapStudent[1] = "student_one";  
      
        mapStudent[2] = "student_two";  
      
        mapStudent[3] = "student_three";  
      
        map<int, string>::iterator iter;  
      
        for(iter = mapStudent.begin(); iter != mapStudent.end(); iter++)  
      
            cout<<iter->first<<' '<<iter->second<<endl;  
      
    }

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

**6、map的大小**  
在往map里面插入了数据，我们怎么知道当前已经插入了多少数据呢，可以用size函数，用法如下：  
Int nSize = mapStudent.size();

**7、数据的遍历**  
这里也提供三种方法，对map进行遍历  
第一种：应用前向迭代器

第二种：应用反相迭代器

//第二种，利用反向迭代器  
      
    #include <map>  
      
    #include <string>  
      
    #include <iostream>  
      
    using namespace std;  
      
    int main()  
      
    {
          
      
        map<int, string> mapStudent;  
      
        mapStudent.insert(pair<int, string>(1, "student_one"));  
      
        mapStudent.insert(pair<int, string>(2, "student_two"));  
      
        mapStudent.insert(pair<int, string>(3, "student_three"));  
      
        map<int, string>::reverse_iterator iter;  
      
        for(iter = mapStudent.rbegin(); iter != mapStudent.rend(); iter++)  
      
            cout<<iter->first<<"  "<<iter->second<<endl;  
      
    }

![在这里插入图片描述][20210131142406181.png]  
第三种，用数组的形式，程序说明如下：

//第三种：用数组方式，程序说明如下  
      
    #include <map>  
      
    #include <string>  
      
    #include <iostream>  
      
    using namespace std;  
      
    int main()  
      
    {
          
      
        map<int, string> mapStudent;  
      
        mapStudent.insert(pair<int, string>(1, "student_one"));  
      
        mapStudent.insert(pair<int, string>(2, "student_two"));  
      
        mapStudent.insert(pair<int, string>(3, "student_three"));  
      
        int nSize = mapStudent.size();  
      
    //此处应注意，应该是 for(int nindex = 1; nindex <= nSize; nindex++)  
    //而不是 for(int nindex = 0; nindex < nSize; nindex++)  
      
        for(int nindex = 1; nindex <= nSize; nindex++)  
      
            cout<<mapStudent[nindex]<<endl;  
      
    }

**8、查找并获取map中的元素（包括判定这个关键字是否在map中出现）**

第一种：用count函数来判定关键字是否出现，其缺点是无法定位数据出现位置,由于map的特性，一对一的映射关系，就决定了count函数的返回值只有两个，要么是0，要么是1，出现的情况，当然是返回1了

第二种：用find函数来定位数据出现位置，它返回的一个迭代器，当数据出现时，它返回数据所在位置的迭代器，如果map中没有要查找的数据，它返回的迭代器等于end函数返回的迭代器。**查找map中是否包含某个关键字条目用find()方法，传入的参数是要查找的key**，在这里需要提到的是begin()和end()两个成员，分别代表map对象中第一个条目和最后一个条目，这两个数据的类型是iterator.

#include <map>  
      
    #include <string>  
      
    #include <iostream>  
      
    using namespace std;  
      
    int main()  
      
    {
          
      
        map<int, string> mapStudent;  
      
        mapStudent.insert(pair<int, string>(1, "student_one"));  
      
        mapStudent.insert(pair<int, string>(2, "student_two"));  
      
        mapStudent.insert(pair<int, string>(3, "student_three"));  
      
        map<int, string>::iterator iter;  
      
        iter = mapStudent.find(1);  
      
        if(iter != mapStudent.end())  
      
           cout<<"Find, the value is "<<iter->second<<endl;  
      
        else  
      
           cout<<"Do not Find"<<endl;  
          
        return 0;  
    }

![在这里插入图片描述][20210131143138380.png]  
**9、从map中删除元素**  
移除某个map中某个条目用erase（）

mapStudent.erase(iter);  
      
       如果要删除1，用关键字删除  
      
      int n = mapStudent.erase(1);//如果删除了会返回1，否则返回0  
      
       用迭代器，成片的删除  
      
       一下代码把整个map清空  
      
      mapStudent.erase( mapStudent.begin(), mapStudent.end() );  
      
       成片删除要注意的是，也是STL的特性，删除区间是一个前闭后开的集合  
      
       自个加上遍历代码，打印输出吧

**10、map中的swap用法**  
map中的swap不是一个容器中的元素交换，而是两个容器所有元素的交换。

**11、排序-map中的sort问题**  
map中的元素是自动按Key升序排序，所以不能对map用sort函数；

**12、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的函数

map：

1、优点：
    
           （1）有序性：map结构的红黑树自身是有序的，但是要中序遍历输出
    
           （2）时间复杂度低：内部结构时红黑树，红黑树很多操作都是在logn的时间复杂度下实现的，因此效率高。
    
      2、缺点：
    
            空间占有率高，因为map内部实现是红黑树，虽然它时间复杂度低，运行效率高，但是因为每一个节点都需要额外保存父  节点、孩子节点和红黑树性质，这样使得每一个节点都占用大量的空间。
    
      3、应用场景：
    
            应用于对顺序有要求的问题，用map会更高效。

unordered\_map：

1、优点：内部结构是哈希表，查找为O(1)，效率高。
    
     2、缺点：哈希表的建立耗费时间。
    
     3、应用场景：  对于频繁查找的问题，用unordered_map更高效。

总结：

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

map和unordered\_map的使用  
unordered\_map与map用法一致，里面的元素以pair类型存储。虽然底层实现完全不同，但是外部使用一致。

[20210306171554951.png]: /images/20221024/17d158d371e841a5b91c92ba6e7933b8.png
[20210131142406181.png]: /images/20221024/88271e022ed0439d8aa89578648b1e52.png
[20210131143138380.png]: /images/20221024/863c9a40688941fc829b8ef1eb58b2fd.png