C++基础知识 - map和multimap容器

map/multimap的简介

• map是标准的关联式容器，一个map里存储的元素是一个键值对序列，叫做(key,value)键值对。它提供基于key快速检索数据的能力。
• map中key值是唯一的。集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入，所以不能指定插入位置。
• map底层的具体实现是采用红黑树变体的平衡二叉树的数据结构。在插入操作、删除和检索操作上比vector快很多。
• map可以直接存取key所对应的value，支持[]操作符，如map[key]=value。
• 头文件 #include < map>

multimap与map的区别：

map支持唯一键值，每个键只能出现一次；而multimap中相同键可以出现多次。multimap不支持[]操作符。

	//map
	map<int, string> m1;
	m1.insert(pair<int, string>(1, "张三"));	//map只能出现一次key键
	m1.insert(pair<int, string>(2, "张三"));
	m1.insert(pair<int, string>(3, "张三"));
	//可以使用下标访问符
	m1[4] = "张三";
	for (auto it = m1.begin(); it != m1.end(); it++) {
		cout << "key:" << (*it).first << " value:" << (*it).second << endl;
	}

	//multimap
	multimap<int, string> m1;
	m1.insert(pair<int, string>(1, "张三"));	//multimap支持相同的key键插入
	m1.insert(pair<int, string>(1, "张三"));
	m1.insert(pair<int, string>(1, "李四"));

	//multimap 不支持下标运算符重载
	//m1[4] = "张三";
	for (auto it = m1.begin(); it != m1.end(); it++) {
		cout << "key:" << (*it).first << " value:" << (*it).second << endl;
	}

map/multimap对象的默认构造

map/multimap采用模板类实现，对象的默认构造形式：
	map<T1,T2> mapTT; 
	multimap<T1,T2>  multimapTT;  

如：
	map<int, char> mapA;
	map<string,float> mapB;
	//其中T1,T2还可以用各种指针类型或自定义类型

map和multimap对象的带参数构造

方式一：map(beg,end);     			//将[beg, end)区间中的元素拷贝给本身。
方式二：map(const map &mapObject);  //拷贝构造函数。

	map<int, string> m1;
	m1.insert(pair<int, string>(1, "张三"));
	m1.insert(pair<int, string>(2, "李四"));

	map<int, string> m2(m1.begin(), m1.end());	//将m1的区间元素插入到m2中
	map<int, string> m3(m1);					//将m1容器的元素全部拷贝到m3中

	for (auto it = m3.begin(); it != m3.end(); it++) {
		cout << "key:" << (*it).first << " value:" << (*it).second << endl;
	}

map的插入与迭代器

map.insert(...);    //往容器插入元素，返回pair<iterator,bool>

map中插入元素的四种方式：
假设  map<int, string> mapStu;

	//方式一、通过pair的方式插入对象
	mapStu.insert(pair<int,string>(1,"张三"));
	
	pair<map<int, string>::iterator,bool> ret;
	ret = mapStu.insert(pair<int,string>(1, "小张三"));
	if(ret.second == true){
		cout<<"插入成功! value: "<<(*(ret.first)).second<<endl;
	}else {
		cout<<"插入失败!"<<endl;
	}
	
	//方式二、通过pair的方式插入对象
	mapStu.inset(make_pair(2, "李四"));
	
	//方式三、通过value_type的方式插入对象
	mapStu.insert(map<int,string>::value_type(3,"王五"));
	
	//方式四、通过数组的方式插入值(仅map支持, multimap不支持)
	mapStu[4] = "赵六";
	mapStu[4] = "小赵六";	//mapStu[4] = "赵六" 会被mapStu[4] = "小赵六" 覆盖
	mapStu[5] = “小七"；


注意： 

前三种方法，采用的是insert()方法，该方法返回值为pair<iterator,bool>

第四种方法非常直观，但碰到相同的键时会进行覆盖操作。比如插入key 为4的键值时，先在mapStu中查找主键为4的项，若不存在，则将一个键为4，值为默认初始化值的对组插入到mapStu中，然后再将值修改成“赵六”。若发现已存在4这个键，则修改这个键对应的value。

string strName = mapStu[8];   //取值操作或插入操作

只有当mapStu存在8这个键时才是正确的取操作，否则会自动插入一个实例，键为8，值为默认构造时的初始化值。

迭代器

map.begin();  	//返回容器中第一个数据的迭代器。
map.end();  	//返回容器中最后一个数据之后的迭代器。
map.rbegin();  	//返回容器中倒数第一个元素的迭代器。
map.rend();   	//返回容器中倒数最后一个元素的后面的迭代器

map/multimap 排序

map<T1,T2,less<T1> >  mapA;    //该容器是按键的升序方式排列元素。未指定函数对象，默认采用less<T1>函数对象。
map<T1,T2,greater<T1>> mapB;   //该容器是按键的降序方式排列元素。
less<T1>与greater<T1>  		   //可以替换成其它的函数对象functor。
可编写自定义函数对象以进行自定义类型的比较，使用方法与set构造时所用的函数对象一样。

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

//自定义类
class Demo {
public:
	Demo(int age = 0, string name = "无名") {
		this->name = name;
		this->age = age;
	}

	bool operator<(const Demo& other) const {
		return (this->age < other.age);
	}

	bool operator>(const Demo& other) const {
		return (this->age > other.age);
	}

	int getAge() const {
		return age;
	}
private:
	string name;
	int age;
};

//仿函数
template <typename T1>
class Fun {
public:
	bool operator()(const T1& m1, const T1& m2) const {
		return (m1 > m2);
	}
};

int main(void) {	
	map<Demo, string, Fun<Demo>> m1;	//排序 19 18
	m1.insert(pair<int, string>(18, "张三"));
	m1.insert(pair<int, string>(19, "李四"));
	
	for (auto it = m1.begin(); it != m1.end(); it++) {
		cout << "key:" << (*it).first.getAge() << " value:" << (*it).second << endl;
	}
	
	system("pause");
	return 0;
}

map对象的拷贝构造与赋值

map(const map &mp);		     	//拷贝构造函数
map& operator=(const map &mp);	//重载等号操作符
map.swap(mp);					//交换两个集合容器

	map<int, string> m1, m2;
	m1.insert(pair<int, string>(1, "张三"));
	m1.insert(pair<int, string>(2, "李四"));

	map<int, string> m3(m1);//拷贝构造函数
	m2 = m1;				//赋值构造函数
	m1[0] = "老王";			//插入(0, "老王")	
	m1[1] = "老张";			//把 (1, "张三"), 替换为(1, "老张")
	m3.swap(m2);			//m3的所有元素和m2的所有元素交换

	for (map<int,string>::iterator it = m1.begin(); it != m1.end(); it++) {
		cout << "key:" << (*it).first << " value:" << (*it).second << endl;
	}

map的大小

map.size();		//返回容器中元素的数目
map.empty();	//判断容器是否为空
	
	if(m1.empty()){
		cout<<"m1容器为空"<<endl;
	}

map的删除

map.clear();		//删除所有元素
map.erase(pos);		//删除pos迭代器所指的元素，返回下一个元素的迭代器。
map.erase(beg,end); //删除区间[beg,end)的所有元素，返回下一个元素的迭代器。
map.erase(key);     //删除容器中key为key的对组,返回删除的对组个数
map.erase(key_type *first, key_type *last)  //删除数组指定的半闭半开的区间中特定的key对应的所有队组

	map<int, string> mapA;
	mapA.insert(pair<int,string>(2, "李四"));	  
	mapA.insert(pair<int,string>(1, "张三"));	
	mapA.insert(pair<int,string>(3, "王五"));	
	mapA.insert(pair<int,string>(4, "赵六"));	

	//删除区间内的元素，迭代器指示区间（半闭半开）
	map<int,string>::iterator itBegin=mapA.begin();
	++ itBegin;
	map<int,string>::iterator itEnd=mapA.end();
	mapA.erase(itBegin,itEnd);    //此时容器mapA仅仅包含{1,"张三"}一个元素。

	mapA.insert(pair<int,string>(2, "李四"));	
	mapA.insert(pair<int,string>(3, "王五"));	
	mapA.insert(pair<int,string>(4, "赵六"));

	//删除容器中的第一个元素，使用迭代器指示位置
	mapA.erase(mapA.begin());	//mapA包含{2,"李四"}{3,"王五"}{4,"赵六"}三个元素

	//删除容器中key为4的元素
	mapA.erase(4);    

	//删除mapA的所有元素
	mapA.clear();			//容器为空

map/multimap的查找

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

	//map 查找key元素
	map<int, string> m1;
	m1.insert(pair<int, string>(1, "张三"));
	m1.insert(pair<int, string>(2, "李四"));
	m1.insert(pair<int, string>(3, "王五"));
	m1.insert(pair<int, string>(4, "赵六"));

	map<int, string>::iterator it = m1.find(2);
	if (it != m1.end()) {
		cout << (*it).first << " - " << (*it).second << endl;
	} else {
		cout << "没有找到" << endl;
	}


	//multimap 查找相同key 的元素
	multimap <int, string> m2;
	m2.insert(pair<int, string>(101, "张老师"));
	m2.insert(pair<int, string>(101, "李老师"));
	m2.insert(pair<int, string>(102, "王老师"));
	m2.insert(pair<int, string>(102, "赵老师"));

	multimap<int, string>::iterator mit = m2.find(101);
	if (mit != m2.end()) {
		for (; mit != m2.end(); mit++) {
			if((*mit).first == 101)
			cout << "key:" << (*mit).first << " value:" << (*mit).second << endl;
		}
	} else {
		cout << "没有找到" << endl;
	}


	//equal_range 用法
	map<int, string> m1;
	m1.insert(pair<int, string>(1, "张三"));
	m1.insert(pair<int, string>(2, "李四"));
	m1.insert(pair<int, string>(3, "王五"));
	m1.insert(pair<int, string>(4, "赵六"));

	pair<map<int,string>::iterator, map<int, string>::iterator> iit = m1.equal_range(4);
	if (iit.first != m1.end()) {
		cout << (*(iit.first)).second << endl;		//输出 李四
		if (iit.second != m1.end()) {
			cout << (*(iit.second)).second << endl;	//输出 王五
		}
	} else {
		cout << "没有找到" << endl;
	}