1、map/multimap容器简介

• map 的特性是所有的元素都会根据元素的键值自动排序。map所有元素都是pair(对组)，同时拥有实值和键值，pair的第一元素被认为是键值。
• 不能通过map的迭代器改变map的键值，因为map的键值关系到map元素的排序规则，任意改变map的键值将会破坏map组织。如果想修改map的实值是可以的。
• map和list拥有相同的某些性质，在对容器进行插入或删除操作时，除了删除元素外其他所有元素的迭代器依然有效。
• multimap和map的操作类似，唯一区别是multimap键值可以重复。
• map和multimap都是以红黑树为底层实现机制。

2、API

/*******************************map**********************************/
map<T1,T2> mapT;//map默认构造函数
map(const map& mp);//拷贝构造函数
/*******************************map赋值操作****************************/
map& operator=(const map& mp);//重载等号操作符
swap(mp);//交换两个集合容器
/*******************************map大小操作****************************/
size();//返回容器中元素的数目
empty();//判断容器是否为空
/*******************************插入数据元素**************************/
map<int,string> m;
//第一种：通过pair方式插入对象
m.insert(pair<int,string>(3,"小张"));
//第二种:通过pair方式插入对象
m.insert(make_pair(1,"小明"));
//第三种:通过value_type方式插入对象
m.insert(map<int,string>::value_type(2,"小李"));
//第四种：通过数组方式插入值
m[3]="小刘";
/*******************************删除操作**************************/
clear();//删除所有元素
erase(pos);//删除pos迭代器所指向的元素，返回下一个元素的迭代器
erase(beg,end);//删除区间[beg,end)的所有元素，返回下一个元素的迭代器
erase(keyElem);//删除容器中key为keyElem的对组
/*******************************查找操作**************************/
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、使用

insert、find

#include<iostream>
#include<map>
#include<string>
#include<algorithm>
using namespace std;
void test()
{
	map<int, string> m;
	m.insert(pair<int, string>(9527, "星爷"));//第一种插入方式
	m.insert(make_pair(10010, "联通"));//第二种插入方式（推荐！！！）
	m.insert(map<int, string>::value_type(10086, "移动"));//第三种插入方式
	m[10000] = "电信";//第四种插入方式（在访问map数据时推荐使用！！！！！）
	for_each(m.begin(),m.end(),[](pair<int,string> val){
		cout << val.first << "  " << val.second << endl;
	});
	cout << "***********************************************************" << endl;
	//m[10]寻找key为10的值
	//但是如果容器中没有key为10，使用m[10]会创建一个key为10实值为空的对组
	//如果容器中有key为10，那么m[10]代表key=10的值
	//建议务必确保所需访问的元素存在
	cout << m[10] << endl;
	cout << m[9527] << endl;
	cout << "***********************************************************" << endl;
	//若不能确定key值是否存在，可以先行判断
	map<int, string>::const_iterator mit;
	mit = m.find(10);
	if (mit == m.end()) {
		cout << "未找到!" << endl;
	}
	else {
		cout << m[10] << endl;
	}
}

案例1：map和vector配合使用

LoL职业联赛：有4个战队，随机抽签出场，请打印出场顺序

#include<numeric>//极少的算法
#include<stdlib.h>
#include<time.h>
#include<iostream>
#include<map>
#include<string>
#include<algorithm>

using namespace std;
void test{
    //设置种子
    srand(time(NULL));
    //战队容器(战队编号，战队名称)
    map<int,string> m;
    m.insert(make_pair(1,"RNG"));
    m.insert(make_pair(2,"IG"));
    m.insert(make_pair(3,"WE"));
    m.insert(make_pair(4,"EDG"));
    
    //使用vector存放战队编号
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    //随机抽签(洗牌)，打乱容器元素顺序
    random_shuffle(v.begin(),v.end());
    //随机出场
    for_each(v.begin(),v.end(),[=](int val){
        cout<<m[val]<<"战队出场！"<<endl;//val就是m容器中的key值
    });
}
//multimap允许key相同，map不允许key相同
void test2()
{
    //战队容器（战队编号，战队名称）
    map<int,string> m;
    m.insert(make_pair(1,"RNG"));
    m.insert(make_pair(1,"IG"));
    cout<<m[1]<<endl;//RNG
    cout<<m.count(1)<<endl;//1
    
    //战队容器（战队编号，战队名称）
	multimap<int, string> mm;
	mm.insert(make_pair(1, "RNG"));
	mm.insert(make_pair(1, "IG"));
	//cout << mm[1] << endl;//error,multimap没有[]运算符
	cout << mm.count(1) << endl;//2
}

案例2：multimap案例

公司招聘5名员工，需要指派他们到各部门工作。人员信息有：姓名、年龄、电话、工资等，通过multimap进行信息的插入、保存、显示。分部门显示员工信息，显示全部员工信息。

#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<algorithm>
using namespace std;

class Person {
public:
	string name;
	int age;
	Person(string n, int a){
		name = n;
		age = a;
	}
};
void createPerson(vector<Person>& v)
{
	v.push_back(Person("员工A", 21));
	v.push_back(Person("员工B", 25));
	v.push_back(Person("员工C", 24));
	v.push_back(Person("员工D", 27));
	v.push_back(Person("员工E", 26));

}
void createDepartmentToPerson(multimap<int, Person>& m, vector<Person>& v)
{
	for (int i = 0; i < v.size(); i++){
		int op=0;
		cout << "请输入" << v[i].name << "的部门号(1,2,3):";
		cin >> op;
		switch (op){
		case 1:
			m.insert(make_pair(1, v[i])); break;
		case 2:
			m.insert(make_pair(2, v[i])); break;
		case 3:
			m.insert(make_pair(3, v[i])); break;
		}
	}
}
void printDepartment(multimap<int, Person> m, int op)
{
	string depart;
	switch (op){
	case 1:
		depart = "技术部"; break;
	case 2:
		depart = "测试部"; break;
	case 3:
		depart = "后勤部"; break;
	}

	multimap<int, Person>::const_iterator ret;
	ret = m.find(op);//判断查找的部门号是否存在
	if (ret != m.end()){
		cout << depart << "的员工有:" << endl;
		int count = m.count(op);//统计部门号重复的次数
		for (int i = 0; i < count; i++){
			cout << (*ret).second.name << ",年龄" << (*ret).second.age << endl;
			++ret;//multimap容器已经按键值排序，所以键值相同的数据紧挨着
		}
	}
	else{
		cout << depart << "没有员工!" << endl;
	}
}
int main()
{
	vector<Person> v;//存放员工信息
	createPerson(v);//创建员工
	multimap<int, Person> m;//存放部门号和员工信息
	createDepartmentToPerson(m, v);//创建部门到员工的映射
	printDepartment(m, 1);//打印部门员工
	printDepartment(m, 2);
	printDepartment(m, 3);

	return 0;
}

4、vector、deque、list、set、map应用场景

• vector的使用场景：比如软件历史操作记录的存储，我们经常要查看历史记录，比如上一次记录，上上次记录，但却不会去删除记录，因为记录是事实的描述。
• deque的使用场景：比如排队购票系统，对排队者的存储可以采用deque，支持头端的快速移除，尾端的快速添加。如果采用vector，则头端移除时，会移动大量数据，速度漫。
• vector和deque的比较：①vector.at()比deque.at()效率高，比如vector.at(0)是固定的，deque的开始位置却是不固定的；②如果有大量释放操作的话，vector花的时间更少，这跟二者的内部实现有关；③deque支持头部的快速插入和删除，这是deque的优点。
• list的使用场景：比如公交车乘客的存储，随时可能有乘客下车，支持频繁的不确定位置元素的移除插入。
• set的使用场景：比如对手机游戏的个人得分记录的存储，存储要求从高分到低分的顺序排列。
• map的使用场景：比如按ID号存储十万个用户，想要快速通过ID查找对应的用户。二叉树的查找效率就体现出来了。如果是vector容器，最坏的情况可能要遍历完整个容器才能找到该用户。