【C++STL详解(十三)】unordered系列容器的介绍与使用

目录

前言

一、unordered_map

介绍

使用 

构造方式

修改 

容量

迭代器

元素访问

查询

桶操作 

二、unordered_set

介绍

使用

构造

修改

容量

 迭代器（只有单向)

查询

桶操作 

三、unordered系列的性能测试

前言

前面提到的map/set是C++98提供的关联式容器，底层结构是红黑树，最差情况下需要比较树得高度次，若树的结点十分多时，查询效率也不是很理想。C++11中，又提供了4个unordered系列容器，使用起来和map/set基本类似，只是底层结构不同。unordered系列底层是哈希结构（严格来说是哈希桶结构），最快的查询可以达到O(1)。

一、unordered_map

介绍

• unordered_map是存储<key,value>键值对的关联式容器，KV模型
• 键值key通常用于惟一地标识元素（不存在相同元素），而映射值是一个对象，其内容与此
  键关联。键和映射值的类型可能不同。
• 内部没有任何的排序，是无序的，这点和map的最大区别，map有序
• unordered_map通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭
  代方面效率较低。
• 同样也支持operator【】访问
• 底层是哈希桶结构
• 迭代器是单向的，因为底层结构

使用 

使用上和map可以说是基本类似了！除了迭代器

构造方式

	unordered_map<string, int> m;//无参构造
	unordered_map<string, int> m1(m);//拷贝构造
	unordered_map<string, int> m2(m1.begin(), m1.end());//迭代器区间构造

	//初始化列表构造
	unordered_map<string, int> m3 ={ { "aa", 2 }, { "bb",3 } };

修改 

	unordered_map<int, int> m;//无参构造
	vector<int> a = {3,6,9,4,2,10};
	for (auto b : a)
	{
		m.insert({ b,b });
	}
	m.erase(3);
	unordered_map<int, int> m1;
	m.swap(m1);

	m.clear();

容量

	unordered_map<string, int> m3 ={ { "aa", 2 }, { "bb",3 } };
	m3.empty();//判空
	m3.size();//大小

迭代器

	unordered_map<string, int> m3 ={ { "aa", 2 }, { "bb",3 } };
	auto it = m3.begin();
	while (it!=m3.end())
	{
		cout << it->first << ":" << it->second << endl;
		++it;
	}

 注意：这个系列只提供单向迭代器！！

元素访问

operator【】：返回key对应的value的引用，和map一样！功能强大，既能插入又能修改！

	unordered_map<string, int> m3 ={ { "aa", 2 }, { "bb",3 } };
	m3["aa"] = 4;

查询

注意：Key是唯一的，不允许重复，所以count为0/1！

	auto it = m3.find("aa");
	m3.count("aa");

桶操作 

二、unordered_set

介绍

• unordered_set是存储key的关联式容器，K模型，底层可以看出<key,key>
• 键值key通常用于惟一地标识元素（不存在相同元素）
• 内部没有任何的排序，是无序的，这点和set的最大区别，set有序
• unordered_set通过key访问单个元素要比set快，但它通常在遍历元素子集的范围迭
  代方面效率较低。
• 底层是哈希桶结构
• 迭代器是单向的，因为底层结构

使用

构造

和set基本一样，这里直接看实例就好了！

	unordered_set<int> s;//无参
	unordered_set<int> s1(s);//拷贝

	vector<int> a = { 3,6,9,4,2,10,3 };
	unordered_set<int> s2(a.begin(),a.end());//迭代区间
	//初始化列表
	unordered_set<int> s3 = { 6,7,1,2,4,9,10 };

修改

	unordered_set<int> m;//无参构造
	vector<int> a = {3,6,9,4,2,10};
	for (auto b : a)
	{
		m.insert(b);
	}
	m.erase(3);
	unordered_set<int> m1;
	m.swap(m1);
	m.clear();

容量

	unordered_set<int> s3 = { 3,6,9,4,2,10,3 };
	s3.size();
	s3.empty();

 迭代器（只有单向)

	unordered_set<int> s3 = { 3,6,9,4,2,10,3 };
	auto it = s3.begin();
	while (it != s3.end())
	{
		cout << *it << endl;
		++it;
	}

查询

auto it = s3.find(3);
s3.count(3);// 0/1

桶操作 

	cout << s3.bucket_count() << endl;//统计桶的总数
	cout << s3.bucket_size(3) << endl;//返回3号桶中的数据个数
	cout << s3.bucket(3) << endl;//放回3所在的桶号

注意：还有两个容器这里就不过多介绍了，这几个容器使用起来差别不算很大，也比较简单，大家可以点击unordered_multiset和unordered_multimap查看，区别就是multi系列可以存在重复元素

三、unordered系列的性能测试

void test_set2()
{
	const size_t N = 1000000;
	unordered_set<int> us;
	set<int> s;

	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; ++i)
	{
		//v.push_back(rand()); // N比较大时，重复值比较多
		//v.push_back(rand()+i); // 重复值相对少
		v.push_back(i); // 没有重复，有序
	}

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

	size_t begin2 = clock();
	for (auto e : v)
	{
		us.insert(e);
	}
	size_t end2 = clock();
	cout << "unordered_set insert:" << end2 - begin2 << endl;

	int m1 = 0;
	size_t begin3 = clock();
	for (auto e : v)
	{
		auto ret = s.find(e);
		if (ret != s.end())
		{
			++m1;
		}
	}
	size_t end3 = clock();
	cout << "set find:" << end3 - begin3 << "->" << m1 << endl;

	int m2 = 0;
	size_t begin4 = clock();
	for (auto e : v)
	{
		auto ret = us.find(e);
		if (ret != us.end())
		{
			++m2;
		}
	}
	size_t end4 = clock();
	cout << "unorered_set find:" << end4 - begin4 << "->" << m2 << endl;

	cout << "插入数据个数：" << s.size() << endl;
	cout << "插入数据个数：" << us.size() << endl << endl;

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

	size_t begin6 = clock();
	for (auto e : v)
	{
		us.erase(e);
	}
	size_t end6 = clock();
	cout << "unordered_set erase:" << end6 - begin6 << endl << endl;

}

int main()
{
	test_set2();
	//test_map1();
	return 0;
}

大家可以copy到自己的编译器看看其他不同的结果，上述代码的结果如下：

可以看到unordered系列查找的速度确实快啊！因为底层的结构。

如果对你有那么一点帮助，欢迎点赞+收藏哦！