【C++】unordered_map和unordered_set的使用及 OJ練習(xí)

這篇具有很好參考價(jià)值的文章主要介紹了【C++】unordered_map和unordered_set的使用及 OJ練習(xí)。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

前言

在前面的文章中，我們已經(jīng)學(xué)習(xí)了STL中底層為紅黑樹結(jié)構(gòu)的一系列關(guān)聯(lián)式容器——set/multiset 和 map/multimap（C++98）

1. unordered系列關(guān)聯(lián)式容器

在C++98中，STL提供了底層為紅黑樹結(jié)構(gòu)的一系列關(guān)聯(lián)式容器，在查詢時(shí)效率可達(dá)到 $log_2 N$ ，即最差情況下需要比較紅黑樹的高度次。
在C++11中，STL又提供了4個(gè)unordered系列的關(guān)聯(lián)式容器，這四個(gè)容器與紅黑樹結(jié)構(gòu)的關(guān)聯(lián)式容器使用方式基本一樣，只是其底層結(jié)構(gòu)不同。
本文中只對(duì)unordered_map和unordered_set進(jìn)行介紹，
unordered_multimap和unordered_multiset大家可自行查看文檔介紹。

2. map、set系列容器和unordered_map、unordered_set系列容器的區(qū)別

首先我們來簡(jiǎn)單說一下前面學(xué)的不帶unordered的幾個(gè)容器和這篇文章學(xué)習(xí)的unordered系列的容器有什么區(qū)別。

首先，它們的底層結(jié)構(gòu)是不一樣的：

我們前面學(xué)習(xí)的那一系列關(guān)聯(lián)式容器——set/multiset 和 map/multimap它們的底層結(jié)構(gòu)是紅黑樹，而我們這篇文章要學(xué)的unordered系列的——unordered_map/unordered_multimap、unordered_set/unordered_multiset它們的底層是哈希表，至于什么是哈希表，大家有的可能聽說過，有的可能沒有，沒關(guān)系，我們后面會(huì)講。
同樣的，unordered系列中，帶multi的和不帶multi的區(qū)別也是允許鍵值重復(fù)出現(xiàn)和不允許重復(fù)出現(xiàn)的問題。

其次，從名字上我們其實(shí)就能得出它們的第二個(gè)區(qū)別：

unordered不就是無序的意思嘛。
所以，map和set我們用迭代器遍歷，得到的是有序的序列，二unordered系列，我們?nèi)ケ闅v的話，得到的是無序的。
其實(shí)單從使用上來說最大的區(qū)別就是這個(gè)。

那說到迭代器，它們的迭代器也是有區(qū)別的：

map和set系列它們的迭代器是雙向迭代器，而unordered系列它們的迭代器是單向迭代器。

3. unordered_map和unordered_set的使用

其實(shí)單從使用來說，大家如果學(xué)會(huì)了我們之前講的C++98的那幾個(gè)關(guān)聯(lián)式容器——set/multiset 和 map/multimap的使用的話，那C++11的這4個(gè)unordered系列的關(guān)聯(lián)式容器其實(shí)大家就直接可以用了，因?yàn)樗鼈兊挠梅ɑ疽恢?，常用的接口都差不多?/font>

所以下面我們就簡(jiǎn)單介紹一下它們的使用，然后做一些練習(xí)，另外還有一些東西是需要我們學(xué)了它們的底層才能看懂的，這篇文章我們也先不做講解。

首先我們可以看一下unordered_map的接口：

常用的接口還是那幾個(gè)，跟map的用法一樣，還有一些看不懂的，我們現(xiàn)在不用管，那些是跟他的底層結(jié)構(gòu)哈希有關(guān)的。
另外我們會(huì)注意到它的迭代器沒有rbegin、rend，因?yàn)樗牡魇菃蜗虻穆?，都不支持反向遍歷。

然后unordered_set我們也可以簡(jiǎn)單看一下：

接口也都差不多，只是set系列的沒有[]和at接口

還是給大家簡(jiǎn)單演示一下它的使用吧：

這使用起來是不是跟set差不多啊，只不過我們看到它這里遍歷是無序的。
當(dāng)然也可以用迭代器遍歷。
我們可以跟set對(duì)比一下

那unordered_map，也簡(jiǎn)單演示一下：

我們可以用unordered_map來跑一下那個(gè)統(tǒng)計(jì)次數(shù)的程序：

同樣我們可以和map對(duì)比一下

其實(shí)還是有序無序的區(qū)別，只不過這里按照key排序，我們的key是漢字（水果名稱），所以不太好看排序的效果。
當(dāng)然這種場(chǎng)景的話其實(shí)順序也不重要了。

那大家思考一下，既然它們好像跟map和set差不多，那為什么還要提高unordered系列呢？有什么優(yōu)勢(shì)嗎？

其實(shí)在文檔里面也有一些說明
比如我們看unordered_map

??，由于它底層使用的哈希結(jié)構(gòu)，使得它們能夠更快的按照鍵值去訪問某個(gè)元素。

4. set與unordered_set性能對(duì)比

那我這里呢也提供了一段代碼，以set和unordered_set為例來測(cè)試對(duì)比一下它們的性能：

因?yàn)閡nordered系列和非unordered系列它們底層的數(shù)據(jù)結(jié)構(gòu)都是一樣的，所以我們這里拿一組去對(duì)比就可以了

先看一下代碼吧：

int main()
{
	const size_t N = 1000000;

	unordered_set<int> us;
	set<int> s;

	vector<int> v;
	v.reserve(N);
	srand((unsigned int)time(nullptr));
	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;

	return 0;
}

簡(jiǎn)單解釋一下這段代碼：

其實(shí)就是搞了一個(gè)set和一個(gè)unordered_set，然后我們?nèi)タ刂飘a(chǎn)生一些隨機(jī)數(shù)，先放到一個(gè)vector里面，再分別插入到set和一個(gè)unordered_set里面，對(duì)比它們插入、查找、刪除的性能。
插入之后我們還統(tǒng)計(jì)了一下實(shí)際插入的個(gè)數(shù)，因?yàn)閞and函數(shù)產(chǎn)生的隨機(jī)數(shù)是有限的。

我們來測(cè)試幾組：

先來10萬個(gè)隨機(jī)數(shù)

我們可以看到unordered_set三種操作都是比較快的，但是大家看到雖然我們產(chǎn)生10萬個(gè)隨機(jī)數(shù)，但是實(shí)際插入只有3萬多個(gè)，因?yàn)閞and產(chǎn)生的隨機(jī)數(shù)會(huì)有大量重復(fù)值。

如果想減少數(shù)據(jù)有大量重復(fù)，可以用這個(gè)：

對(duì)每次產(chǎn)生的隨機(jī)數(shù)加一個(gè)i，因?yàn)閕每次是不同的嘛，這樣重復(fù)數(shù)據(jù)肯定會(huì)減少
運(yùn)行一下

大家自己對(duì)比一下

當(dāng)然我們可以插入i，這樣就沒有重復(fù)值了

所以：

綜合而言，unordered系列的效率是比較高的，尤其是find的效率（因?yàn)樗讓拥墓＝Y(jié)構(gòu)，這個(gè)我們后面會(huì)講）。
當(dāng)然大家不要太關(guān)注我們上面的測(cè)試結(jié)果，因?yàn)榭赡茉谀承┨囟▓?chǎng)景下unordered系列的插入刪除這樣操作不一定有map/set快（比如如果一直插入有序數(shù)據(jù)的話，set底層紅黑樹就會(huì)一直向一邊旋轉(zhuǎn)，最終就會(huì)比較平衡，那它的插入刪除就不一定比unordered差了），但它的查找一定是很快的。
所以我們說的是綜合各種場(chǎng)景而言，unordered系列的綜合性能是較好的。

5. OJ練習(xí)

下面我們來做幾道相關(guān)的OJ題

5.1 在長(zhǎng)度 2N 的數(shù)組中找出重復(fù) N 次的元素

題目鏈接: link
【C++】unordered_map和unordered_set的使用及 OJ練習(xí),C++,c++,開發(fā)語言,數(shù)據(jù)結(jié)構(gòu)

思路分析

這道題給我們一個(gè)長(zhǎng)度為2n的數(shù)組，其中有一個(gè)元素恰好出現(xiàn)n次，我們要找到并返回這個(gè)元素。
那我們是不是統(tǒng)計(jì)出次數(shù)就好辦了，統(tǒng)計(jì)出次數(shù)然后找到次數(shù)為n的返回就行了，那統(tǒng)計(jì)次數(shù)的話我們就可以用unordered_map（當(dāng)然map也可以）。

AC代碼

寫一下代碼：

class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        int n=nums.size()/2;
    
        unordered_map<int,int> m;
        for(auto e:nums)
        {
            m[e]++;
        }

        for(auto e:m)
        {
            if(e.second==n)
                return e.first;
        }
        return -1;
    }
};

5.2 兩個(gè)數(shù)組的交集

題目鏈接: link

【C++】unordered_map和unordered_set的使用及 OJ練習(xí),C++,c++,開發(fā)語言,數(shù)據(jù)結(jié)構(gòu)
這道題我們是不是前面剛做過啊，當(dāng)時(shí)我們用set去搞的，set達(dá)到一個(gè)排序+去重的效果，然后就好辦了（具體解法大家可以去看之前文章的講解）。

那我們今天學(xué)的是unordered_set，它不會(huì)進(jìn)行排序，那我們要怎么解決？

思路分析

那這道題其實(shí)只用unordered_set也能搞：

unordered_set雖然不能排序，但是也是可以去重的，首先我們先對(duì)兩個(gè)數(shù)組進(jìn)行去重。
然后，我們遍歷其中一個(gè)數(shù)組，遍歷的同時(shí)去依次判斷當(dāng)前元素在不在另一個(gè)數(shù)組中，如果在，就是交集。

AC代碼

【C++】unordered_map和unordered_set的使用及 OJ練習(xí),C++,c++,開發(fā)語言,數(shù)據(jù)結(jié)構(gòu)

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> s1(nums1.begin(),nums1.end());
        unordered_set<int> s2(nums2.begin(),nums2.end());
        vector<int> ret;

        for(auto e:s1)
        {
            if(s2.find(e)!=s2.end())
            {
                ret.push_back(e);
            }
        }

        return ret;
    }
};

5.3 兩個(gè)數(shù)組的交集 II

題目鏈接: link
【C++】unordered_map和unordered_set的使用及 OJ練習(xí),C++,c++,開發(fā)語言,數(shù)據(jù)結(jié)構(gòu)
來看這道題，是上一題的一個(gè)升級(jí)版，還是求交集，但是多了一些要去：

返回結(jié)果中每個(gè)元素出現(xiàn)的次數(shù)，應(yīng)與元素在兩個(gè)數(shù)組中都出現(xiàn)的次數(shù)一致（如果在兩數(shù)組中出現(xiàn)次數(shù)不一致，則考慮取較小值）。
但是它沒有要去輸出結(jié)果中每個(gè)元素是唯一的。

怎么搞？

思路分析

那這道題的關(guān)鍵其實(shí)在于控制這個(gè)次數(shù)：

最終返回的交集中，每個(gè)元素出現(xiàn)的次數(shù)要和它們?cè)趦蓚€(gè)數(shù)組中出現(xiàn)的次數(shù)一樣，如果在兩個(gè)數(shù)組中出現(xiàn)次數(shù)不一樣，則取較小值。

所以我們可以這樣搞：

用unordered_map（當(dāng)然map也可以）先統(tǒng)計(jì)出一個(gè)數(shù)組每個(gè)元素的個(gè)數(shù)。
然后遍歷第二個(gè)數(shù)組，依次取每個(gè)元素判斷其是否在map中存在等效鍵（用count接口），如果存在就是交集，放入vector里面并讓其對(duì)應(yīng)的次數(shù)–，如果次數(shù)減到0了，就從map中刪除掉，因?yàn)榇藭r(shí)它的個(gè)數(shù)已經(jīng)等于它在兩數(shù)組中出現(xiàn)次數(shù)的較小值了。
如果不刪除，后面在第二個(gè)數(shù)組中再遇到的話，次數(shù)就會(huì)超。

如果但看思路不太理解的話可以結(jié)合下面的代碼看。

AC代碼

【C++】unordered_map和unordered_set的使用及 OJ練習(xí),C++,c++,開發(fā)語言,數(shù)據(jù)結(jié)構(gòu)

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> m;
        vector<int> ret;
        for(auto e:nums1)
        {
            m[e]++;
        }

        for(auto e:nums2)
        {
            if(m.count(e))
            {
                ret.push_back(e);
                m[e]--;
                
                if(m[e]==0)
                {
                    m.erase(e);
                }
            }
        }

        return ret;
    }
};

5.4 存在重復(fù)元素

題目鏈接: link
【C++】unordered_map和unordered_set的使用及 OJ練習(xí),C++,c++,開發(fā)語言,數(shù)據(jù)結(jié)構(gòu)
這道題給我們一個(gè)數(shù)組，如果存在任意一個(gè)值出現(xiàn)至少兩次，就返回true，否則返回false。

思路分析

那這個(gè)太簡(jiǎn)單了，統(tǒng)計(jì)一下次數(shù)，判斷有沒有次數(shù)大于等于2的就行了

AC代碼

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int,int> m;
        for(auto e:nums)
        {
            m[e]++;
        }

        for(auto e:m)
        {
            if(e.second>=2)
                return true;
        }

        return false;
    }
};

【C++】unordered_map和unordered_set的使用及 OJ練習(xí),C++,c++,開發(fā)語言,數(shù)據(jù)結(jié)構(gòu)

5.5 兩句話中的不常見單詞

題目鏈接: link
【C++】unordered_map和unordered_set的使用及 OJ練習(xí),C++,c++,開發(fā)語言,數(shù)據(jù)結(jié)構(gòu)
這道題其實(shí)就是讓我們找出在兩句話中只出現(xiàn)一次的那些單詞。

思路分析

那其實(shí)思路很簡(jiǎn)單：

只要統(tǒng)計(jì)出這兩句話中每個(gè)單詞出現(xiàn)的次數(shù)就行了，次數(shù)為1的就是要找到不常用單詞。
而這道題麻煩的是他給我們的是兩個(gè)字符串，所以我們要統(tǒng)計(jì)單詞次數(shù)的話可以先按空格把單詞分割出來，放到一個(gè)vector里面，這樣比較好統(tǒng)計(jì)。

AC代碼

class Solution {
public:
    vector<string> uncommonFromSentences(string s1, string s2) {
        //加個(gè)空格，把兩句話合二為一
        string s=s1+' '+s2;

        //按空格拆分句子中的單詞放到vector里面
        vector<string> v;
        string word;
        for(auto e:s)
        {
            if(e!=' ')
            {
                word+=e;
            }
            else
            {
                v.push_back(word);
                word.clear();
            }
        }
        //最后結(jié)束沒有空格，所以要多push一次
        v.push_back(word);

        //統(tǒng)計(jì)次數(shù)
        unordered_map<string,int> m;
        vector<string> ret;

        for(auto e:v)
        {
            m[e]++;
        }

        //只出現(xiàn)一次的單詞就是不常用單詞
        for(auto e:m)
        {
            if(e.second==1)
            {
                ret.push_back(e.first);
            }
        }

        return ret;
    }
};

【C++】unordered_map和unordered_set的使用及 OJ練習(xí),C++,c++,開發(fā)語言,數(shù)據(jù)結(jié)構(gòu)

6. 代碼

#include <iostream>
using namespace std;
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <set>
#include <map>

void test_unordered_set()
{
	unordered_set<int> s;
	s.insert(1);
	s.insert(5);
	s.insert(3);
	s.insert(8);
	s.insert(2);
	s.insert(3);
	for (unordered_set<int>::iterator it = s.begin(); it != s.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;
	for (auto e : s)
	{
		cout << e << " ";
	}
}

void test_unordered_map()
{
	string arr[] = { "蘋果", "西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜",
"蘋果", "香蕉", "蘋果", "香蕉" };
	unordered_map<string, int> m;
	for (auto e : arr)
	{
		m[e]++;
	}
	for (auto& e : m)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;
}


//int main()
//{
//	const size_t N = 1000000;
//
//	unordered_set<int> us;
//	set<int> s;
//
//	vector<int> v;
//	v.reserve(N);
//	srand((unsigned int)time(nullptr));
//	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;
//
//	return 0;
//}

【C++】unordered_map和unordered_set的使用及 OJ練習(xí),C++,c++,開發(fā)語言,數(shù)據(jù)結(jié)構(gòu) 文章來源地址http://www.zghlxwxcb.cn/news/detail-667100.html

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