C++之map/set与undered

一、map和undered_map区别

1.map（有序）：map和set都是基于红黑树

元素是按照二叉搜索树存储，进行中序遍历会得到有序遍历。
map的底层是基于红黑树实现的;
优点：有序性，这是map最大的优点，其元素的有序性在很多应用中都会简化很多操作
map的查找，删除，增加等一系列操作的时间复杂度稳定，都为 logn。

缺点：
查找、删除、增加等操作的平均时间复杂度较慢，与n相关

2.unordered_map（无序）：unordered_map和unordered_set基于哈希表
unordered_map的底层基于哈希表实现的,存储机制是哈希表，，即unordered_map内部元素是无序的.
优点：查找，删除添加的速度快，时间复杂度为常数级0（c)

缺点：由于unordered_map的底层是基于哈希表实现的以（key,value)的储存形式，因此空间占用率高。
unordered_map的查找，删除，添加的时间复杂度不稳定,平均为常数级O（c) 取决于哈希函数，极端情况下为O（n).

二、map和undered_map使用

map和unordered_map的使用：
unordered_map的用法和map是一样的，提供了 insert，size，count等操作，并且里面的元素也是以pair类型来存贮的。其底层实现是完全不同的，但是就外部使用来说却是一致的。

三、红黑树和哈希表的比较

map的底层是红黑树，unordered_map底层是哈希表，明明哈希表的查询效率更高，为什么还需要红黑树？

hashmap有unordered_map，map其实就是很明确的红黑树。map比起unordered_map的优势主要有：

1.map始终保证遍历的时候是按key的大小顺序的，这是一个主要的功能上的差异。（有序无序）

2.时间复杂度上，红黑树的插入删除查找性能都是O(logN)而哈希表的插入删除查找性能理论上都是O(1)，他是相对于稳定的，最差情况下都是高效的。哈希表的插入删除操作的理论上时间复杂度是常数时间的，这有个前提就是哈希表不发生数据碰撞。在发生碰撞的最坏的情况下，哈希表的插入和删除时间复杂度最坏能达到O(n)。

3.map可以做范围查找，而unordered_map不可以。

4. 扩容导致迭代器失效。 map的iterator除非指向元素被删除，否则永远不会失效。unordered_map的iterator在对unordered_map修改时有时会失效。

5.因为3，所以对map的遍历可以和修改map在一定程度上并行（一定程度上的不一致通常可以接受），而对unordered_map的遍历必须防止修改map的iterator可以双向遍历，这样可以很容易查找到当前map中刚好大于这个key的值，或者刚好小于这个key的值这些都是map特有而unordered_map不具备的功能。

map和undered_map用法

//1.map和unordered_map用法
#include 
#include 
#include 
#include 
using namespace std;

void map_sum(vector &num, map &result, int target){
	for(int i = 0; i < num.size(); i++){
		for(int j = i+1; j < num.size(); j++){
			if(num[i] + num[j] == target){
				result.insert(make_pair(i,j));
			}
		}
	}
}

void unordered_sum(vector &num, unordered_map &result, int target){
	for(int i = 0; i < num.size(); i++){
		for(int j = i+1; j < num.size(); j++){
			if(num[i] + num[j] == target){
				result.insert(make_pair(i,j));
			}
		}
	}
}

int main(){
	vector num = {0,1,2,3,4,5,6,7,9,10};
	int target = 10;
	map mp_rst;

#if 1
	map_sum(num, mp_rst, target);
	for(auto i : mp_rst) //map里取出为有序
		cout << i.first << " " << i.second<< endl;

#else
	unordered_map un_mp_rst;
	unordered_sum(num, un_mp_rst, target);
	for(auto i : un_mp_rst) //unordered里取出为无序
		cout << i.first << " " << i.second<< endl;
#endif	
}

打印结果：

map: 
0 9
1 8
3 7
4 6

unordered_map: 
4 6
3 7
0 9
1 8

打印说明：

map：是我们想要的结果（有序），key-value对(基于红黑树：二分查找)。

unordered_map：是我们想要的结果（无序）,key-value对(基于哈希)

set和unordered_set用法

#include 
#include 
#include 
#include 
using namespace std;

void set_sum(vector &num, set &result, int target){
	for(int i = 0; i < num.size(); i++){
		for(int j = i+1; j < num.size(); j++){
			if(num[i] + num[j] == target){
				result.insert(i);
				result.insert(j);
			}
		}
	}
}

void unordered_set_sum(vector &num, unordered_set &result, int target){
	for(int i = 0; i < num.size(); i++){
		for(int j = i+1; j < num.size(); j++){
			if(num[i] + num[j] == target){
				result.insert(i);
				result.insert(j);
			}
		}
	}
}

int main(){
	vector num = {0,1,2,3,4,5,6,7,9,10};
	int target = 10;
	set mp_rst;
	set::iterator it;

#if 1
	cout << "set: ";
	set_sum(num, mp_rst, target);
	for(auto i : mp_rst)
		cout << i << " " ;
	cout << endl;
	
//#else
	cout << "unordered_set: ";
	unordered_set un_mp_rst;
	unordered_set_sum(num, un_mp_rst, target);
	for(auto i : un_mp_rst)
		cout << i << " " ;
#endif	
}

打印结果：

set: 0 1 3 4 6 7 8 9
unordered_set: 6 4 9 0 7 1 8 3

输出说明：

set：不是我们想要的结果，因为它把两数等于10的索引，计算出来，又重新排序了.(自作主张).

unordered_set:是我们想要的结果，不过使用的是哈希表，是乱序的。

C++之map/set与undered

C/C++/C#相关栏目本月热门文章