【STL容器学习】-关联容器与map的使用方法

谁借莪１个温暖的怀抱￠ 2022-08-04 11:44 220阅读 0赞

STL提供了4个关联容器：set、multiset、map和multimap。这些容器提供了通过关键字快速存储和访问数据元素的能力。Set和map不允许有重复关键字，而multiset和multimap允许重复关键字。关联容器的几个共同函数如下：  
find(key)：搜索容器中具有指定关键字的元素，返回指向此元素的迭代器。  
lower\_bound(key)：搜索容器中具有指定关键字的第一个元素，返回指向此元素的迭代器。  
upper\_bound(key)：搜索容器中具有指定关键字的最后一个元素，返回指向此元素的迭代器。  
count(key)：返回容器中具有指定关键字的元素的数目。  
Map是比较重要的STL容器，本文主要来介绍map的原理和一些常见的用法。  
1.map实现的原理  
Map内部自建一个一颗红黑树，一种严格意义上的平衡二叉树，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的。  
  
2.数据插入  
1）用insert函数插入pair数据。  
2）用insert函数插入value\_type数据。  
3）用数组方式插入数据。  
以上三种方法，都可以实现插入操作，但是还是有区别的。用insert函数进行插入操作时，在数据的插入上涉及到集合的唯一性这个概念，即当map中有key值时，insert操作无法插入数据。但是如果是用数组方式就不同了，它可以覆盖以前关键字对应的值。可以用pair来获得是否插入成功，Pair<map<int, string>::iterator, bool> Insert\_Pair，执行完insert操作后，通过判断Insert\_Pair.second值的真假来判断是否插入成功。

代码举例及分析如下：

#include <iostream>
    #include <map>
    #include <string>
    using namespace std;
    int _tmain(int argc, _TCHAR* argv[])
    {
    	map<int,string> map1;
    	map1.insert(pair<int,string>(1,"John"));   //insert pair的方式插入
    	map1.insert(pair<int,string>(1,"Jeff"));   //不会再执行插入操作
    	map1.insert(map<int,string>::value_type(2,"King"));    //insert value_type的方式插入
    	map1.insert(map<int,string>::value_type(2,"Jane"));    //不会再执行插入操作
    	map1[3]="Peter";   //数组方式插入
    	map1[3]="Smith";   //会覆盖掉上一个值
    	map<int,string>::iterator p;   //迭代器遍历输出
    	for(p=map1.begin();p!=map1.end();p++)
    	{
    		cout<<p->first<<"\t"<<p->second<<endl;
    	}
    	pair<map<int, string>::iterator, bool> insert_pair;   //用pair判断是否成功插入数据
    	insert_pair=map1.insert(pair<int,string>(4,"Kevin"));
    	if(insert_pair.second)    //判断是否插入成功
    	{
    		cout<<"Insert Kevin Successfully"<<endl;
    	}
    	else
    	{
    		cout<<"Insert Kevin failed"<<endl;
    	}
    	insert_pair=map1.insert(pair<int,string>(4,"Cathy"));
    	if(insert_pair.second)
    	{
    		cout<<"Insert Cathy Successfully"<<endl;
    	}
    	else
    	{
    		cout<<"Insert Cathy failed"<<endl;
    	}
    	for(p=map1.begin();p!=map1.end();p++)
    	{
    		cout<<p->first<<"\t"<<p->second<<endl;
    	}
    	return 0;
    }

执行结果为：  
1 John  
2 King  
3 Smith  
Insert Kevin Successfully  
Insert Cathy failed  
1 John  
2 King  
3 Smith  
4 Kevin  
  
3.数据遍历  
1）应用前向迭代器  
2）应用反向迭代器  
3）用数组方式  
代码及分析如下：

#include <iostream>
    #include <map>
    #include <string>
    using namespace std;
    int _tmain(int argc, _TCHAR* argv[])
    {
    	map<int,string> map1;
    	map1.insert(pair<int,string>(1,"John"));   
    	map1.insert(pair<int,string>(2,"Jeff"));   
    	map1.insert(pair<int,string>(3,"Smith"));
    	map<int,string>::iterator it;   //前向迭代器遍历输出
    	cout<<"应用前向迭代器输出:"<<endl;
    	for(it=map1.begin();it!=map1.end();it++)
    	{
    		cout<<it->first<<"\t"<<it->second<<endl;
    	}
    	map<int,string>::reverse_iterator reverse_it; //反序迭代器
    	cout<<"应用反向迭代器输出:"<<endl;
    	for(reverse_it=map1.rbegin();reverse_it!=map1.rend();reverse_it++)
    	{
    		cout<<reverse_it->first<<"\t"<<reverse_it->second<<endl;
    	}
    	int size = map1.size();
    	cout<<"应用数组方法输出:"<<endl;
    	for(int index=1;index<=size;index++)
    	{
    		cout<<index<<"\t"<<map1[index]<<endl;
    	}
    	return 0;
    }

执行结果为：  
应用前向迭代器输出:  
1 John  
2 Jeff  
3 Smith  
应用反向迭代器输出:  
3 Smith  
2 Jeff  
1 John  
应用数组方法输出:  
1 John  
2 Jeff  
3 Smith  
  
4.数据查找  
1）用count函数判断关键字是否出现，它的缺点是不能定位关键字的位置。  
2）用find函数，它会返回一个迭代器，如果查找到数据，则返回数据所在位置的迭代器，如果没有查找到，则返回end迭代器。  
代码及分析如下：

#include <iostream>
    #include <map>
    #include <string>
    using namespace std;
    int _tmain(int argc, _TCHAR* argv[])
    {
    	map<int,string> map1;
    	map1.insert(pair<int,string>(1,"John"));   
    	map1.insert(pair<int,string>(2,"Jeff"));   
    	map1.insert(pair<int,string>(3,"Smith"));
    	map<int,string>::iterator it;   //前向迭代器遍历输出
    	cout<<"应用前向迭代器输出:"<<endl;
    	for(it=map1.begin();it!=map1.end();it++)
    	{
    		cout<<it->first<<"\t"<<it->second<<endl;
    	}
    	if (map1.count(1)!=0)	//用count函数来进行查找
    	{
    		cout<<"1 is in map"<<endl;
    	}
    	else
    	{
    		cout<<"1 is not in map"<<endl;
    	}
    	if(map1.find(4)!=map1.end())	//用find函数来进行查找
    	{
    		cout<<"4 is in map"<<endl;
    	}
    	else
    	{
    		cout<<"4 is not in map"<<endl;
    	}
    	return 0;
    }

执行结果为：  
应用前向迭代器输出:  
1 John  
2 Jeff  
3 Smith  
1 is in map  
4 is not in map  
  
5.map使用\[ \]符号注意事项  
使用\[ \]对map进行插入或者查找操作非常便捷，但是如果map下标符运用不得当，就会造成意想不到的问题。对于map而言，并没有下标越界的概念，但是却有可能发生关键字在map中不存在的问题。如果访问的关键字在map中并不存在，则map会自动生成相应的关键字，并会给定一个默认的初始值。  
代码和解析如下：

#include <iostream>
    #include <map>
    #include <string>
    using namespace std;
    int _tmain(int argc, _TCHAR* argv[])
    {
    	map<int,string> map1;
    	map1.insert(pair<int,string>(1,"John"));   
    	map1.insert(pair<int,string>(2,"Jeff"));   
    	map1.insert(pair<int,string>(3,"Smith"));
    	if (map1[4] == "Kevin")   //4不存在，map会自动添加，并初始化值为空，即“”
    	{
    		map1[4]="Cathy";
    	}
    	map<int,string>::iterator it;   //前向迭代器遍历输出
    	cout<<"应用前向迭代器输出:"<<endl;
    	for(it=map1.begin();it!=map1.end();it++)
    	{
    		cout<<it->first<<"\t"<<it->second<<endl;
    	}
    	return 0;
    }

执行结果为：  
应用前向迭代器输出:  
1 John  
2 Jeff  
3 Smith  
4  
如输出所示，最后输出4的值为空。这是因为在进行查找操作时，map自动添加4为关键字，且它的值为空。所以，判断语句一直不成立，最后输出仍然为空。