前言

在 C++98 中， STL 提供了底層為紅黑樹結(jié)構(gòu)的一系列關(guān)聯(lián)式容器，在查詢時(shí)效率可達(dá)到O（logN） ，即最差情況下需要比較紅黑樹的高度次，當(dāng)樹中的節(jié)點(diǎn)非常多時(shí)，查詢效率也不理想。最好的查詢是，進(jìn)行很少的比較次數(shù)就能夠?qū)⒃卣业?，因此在C++11 中， STL 又提供了 4 個(gè)

unordered 系列的關(guān)聯(lián)式容器，這四個(gè)容器與紅黑樹結(jié)構(gòu)的關(guān)聯(lián)式容器使用方式基本類似，只是

其底層結(jié)構(gòu)不同.

1.unordered_map

?下面我們對(duì)比一下unordered_map和map的區(qū)別：

看到這里大家發(fā)現(xiàn)了吧，其實(shí)他們的功能一模一樣，只不過底層不一樣。注意：map和set使用的是雙向迭代器? ? ? ? ? unordered系列用的是單向迭代器

map / set? ?：的底層是紅黑樹

unordered_map / unordered_set :的底層是哈希表

為什么要設(shè)計(jì)他們倆呢？因?yàn)楣５牟檎倚史浅８撸?/p>

下面我們進(jìn)入使用環(huán)節(jié)：

一、unordered_map的使用

#include <unordered_map>
#include <unordered_set>
#include <iostream>
using namespace std;

void unordered_map_test()
{
	unordered_map<string, int> ump;
	ump.insert(make_pair("left", 1));
	ump.insert(make_pair("right", 2));
	ump.insert(make_pair("string", 3));
	ump.insert(make_pair("list", 4));
	ump.insert(make_pair("list", 5));
	for (auto& e : ump)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;
	unordered_map<string, int>::iterator it = ump.begin();
	while (it != ump.end())
	{
		cout << it->first << ":" << it->second << endl;
		++it;
	}
}
int main()
{
	unordered_map_test();
}

?我們可以看到unordered的使用方法簡(jiǎn)直和map一模一樣，都是重復(fù)的數(shù)據(jù)不會(huì)被插入，當(dāng)然也有支持重復(fù)數(shù)據(jù)插入的unordered_multimap系列，那么主要區(qū)別在哪里呢？我們來看看：

?可以看到最主要的區(qū)別是unordered系列是無序的，下面我們給出map和unordered系列的性能測(cè)試：

void unordered_map_test2()
{
	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());
		//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;


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

	size_t begin4 = clock();
	for (auto e : v)
	{
		us.find(e);
	}
	size_t end4 = clock();
	cout << "unordered_set find:" << end4 - begin4 << endl << 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;
}

?

先從10000個(gè)隨機(jī)數(shù)為例：

?我們可以看到哈希系列的各項(xiàng)功能都比普通的快，下面我們來100000個(gè)隨機(jī)數(shù)對(duì)比一下：

?可以看到還是unordered系列更快，再來1000000個(gè)：

?從以上的結(jié)果可以看出來為什么c++會(huì)新增哈希系列了，下面是另一臺(tái)機(jī)器測(cè)出的數(shù)據(jù)：

?總結(jié)：綜合各種場(chǎng)景而言，unordered系列綜合性能是更好的，尤其是find更是一騎絕塵。

二、unordered_set的使用

同樣我們先看看set和哈希set有沒有功能的不同：

?還是我們之前說的，set是雙向迭代器哈希系列是單向迭代器，除了迭代器有區(qū)別其他功能幾乎都是一樣的，下面我們演示一下基礎(chǔ)功能如何使用：

void unordered_set_test()
{
	unordered_set<int> ust;
	ust.insert(1);
	ust.insert(7);
	ust.insert(4);
	ust.insert(9);
	ust.insert(3);
	for (auto& e : ust)
	{
		cout << e << " ";
	}
	cout << endl;
	unordered_set<int>::iterator it = ust.begin();
	while (it != ust.end())
	{
		cout << *it << " ";
		++it;
	}
}
int main()
{
	unordered_set_test();
}

習(xí)題練習(xí)：?

?同樣與set的區(qū)別是無序的，以上就是所有內(nèi)容哈希系列的使用，下面我們用哈希系列練習(xí)一道題：

兩個(gè)數(shù)的交集I：

力扣鏈接：力扣

?交集只需要找出兩個(gè)數(shù)組相同的元素就可以了，而且題目告訴了我們每個(gè)元素都是唯一的所以不存在重復(fù)元素.

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
       unordered_set<int> us1(nums1.begin(),nums1.end());
       unordered_set<int> us2(nums2.begin(),nums2.end());
       vector<int> v;
       for (auto& e:us1)
       {
           if (us2.find(e)!=us2.end())
           {
                v.push_back(e);
           }
       }
       return v;
    }
};

首先我們將兩個(gè)數(shù)組的數(shù)分別放入哈希set中，然后我們遍歷第一個(gè)哈希set（也可以遍歷第二個(gè)都是一樣的），然后我們讓第二個(gè)哈希set查找第一個(gè)哈希set中的值，如果找到了就說明這個(gè)數(shù)是交集就放到數(shù)組中，然后最后返回?cái)?shù)組即可。

總結(jié)

哈希系列的容器與之前的容器用法幾乎都是一樣的，經(jīng)常使用STL容器更容易上手，下一篇我們講解哈希表的底層原理并且實(shí)現(xiàn)，所以要想實(shí)現(xiàn)底層還是需要知道人家這個(gè)容器是如何使用的你才能實(shí)現(xiàn)出功能。文章來源地址http://www.zghlxwxcb.cn/news/detail-459244.html

到了這里，關(guān)于【C++】unordered_map和unordered_set的使用的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！