C++标准模板库STL map介绍

淡淡的烟草味﹌ 2023-02-19 15:23 13阅读 0赞

[算法笔记总目录][Link 1]

## 零. map的常见用途 ##

1.  需要建立字符(或字符串)与整数之间映射的题目，使用map可以减少代码量。
2.  判断大整数或者其他类型数据是否存在的题目，可以把map当bool数组用。
3.  字符串和字符串的映射也有可能会遇到。

延伸：map的键和值是唯一的， 而如果一个键需要对应多个值，就只能用mulimap.另外，C++ 11标准中还增加了unordered\_map, 以散列代替map内部的红黑树实现，使其可以用来处理只映射而不按key排序的需求，速度比map要快得多，有兴趣的读者可以自行了解，此处不多作说明。

## 一. 概念 ##

map是STL的一个关联容器，它提供一对一的数据处理能力。

map对象是模板类，需要关键字和存储对象两个模板参数，其中第一个参数称为关键字，每个关键字只能在map中出现一次；第二个参数称为该关键字的值，可理解为“\{键，值\}对”。例如，学生的“学号”与“姓名”就可以用map进行描述，“学号”对应“关键字”，“姓名”对应“值”，具体的map描述如下：

std::map<int, string> mapStudent;

map内部数据的组织：map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的。

上面语句定义了一个用int作为索引（关键字），并拥有相关联的指向string的指针。为了使用方便，我们可以对模板类使用typedef进行下面的类型定义：

typedef map<int, string> mapStudent_t;
    mapStudent_t mapStudent;

## 二、基本操作 ##

2.1 map构造函数

//法一
    map<int, string> mp;
    //法二
    typedef map<int, string> mapExample;
    mapExample mapStudent;

2.2 map的数据插入操作

注意区别二者

//法一
    mapStudent.insert(pair<int, string>(1, "zhao"));
    mapStudent.insert(pair<int, string>(2, "qian"));
    mapStudent.insert(pair<int, string>(3, "sun"));
    //法二
    mapStudent[1] = "zhao";
    mapStudent[2] = "qian";
    mapStudent[3] = "sun";
    /* 说明：上面的两种方法是有区别的，用insert函数插入数据，涉及到集合的唯一性这个概念， 即当map中有这个关键字时，insert操作是不能实现数据插入的；但是数组方式能够插入数据， 插入的数据会覆盖该关键字之前对应的值。 */

2.3 map中数据的遍历

//map元素访问
    #include <iostream>
    #include <map>
    using namespace std;
    
    int main()
    { 
    	map<char,int> mp;
    	//通过下标访问 
    	mp['c'] = 20;
    	mp['c'] = 30;//20被覆盖
    	printf("%d\n",mp['c']);//输出30
    	
    	//通过迭代器访问
    	mp['m'] = 20;
    	mp['r'] = 30;
    	mp['a'] = 40;
    	for(map<char,int>::iterator it = mp.begin();it != mp.end();it++){ 
    		//it->first是当前映射的键；it->second是当前映射的值 
    		printf("%c %d\n",it->first,it->second);
    	}
    	return 0;
    }

输出如下：

a 40
    m 20
    r 30

注：map会以键从小到大的顺序自动排序，即 a<m<r. 这是由于map内部是使用红黑树实现的也是，在建立映射过程中自动实现排序功能。

## 三、map常用函数 ##

1.find()  
find(key)返回键为key的映射的迭代器，时间复杂度为O(logN),N为map中映射的个数。  
2.erase()

删除单个元素

*  mp.erase(it), it为欲删除的元素的迭代器。时间复杂度为O(1)。
 *  mp.erase(key),key为欲删除的映射的键。时间复杂度为O(logN), N为map内元素的个数。

删除一个区间内的所有元素。

*  mp.erase(first, last), 其中first为雷要删除的区间的起始迭代器，而last则为需要删除的区间的末尾迭代器的下一个地址,也即为删除左闭右开的区间\[first,last)。时间复杂度为O(last- first)。

3.size()  
size()用来获得map中映射的对数，时间复杂度为0(1)。  
4.clear()  
clear()用来清空map中的所有元素，复杂度为O(N),其中N为map中元素的个数。

#include <iostream>
    #include <map>
    using namespace std;
    
    int main()
    { 
    	map<char,int> mp;
    	//###-1-find(key)函数 
    	mp['a'] = 1;
    	mp['b'] = 2;
    	mp['c'] = 3;
    	cout<<"find()对应的字母及其下标为："; 
    	map<char,int>::iterator it = mp.find('b');
    	printf("%c %d\n",it->first,it->second);
    	cout<<endl; 
    	//###-2-erase函数
    	//删除单个元素mp.erase(it)
    	it = mp.find('m');
    	mp.erase(it);//删除b 2
    	cout<<"删除m元素后为："<<endl;
    	for(map<char,int>::iterator it = mp.begin();it != mp.end();it++){ 
    		printf("%c %d\n",it->first,it->second);
    	} 
    	cout<<endl;
    	//删除单个元素mp.erase('r')
    	mp.erase('r');//删除b 2
    	cout<<"删除r元素后为："<<endl;
    	for(map<char,int>::iterator it = mp.begin();it != mp.end();it++){ 
    		printf("%c %d\n",it->first,it->second);
    	} 
    	cout<<endl;
    	//删除一个区间内的所有元素mp.erase(first,last)
    	it=mp.find('b');
    	mp.erase(it,mp.end());//删除b及其后元素 
    	cout<<"删除b及其后元素map为："<<endl;
    	for(map<char,int>::iterator it = mp.begin();it != mp.end();it++){ 
    		printf("%c %d\n",it->first,it->second);
    	} 
    	cout<<endl;
    	//###-3-size()函数
    	cout<<"此时map的长度为："<<mp.size(); //输出为 3 
    	cout<<endl;
    	
    	//###-4-clear函数
    	mp.clear();
    	cout<<"执行clear()后map为："<<endl;
    	for(map<char,int>::iterator it = mp.begin();it != mp.end();it++){ 
    		printf("%c %d\n",it->first,it->second);
    	} 
    	cout<<"此时map的长度为："<<mp.size();//输出为 0
    	cout<<endl;
    	return 0;
    }

四、例题

[6168-Problem-A-Speech Patterns(25)][6168-Problem-A-Speech Patterns_25]

题目描述  
People often have a preference among synonyms of the same word. For example, some may prefer “the police”, while others may prefer “the cops”. Analyzing such patterns can help to narrow down a speaker’s identity, which is useful when validating, for example, whether it’s still the same person behind an online avatar.

Now given a paragraph of text sampled from someone’s speech, can you find the person’s most commonly used word?

输入  
Each input file contains one test case. For each case, there is one line of text no more than 1048576 characters in length, terminated by a carriage return ‘\\n’. The input contains at least one alphanumerical character, i.e., one character from the set \[0-9 A-Z a-z\].  
输出  
For each test case, print in one line the most commonly occurring word in the input text, followed by a space and the number of times it has occurred in the input. If there are more than one such words, print the lexicographically smallest one. The word should be printed in all lower case. Here a “word” is defined as a continuous sequence of alphanumerical characters separated by non-alphanumerical characters or the line beginning/end.

Note that words are case insensitive.

样例输入 Copy

Can1: "Can a can can a can? It can!"

样例输出 Copy

can 5

代码：

//6168-Problem-A-Speech Patterns(25)
    //map元素访问
    #include <iostream>
    #include <map>
    using namespace std;
    
    int main()
    { 
    	string str;
    	while(getline(cin,str)){ 
    		map<string,int> mp;
    		string substr;
    		for(int i=0;i<str.length();i++){ //输入字符串并进行处理 
    			if(str[i] >= 'A' && str[i] <= 'Z'){ //大写字母转化为小写字母 
    				str[i] += 32;
    			}
    		// if(isalpha(str[i]) || (str[i] >= '0' && str[i] <= '9'))
    			if((str[i] >= 'a' && str[i] <= 'z') || (str[i] >= '0' && str[i] <= '9'))
    				substr += str[i];//字母数字字符存入子字符串 
    			else{ 
    				if(substr.length() != 0){ 
    					if(mp.find(substr) != mp.end()){ 
    						mp[substr]++;//在输入字符串中查找子字符串并计数 
    					}
    					else
    						mp[substr] = 1;
    					substr.clear();
    				}
    			}
    		}
    		//单个字符串的特殊情况 
    		if(substr.length() != 0){ 
    			if(mp.find(substr) != mp.end()){ 
    				mp[substr]++;
    			}
    			else
    				mp[substr] = 1;
    			substr.clear();
    		}
    		
    		int max = -1;//遍历子字符串，找到输入字符串中出现最多的字母数字子串 
    		string ans;
    		for(map<string,int>::iterator it = mp.begin();it != mp.end();it++){  
    			if(it->second > max){ 
    				max = it->second;
    				ans = it->first;
    			}
    		} 
    		cout<<ans<<' '<<max;
    		mp.clear();
    	}
    	return 0;
    }

## 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的函数

参考的博客：

[本博客参考的博客1地址链接][1]  
[本博客参考的博客2地址链接][2]

[Link 1]: https://blog.csdn.net/qq_21480607/article/details/106660085
[6168-Problem-A-Speech Patterns_25]: http://codeup.cn/problem.php?cid=100000599&pid=0
[1]: https://blog.csdn.net/liitdar/article/details/80009712
[2]: https://blog.csdn.net/qq_34767784/article/details/103848472