C++-STL-组件(一)-容器08：map/multimap（字典）

阳光穿透心脏的1/2处 2023-09-28 10:05 65阅读 0赞

### 1、map/multimap基本概念 ###

Map的特性是，所有元素都会根据元素的键值自动排序。Map所有的元素都是pair,同时拥有实值和键值，pair的第一元素被视为键值，第二元素被视为实值，map不允许两个元素有相同的键值。

我们可以通过map的迭代器改变map的键值吗？答案是不行，因为map的键值关系到map元素的排列规则，任意改变map键值将会严重破坏map组织。如果想要修改元素的实值，那么是可以的。

Map和list拥有相同的某些性质，当对它的容器元素进行新增操作或者删除操作时，操作之前的所有迭代器，在操作完成之后依然有效，当然被删除的那个元素的迭代器必然是个例外。

Multimap和map的操作类似，唯一区别multimap键值可重复。

Map和multimap都是以红黑树为底层实现机制。

### 2、map/multimap常用API ###

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

map<T1, T2> mapTT;//map默认构造函数: 
    map(const map &mp);//拷贝构造函数

#### 2.2 map赋值操作 ####

map& operator=(const map &mp);//重载等号操作符
    swap(mp);//交换两个集合容器

#### 2.3 map大小操作 ####

size();//返回容器中元素的数目
    empty();//判断容器是否为空

#### 2.4 map插入数据元素操作 ####

map.insert(...); //往容器插入元素，返回pair<iterator,bool>
    map<int, string> mapStu;
    // 第一种 通过pair的方式插入对象
    mapStu.insert(pair<int, string>(3, "小张"));
    // 第二种 通过pair的方式插入对象
    mapStu.inset(make_pair(-1, "校长"));
    // 第三种 通过value_type的方式插入对象
    mapStu.insert(map<int, string>::value_type(1, "小李"));
    // 第四种 通过数组的方式插入值
    mapStu[3] = "小刘";
    mapStu[5] = "小王";

#### 2.5 map删除操作 ####

clear();//删除所有元素
    erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
    erase(beg,end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
    erase(keyElem);//删除容器中key为keyElem的对组。

#### 2.6 map查找操作 ####

find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；/若不存在，返回map.end();
    count(keyElem);//返回容器中key为keyElem的对组个数。对map来说，要么是0，要么是1。对multimap来说，值可能大于1。
    lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
    upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
    equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。

### 3、multimap案例 ###

//公司今天招聘了5个员工，5名员工进入公司之后，需要指派员工在那个部门工作
    //人员信息有: 姓名 年龄 电话 工资等组成
    //通过Multimap进行信息的插入 保存 显示
    //分部门显示员工信息 显示全部员工信息
    
    #define _CRT_SECURE_NO_WARNINGS
    
    #include<iostream>
    #include<map>
    #include<string>
    #include<vector>
    using namespace std;
    
    //multimap 案例
    //公司今天招聘了 5 个员工，5 名员工进入公司之后，需要指派员工在那个部门工作
    //人员信息有: 姓名 年龄 电话 工资等组成
    //通过 Multimap 进行信息的插入 保存 显示
    //分部门显示员工信息 显示全部员工信息
    
    
    #define SALE_DEPATMENT 1 //销售部门
    #define DEVELOP_DEPATMENT 2 //研发部门
    #define FINACIAL_DEPATMENT 3 //财务部门
    #define ALL_DEPATMENT 4 //所有部门
    
    //员工类
    class person{
        
    public:
    	string name; //员工姓名
    	int age; //员工年龄
    	double salary; //员工工资
    	string tele; //员工电话
    };
    
    //创建5个员工
    void CreatePerson(vector<person>& vlist){
        
    
    	string seed = "ABCDE";
    	for (int i = 0; i < 5; i++){
        
    		person p;
    		p.name = "员工";
    		p.name += seed[i];
    		p.age = rand() % 30 + 20;
    		p.salary = rand() % 20000 + 10000;
    		p.tele = "010-8888888";
    		vlist.push_back(p);
    	}
    
    }
    
    //5名员工分配到不同的部门
    void PersonByGroup(vector<person>& vlist, multimap<int, person>& plist){
        
    
    
    	int operate = -1; //用户的操作
    
    	for (vector<person>::iterator it = vlist.begin(); it != vlist.end(); it++){
        
    
    		cout << "当前员工信息:" << endl;
    		cout << "姓名：" << it->name << " 年龄:" << it->age << " 工资:" << it->salary << " 电话：" << it->tele << endl;
    		cout << "请对该员工进行部门分配(1 销售部门, 2 研发部门, 3 财务部门):" << endl;
    		scanf("%d", &operate);
    
    		while (true){
        
    
    			if (operate == SALE_DEPATMENT){
          //将该员工加入到销售部门
    				plist.insert(make_pair(SALE_DEPATMENT, *it));
    				break;
    			}
    			else if (operate == DEVELOP_DEPATMENT){
        
    				plist.insert(make_pair(DEVELOP_DEPATMENT, *it));
    				break;
    			}
    			else if (operate == FINACIAL_DEPATMENT){
        
    				plist.insert(make_pair(FINACIAL_DEPATMENT, *it));
    				break;
    			}
    			else{
        
    				cout << "您的输入有误，请重新输入(1 销售部门, 2 研发部门, 3 财务部门):" << endl;
    				scanf("%d", &operate);
    			}
    
    		}
    
    	}
    	cout << "员工部门分配完毕!" << endl;
    	cout << "***********************************************************" << endl;
    
    }
    
    //打印员工信息
    void printList(multimap<int, person>& plist, int myoperate){
        
    
    	if (myoperate == ALL_DEPATMENT){
        
    		for (multimap<int, person>::iterator it = plist.begin(); it != plist.end(); it++){
        
    			cout << "姓名：" << it->second.name << " 年龄:" << it->second.age << " 工资:" << it->second.salary << " 电话：" << it->second.tele << endl;
    		}
    		return;
    	}
    
    	multimap<int, person>::iterator it = plist.find(myoperate);
    	int depatCount = plist.count(myoperate);
    	int num = 0;
    	if (it != plist.end()){
        
    		while (it != plist.end() && num < depatCount){
        
    			cout << "姓名：" << it->second.name << " 年龄:" << it->second.age << " 工资:" << it->second.salary << " 电话：" << it->second.tele << endl;
    			it++;
    			num++;
    		}
    	}
    }
    
    //根据用户操作显示不同部门的人员列表
    void ShowPersonList(multimap<int, person>& plist, int myoperate){
        
    
    	switch (myoperate)
    	{
        
    	case SALE_DEPATMENT:
    		printList(plist, SALE_DEPATMENT);
    		break;
    	case DEVELOP_DEPATMENT:
    		printList(plist, DEVELOP_DEPATMENT);
    		break;
    	case FINACIAL_DEPATMENT:
    		printList(plist, FINACIAL_DEPATMENT);
    		break;
    	case ALL_DEPATMENT:
    		printList(plist, ALL_DEPATMENT);
    		break;
    	}
    }
    
    //用户操作菜单
    void PersonMenue(multimap<int, person>& plist){
        
    
    	int flag = -1;
    	int isexit = 0;
    	while (true){
        
    		cout << "请输入您的操作((1 销售部门, 2 研发部门, 3 财务部门, 4 所有部门, 0退出)：" << endl;
    		scanf("%d", &flag);
    
    		switch (flag)
    		{
        
    		case SALE_DEPATMENT:
    			ShowPersonList(plist, SALE_DEPATMENT);
    			break;
    		case DEVELOP_DEPATMENT:
    			ShowPersonList(plist, DEVELOP_DEPATMENT);
    			break;
    		case FINACIAL_DEPATMENT:
    			ShowPersonList(plist, FINACIAL_DEPATMENT);
    			break;
    		case ALL_DEPATMENT:
    			ShowPersonList(plist, ALL_DEPATMENT);
    			break;
    		case 0:
    			isexit = 1;
    			break;
    		default:
    			cout << "您的输入有误，请重新输入!" << endl;
    			break;
    		}
    
    		if (isexit == 1){
        
    			break;
    		}
    	}
    
    }
    
    int main(){
        
    
    	vector<person>  vlist; //创建的5个员工 未分组
    	multimap<int, person> plist; //保存分组后员工信息
    
    	//创建5个员工
    	CreatePerson(vlist);
    	//5名员工分配到不同的部门
    	PersonByGroup(vlist, plist);
    	//根据用户输入显示不同部门员工信息列表 或者 显示全部员工的信息列表
    	PersonMenue(plist);
    
    	system("pause");
    	return EXIT_SUCCESS;
    }

## 九、STL容器使用时机 ##

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>vector</th> 
   <th>deque</th> 
   <th>list</th> 
   <th>set</th> 
   <th>multiset</th> 
   <th>map</th> 
   <th>multimap</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>典型内存结构</td> 
   <td>单端数组</td> 
   <td>双端数组</td> 
   <td>双向链表</td> 
   <td>二叉树</td> 
   <td>二叉树</td> 
   <td>二叉树</td> 
   <td>二叉树</td> 
  </tr> 
  <tr> 
   <td>可随机存取</td> 
   <td>是</td> 
   <td>是</td> 
   <td>否</td> 
   <td>否</td> 
   <td>否</td> 
   <td>对key而言：不是</td> 
   <td>否</td> 
  </tr> 
  <tr> 
   <td>元素搜寻速度</td> 
   <td>慢</td> 
   <td>慢</td> 
   <td>非常慢</td> 
   <td>快</td> 
   <td>快</td> 
   <td>对key而言：快</td> 
   <td>对key而言：快</td> 
  </tr> 
  <tr> 
   <td>元素安插移除</td> 
   <td>尾端</td> 
   <td>头尾两端</td> 
   <td>任何位置</td> 
   <td>-</td> 
   <td>-</td> 
   <td>-</td> 
   <td>-</td> 
  </tr> 
 </tbody> 
</table>

 vector的使用场景：比如软件历史操作记录的存储，我们经常要查看历史记录，比如上一次的记录，上上次的记录，但却不会去删除记录，因为记录是事实的描述。

 deque的使用场景：比如排队购票系统，对排队者的存储可以采用deque，支持头端的快速移除，尾端的快速添加。如果采用vector，则头端移除时，会移动大量的数据，速度慢。

vector与deque的比较：

1.  vector.at()比deque.at()效率高，比如vector.at(0)是固定的，deque的开始位置 却是不固定的。
2.  如果有大量释放操作的话，vector花的时间更少，这跟二者的内部实现有关。
3.  deque支持头部的快速插入与快速移除，这是deque的优点。

 list的使用场景：比如公交车乘客的存储，随时可能有乘客下车，支持频繁的不确实位置元素的移除插入。

 set的使用场景：比如对手机游戏的个人得分记录的存储，存储要求从高分到低分的顺序排列。

 map的使用场景：比如按ID号存储十万个用户，想要快速要通过ID查找对应的用户。二叉树的查找效率，这时就体现出来了。如果是vector容器，最坏的情况下可能要遍历完整个容器才能找到该用户。