[算法笔记]C++标准模板库（STL）（3）map

4.map

map为映射，map可以将任何基本类型（包括stl容器）映射的任何基本类型（包括stl容器）

1）map定义

#include<map>
using namespace std;
map<typename1,typename2>mp;
//如果是字符串到整型的映射，必须使用string而不能使用char数组
map<string,int> mp;
//STL容器的映射
map<set<int>,int>;

2）map容器内元素的访问

1.通过下标访问
与普通数组的访问方式一样，对于map<char,int> mp的map来说，可以使用map[‘c’]来访问它对应的整数
map中的键值必须是唯一的

#include<cstdio>
#include<map>
using namespace std;
int main() {
	map<char, int> mp;
	mp['m'] = 20;
	mp['r'] = 30;
	mp['a'] = 40;
	printf("%d", mp['m']);
	return 0;
}

输出

20

2.通过迭代器访问
迭代器定义：map<typename1,typename2>::iterator it;
map中可以使用it->first来访问键，使用it->second来访问值

#include<cstdio>
#include<map>
using namespace std;
int main() {
	map<char, int> mp;
	mp['m'] = 20;
	mp['r'] = 30;
	mp['a'] = 40;
	for (map<char, int>::iterator it = mp.begin(); it != mp.end(); it++) {
		printf("%c %d\n", it->first, it->second);
	}
	return 0;
}

输出

a 40
m 20
r 30

map会以键的大小从小到大进行排序，内部使用红黑树实现，在建立映射的时候会实现从小到大的排序功能（与set一样）。

3）map常用函数

1.find()
find(key)返回键值为k的映射的迭代器，时间复杂度O(logN)

	#include<cstdio>
	#include<map>
	using namespace std;
	int main() {
		map<char, int> mp;
		mp['a'] = 1;
		mp['b'] = 2;
		mp['c'] = 3;
		map<char, int>::iterator it = mp.find('b');
		printf("%c %d\n", it->first, it->second);
		return 0;
	}

输出

b 2

2.earse()
1)删除单个元素
mp.earse(it);时间复杂度O(1)。

	#include<cstdio>
	#include<map>
	using namespace std;
	int main() {
		map<char, int> mp;
		mp['a'] = 1;
		mp['b'] = 2;
		mp['c'] = 3;
		map<char, int>::iterator it1 = mp.find('b');
		mp.erase(it1);
		for (map<char, int>::iterator it = mp.begin(); it != mp.end(); it++) {
			printf("%c %d\n", it->first, it->second);
		}
		return 0;
	}

输出

a 1
c 3

mp.erase(key)，key为欲删除的键，时间复杂度O(logN)

	#include<cstdio>
	#include<map>
	using namespace std;
	int main() {
		map<char, int> mp;
		mp['a'] = 1;
		mp['b'] = 2;
		mp['c'] = 3;
		map<char, int>::iterator it1 = mp.find('b');
		mp.erase(it1);
		for (map<char, int>::iterator it = mp.begin(); it != mp.end(); it++) {
			printf("%c %d\n", it->first, it->second);
		}
		return 0;
	}

输出

a 1
c 3

2)删除一个区间的元素
mp.erase(first,last)，firsr为开始的迭代器，last为需要删除的区间的末尾迭代器的下一个地址，即[first,last)。时间复杂度O(last-first)

	#include<cstdio>
	#include<map>
	using namespace std;
	int main() {
		map<char, int> mp;
		mp['a'] = 1;
		mp['b'] = 2;
		mp['c'] = 3;
		map<char, int>::iterator it1 = mp.find('b');
		mp.erase(it1, mp.end());//删除it之后的所有映射
		for (map<char, int>::iterator it = mp.begin(); it != mp.end(); it++) {
			printf("%c %d\n", it->first, it->second);
		}
		return 0;
	}

输出

a 1

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