C++ map和unordered_map的区别和联系以及map的使用

在c++中有两个关联容器，一个是map，另一个是unordered_map。下面说一下他们之间内部实现机理。

一、map和unordered_map的实现机理：
map:是基于红黑树来实现的（红黑树是非常严格的平衡二叉搜索树），红黑树具有自动排序功能，红黑树的每一个节点都代表着map中的一个元素，因此对于map的查找，删除和插入操作都是对红黑树的操作。
unordered_map:是基于哈希表来实现的，查找的时间复杂度是O(1),在海量数据处理中有着广泛的应用。

二、map和unordered_map的优缺点
map的优点：（1）map是有序的（2）基于红黑树实现，查找的时间复杂度是O(n)
map的缺点：空间占用率比较高，因为内部实现了红黑树，虽然提高了运行效率，但是每个节点都要保存父亲节点和孩子节点和红黑树的性质，使得每一个节点都占用大量的空间。
适用的情况：对于要有序的结构，适用map
unordered_map的优点：因为内部是哈希表来实现的，所以查找效率会非常高
unordered_map的缺点：哈希表的建立比较费时
适用的情况：对于查找问题，适用unordered_map会更好一点。

三、map的常用操作

/*map中常用的操作
*begin()	还回指向map头部的迭代器
*clear()	删除所有元素，注意是所有元素
*count()	还回指定元素出现的次序
*empty()	如果map为空则还回true
*end()		还回指向map末尾的迭代器
*erase()	删除一个元素
*find()		查找一个元素
*insert()	插入一个元素
*max_size()	还回可以容纳的最大元素个数
*size()		还回map中元素的个数
*swap()		交换两个map
*/

int main() {
	map m;
	//一、数据的插入
	m.insert(pair(1, 'a'));
	m.insert(pair(3, 'b'));
	m.insert(pair(2, 'c'));
	m.insert(pair(-1, 'd'));
	map::iterator it = m.begin();
	for (; it != m.end(); it++) {
		cout << it->first << ":" << it->second << endl;
	}
	//二、数据的查找
	/*（1）使用find()函数，该函数可以找到key对应的value
	（2）使用count()函数,该函数的还回值只有0和1，1为找到，但是还回要查找的值*/
	it = m.find(1);
	if (it != m.end()) { cout << "find" << it->second << endl; }
	else { cout << "not find" << endl; }

	//三、map的清空
	//m.clear(m.begin(), m.end());

	//四、数据的删除
	//m.erase(it);

	//五、map的反向遍历，使用反向迭代容器
	
	for (map::reverse_iterator Rit = m.rbegin(); Rit!=m.rend(); Rit++) {
		cout << Rit->first << ":" << Rit->second;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

反向代理容器的原理：

四、按照Value排序
把map中的元素放到vector中，然后对vector进行排序。

bool Vcmp(pair p1,pair p2) {
	return p1.second < p2.second;
}
int main() {
	map m;
	m[0] = 1;
	m[1] = 1;
	m[2] = 5;
	m[3] = 4;
	map::iterator it;
	for (it=m.begin(); it != m.end(); it++) {
		cout << it->first << ":" << it->second;
	}
	cout << endl;
	vector> vec(m.begin(), m.end());
	sort(vec.begin(),vec.end(),Vcmp);
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i].second << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21