零、前言

本章主要讲解unordered系列关联式容器及其底层结构和模拟实现，还有哈希的相关应用等

一、unordered系列关联式容器

• 概念：

1. 在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 ，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想
2. 最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同
3. unordered_map/unordered_set与map/set基本上只有底层实现上的区别，前者是哈希，后者是红黑树
4. unordered_map/unordered_set与unordered_multimap/unordered_multiset的区别是是否允许键值冗余
5. unordered系列关联式容器因为底层不是红黑树了，所以遍历的结果不是排序好的序列

1、unordered_map介绍及使用

• 概念：

1. unordered_map是存储<key, value>键值对的关联式容器，其允许通过key值快速的索引到与其对应是value
2. 在unordered_map中，键值通常用于唯一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同
3. 在内部，unordered_map没有对<key, value>按照任何特定的顺序排序，为了能在常数范围内找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中
4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低
5. unordered_map实现了直接访问操作符（operator[]），它允许使用key作为参数直接访问value
6. 它的迭代器是单向正向迭代器

• 接口介绍：

1. unordered_map的构造

2. unordered_map的容量

3. unordered_map的迭代器

4. unordered_map的元素访问

注意：该函数中实际调用哈希桶的插入操作，用参数key与V()构造一个默认值往底层哈希桶中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中，将key对应的value返回

5. unordered_map的查询

注意：unordered_map中key是不能重复的，因此count函数的返回值最大为 1，对于unordered_multimap才是允许键值冗余的

6. unordered_map的修改操作

7. unordered_map的桶操作

• 使用示例：

void test_unordered_map()
{
	unordered_map<string, string> dict;
	dict.insert(make_pair("string", ""));
	dict.insert(make_pair("sort", ""));

	auto it = dict.begin();
	while (it != dict.end())
	{
		cout << it->first << ":" << it->second << endl;
		++it;
	}
	cout << endl;
}

• 结果：

2、unordered_set的介绍及使用

• 概念：

1. unordered_set是不按特定顺序存储键值的关联式容器，其允许通过键值快速的索引到对应的元素
2. 在unordered_set中，元素的值同时也是唯一地标识它的key
3. 在内部，unordered_set中的元素没有按照任何特定的顺序排序，为了能在常数范围内找到指定的key，unordered_set将相同哈希值的键值放在相同的桶中
4. unordered_set容器通过key访问单个元素要比set快，但它通常在遍历元素子集的范围迭代方面效率较低
5. 它的迭代器是单向前向迭代器

• 接口介绍：

1. unordered_set当中常用的成员函数

2. 迭代器相关函数

• 使用示例：

void test_unordered_set()
{
	unordered_set<int> s;
	s.insert(3);
	s.insert(4);
	s.insert(5);
	s.insert(3);
	s.insert(1);
	s.insert(2);
	s.insert(6);

	unordered_set<int>::iterator it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

• 结果：

3、性能比较

• 测试代码：

void test_op()
{
	set<int> s;
	unordered_set<int> us;
	const int n = 1000000;
	vector<int> v;
	srand(time(0));
	for (size_t i = 0; i < n; ++i)
	{
		v.push_back(rand());
	}

	size_t begin1 = clock();
	for (auto e : v)
	{
		s.insert(e);
	}
	size_t end1 = clock();

	size_t begin2 = clock();
	for (auto e : v)
	{
		us.insert(e);
	}
	size_t end2 = clock();

	cout << "set insert:" << end1 - begin1 << endl;
	cout << "unordered_set insert:" << end2 - begin2 << endl;
	cout << "=====================" << endl;
	size_t begin3 = clock();
	for (auto e : v)
	{
		s.find(e);
	}
	size_t end3 = clock();

	size_t begin4 = clock();
	for (auto e : v)
	{
		us.find(e);
	}
	size_t end4 = clock();

	cout << "set find:" << end3 - begin3 << endl;
	cout << "unordered_set find:" << end4 - begin4 << endl;

	cout << "=====================" << endl;
	size_t begin5 = clock();
	for (auto e : v)
	{
		s.erase(e);
	}
	size_t end5 = clock();

	size_t begin6 = clock();
	for (auto e : v)
	{
		us.erase(e);
	}
	size_t end6 = clock();

	cout << "set erase:" << end5 - begin5 << endl;
	cout << "unordered_set erase:" << end6 - begin6 << endl;
}

• 结果：

总结：使用底层为哈希的容器总体的效率是非常高的，对于关联式set/map的复杂度能达到O(logN)，而unordered系列关联式容器可以达到接近O(1)的水平