C++标准模板库(STL)：set/multiset和map/multimap

亦凉 2022-05-09 09:44 268阅读 0赞

set/multiset（包含在set头文件中）和map/multimap（包含在map头文件中）都是关联型容器。

>    关联型容器内部实现为一个二叉树，在二叉树中，每个元素都有一个父节点和两个子节点，左子树的所有元素都比自己小，右子树的所有元素的比自己大。正因为用了二叉树，**使得它可以高效地查找容器中的每一个元素，但却不能实现任意位置的操作。**

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

## map 、multimap(映射和多重映射） ##

>      map<K，T> 类模板定义在 map 文件头中，它定义了一个保存 T 类型对象的 map，每个 T 类型的对象都有一个关联的 K 类型的键。容器内对象的位置是通过比较键决定的。可以用适当的键值从 map 容器中检索对象。图 1 展示了一个用名称作为键的 map<K,T> 容器，对象是整数值，用来表示年龄。
> 
>       map存储无重复键的元素对，而multimap存储允许重复键值得元素对。

![70][]

*  **创建对象**

>      map<T1,T2> m;       //创建一个空的map容器,T1是键，T2是值
> 
>      map<T1,T2,op> m;   //创建一个空的map容器，以op为准则排序
> 
>      map<T1,T2> m（begin，end）;
> 
>      map<T1,T2，op> m（begin，end）;
> 
> op为排序规则，默认为less<T>（升序），也可以自己设置为降序greater<T>，包含在functional头文件中。

map<string, int> m;
    	map<string, int, greater<string>()> m1;

**multimap和map一样，换个名字就行。**

*  **元素的访问(map)**

> **对于map容器，支持\[\]运算来通过键访问值，同时map函数也提供了at（）函数。**
> 
> **例：m\[key\]    m.at(key)**
> 
> **由于multimap允许重复键值，所以不允许通过这种方式访问。**

*  **统计容器大小（map和multimap）**

> **       m.count(key);      //统计元素个数**
> 
> **       m.max\_size();      //容器最大存储量**
> 
> **       m.size();               //容器大小 **

*  **获取头尾迭代器和序列容器一样 **

*  **插入和删除元素 **

//3种插入操作	
    
    map<string, int> m;
    map<string, int, greater<string>> m1;
    pair<string, int> p1("qw", 2);
    m.insert(p1);
    m.insert(make_pair("sd", 6));
    m["er"] = 1;                    //如果存在er这个键就修改该值，不存在则是创建。
    cout << m["qw"] << endl;

//删除
    
    m.erase(key);  //删除键值为key的元素对

### 应用 ###

#include <iostream>
    #include <map>
    #include <string>
    #include<functional>
    using namespace std;
    void print(map<string,int,greater<string>> m)
    {
    	pair<string,int> p;
    	for(auto it=m.begin();it!=m.end();it++)
    	{
    		p=(pair<string,int>)*it;
    		cout<<p.first<<"->"<<p.second<<endl;
    	}
    }
    int main()
     {
        map<string,int,greater<string>> m;
        m["one"]=1;
        m["error"]=0;
        pair<string,int> p("two",2);
        m.insert(make_pair("three",3));
        m.insert(p);
        m.erase("error");
        print(m);
    	return 0;
    }

![70 1][]

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

## set/multiset（集合和多重集合） ##

> 除了没有单独的键，set 容器和 map 容器很相似。

![70 2][]

*  **创建对象**

>        因为和map相比少了键，所以除了键和map的定义方式一样。
> 
>        set<char,greater<char>> s1;

*  **集合的大小**

> **       s.max\_size();      //容器最大存储量**
> 
> **       s.size();               //容器大小 **
> 
> **       s.empty();           //判断容器是否为空**
> 
> **       s.count();            //统计元素**

*  **查找元素**

> s.find(elem);  
> 
> 返回该元素的迭代器。如果没有找到该元素，则指向最后一个元素的下一个元素，即end（）。

*  **插入元素**

> 和map的一模一样，只不过插入的是一个值，而不是（键-值）。
> 
> 不同的是insert（elem）会返回pair<set<T>::iterator,bool>对象，第一个参数是指向插入位置的迭代器，第二个参数是代表是否插入成功，因为set容器不循序重复的元素。

pair<set<int>::iterator, bool> p = s.insert(2);
    	if (p.second == true)
    		cout << endl << "插入成功" << endl;
    	else
    		cout << endl << "插入失败" << endl;

*  **删除元素**

> **s.erase(elem);  **

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

## map和unordered\_map的比较 ##

*  ### **map** ###

> **优点： **  
> 有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作   
> map底层是以红黑树的数据结构实现的，支持的搜索，插入，删除都是O(logn)的时间复杂度。
> 
> **缺点：**   
> 空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间
> 
> **适用处：**对于那些有顺序要求的问题，用map会更高效一些

*  ### **unordered\_map：** ###

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

[70]: /images/20220509/3ffa2c446b91410faae91fe39580ee20.png
[70 1]: /images/20220509/872c9c9493124f8d8e3666b506a351fb.png
[70 2]: /images/20220509/604ae3d169274e7d8eb9806bbf821183.png