C++STL容器总结篇之map

曾经终败给现在 2023-10-11 15:01 85阅读 0赞

### 一、关于map的介绍 ###

map是STL的一个容器，和set一样，map也是一种关联式容器。**它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力**，由于这个特性，有助于我们处理一对一数据。这里说下map内部数据的组织，map内部是自建一颗**红黑树**(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以**在map内部所有的数据都是有序的**。学习map我们一定要理解什么是一对一的数据映射？  
比如：一个班级中，每个学生的学号跟他的姓名就存在着一一映射的关系，这个模型用map可能轻易描述，很明显学号用int 描述，姓名用字符串描述采用的string，于是我们使用的map形式如下：map<int , string> student;

关于map和set底层实现以及效率问题，在另一篇[《C++STL中set容器的一点总结》][C_STL_set]已经说了一些，map和set底层实现都是采用了平衡树来实现的。这里说一下map和set容器的区别。

> 对于map中的每个节点存储的是一对信息，包括一个键和一个值，各个节点之间的键值不能重复。  
> 对于set中的每个节点存储的是一个信息，只有一个键，但是每个键值也是唯一的。set表示的是集合的概念。

对于map的学习，或者说是对STL中的容器的学习，要知道每种容器的实现原理，每种适合适合解决什么问题的，才关键~~~~

### 二、map容器中的函数 ###

#### 2.1 构造函数 ####

map() //默认构造函数
    map(const map& m) //拷贝构造函数
    map(iterator begin, iterator end ); //区间构造函数
    map(iterator begin, iterator end, const traits& _compare) //带比较谓词的构造函数
    map(iterator begin, iterator end, const traits& _compare, const allocator& all) //带分配器

map的构造函数主要是调用“拷贝构造函数”和利用“迭代器”进行初始化两种方式，因此就不逐个演示了。

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

#### 2.2 map中的基础函数 ####

begin()，end()，rbegin()，rend()，empty()，clear()，size()，max_size()。
    以上常用的函数，看到名字应该就知道怎么用了吧，示例代码如下：

#include<iostream>
    #include<map>
    using namespace std;
    
    int main(){
        
    	map<int, string> student;
    	map<int, string>::iterator ite;
    	
    	student.insert(pair<int, string>(1001, "张三"));
    	student.insert(pair<int, string>(1002, "李四"));
        student[1005] = "王五"; //也可以这样插入
        
    	cout << "迭代器中元素如下：" << endl;
    	for(ite = student.begin(); ite != student.end(); ite++){
        
    		cout << ite->first << "   " << ite->second << endl;
    	}
    	cout << endl;
    	
    	cout << "map 的 size 的值为：" << student.size() << endl;
    	cout << "map 的 max_size 的值为：" << student.max_size() << endl;
    
    	student.clear();
    	if(student.empty()){
        
    		cout << "map 为空！" << endl;
    	}else{
        
    		cout << "map 不为空！" << endl;
    	}
    
    	return 0;
    }

运行结果：  
![在这里插入图片描述][20201121134033548.png_pic_left]

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

#### 2.3 map中的查找元素 ####

find函数和count函数在map中都能用来查找，但因为map中的键值是不允许重复的，所以一个键值只能出现一次，这说明count的返回值就只能是0或1了，那么显然这就能完成查找了。但是用count来完成查找并不是最优的选择，因为原来的本意是用count来完成计数的，这在vector等序列式容器中是灰常好用的，而map中之所以有这个count函数，就是为了STL提供统一的接口，这样说来map中的upper\_bound和lower\_bound，equel\_range等函数组合起来也是可以完成查找功能的（想一想怎么实现）。这里有个疑问：count和find对于完成的效率是不是一致的呢？？  
我们分别看看分别用find和count来完成查找：

运行结果：  
![在这里插入图片描述][20201121135354678.png_pic_left]  
看到了吗，count和find还是有区别的，那就是**count只能单纯的查找元素是否存在，而find能定位要查找元素的位置**。有一点需要注意的是查找的参数是键值哦！！

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

#### 2.3 map中的数据的插入与删除 ####

map中数据的插入，数据的插入大概有三种方式:

1. insert(pair<T1,T2,>(key1,value1))
    2. insert(map<T1,T2>::value_type(key1,value1)) //这种插入方式和第一种基本相似
    3. 利用数组进行插入，这个一会用程序演示吧。

map中数据的删除也有三种方式：

1. erase(map<T1,T2>::iterator iter)	//删除迭代器所指的节点
    2. erase(key k)	//根据键值进行删除，删除键值k所指的节点 
    3. erase(map<T1,T2>::iteratormap iter1，<T1,T2>::iteratoriter2)//删除iter1和iter2之间的数据

#include<iostream>
    #include<map>
    using namespace std;
    
    int main(){
        
    	map<int, string> student;
    	map<int, string>::iterator ite;
    	
    	//插入演示
    	student.insert(pair<int, string>(1001, "张三"));
    	student.insert(pair<int, string>(1001, "张三11111"));
    	student.insert(map<int, string>::value_type(1002, "李四"));
    	student.insert(map<int, string>::value_type(1002, "李四111"));
        student[1003] = "王五";
        student[1003] = "王五1111";
        
    	cout << "迭代器中元素如下：" << endl;
    	for(ite = student.begin(); ite != student.end(); ite++){
        
    		cout << ite->first << "   " << ite->second << endl;
    	}
    	cout << endl;
    
    	//删除演示
    	student[1004] = "小明";//演示删除新增两个数据
    	student[1005] = "小红";
    	
        cout << "第一种删除，迭代器删除首数据：" << endl;
        ite = student.begin();
    	student.erase(ite);
    	for(ite = student.begin(); ite != student.end(); ite++){
        
    		cout << ite->first << "   " << ite->second << endl;
    	}
    	cout << endl;
    	
    	cout << "第二种删除，利用键值删除map中的数据：" << endl;
    	student.erase(1004);
    	for(ite = student.begin(); ite != student.end(); ite++){
        
    		cout << ite->first << "   " << ite->second << endl;
    	}
    	cout << endl;
    	
    	cout << "第三种删除，利用键利用范围迭代器删除map中的所有数据：" << endl;
        student.erase(student.begin(), student.end());
    	for(ite = student.begin(); ite != student.end(); ite++){
        
    		cout << ite->first << "   " << ite->second << endl;
    	}
    	cout << endl;
    	
    	return 0;
    }

![在这里插入图片描述][20201121141151871.png_pic_left]  
**注意**：通过观察输出结果，**利用数组进行插入对数据进行了覆盖，而其他两种插入方式没有进行覆盖**，实际上属于插入失败，还要注意的是，利用数组进行插入下标实际上是键值。

[参考博客https://www.cnblogs.com/BeyondAnyTime/archive/2012/08/24/2654353.html][https_www.cnblogs.com_BeyondAnyTime_archive_2012_08_24_2654353.html]

[C_STL_set]: https://blog.csdn.net/weixin_43819566/article/details/109893234
[20201121134033548.png_pic_left]: https://img-blog.csdnimg.cn/20201121134033548.png?#pic_left
[20201121135354678.png_pic_left]: https://img-blog.csdnimg.cn/20201121135354678.png?#pic_left
[20201121141151871.png_pic_left]: https://img-blog.csdnimg.cn/20201121141151871.png?#pic_left
[https_www.cnblogs.com_BeyondAnyTime_archive_2012_08_24_2654353.html]: https://www.cnblogs.com/BeyondAnyTime/archive/2012/08/24/2654353.html