一、unordered系列關(guān)聯(lián)式容器

在C++98中，STL提供了底層為紅黑樹結(jié)構(gòu)的一系列關(guān)聯(lián)式容器，在查詢時效率可達(dá)到 l o g 2 N log_2N log2?N，即最差情況下需要比較紅黑樹的高度次，當(dāng)樹中的節(jié)點非常多時，查詢效率也不理想。最好的查詢是，進(jìn)行很少的比較次數(shù)就能夠?qū)⒃卣业剑虼嗽贑++11中，STL又提供了4個unordered系列的關(guān)聯(lián)式容器，這四個容器與紅黑樹結(jié)構(gòu)的關(guān)聯(lián)式容器使用方式基本類似，只是其底層結(jié)構(gòu)不同

二、unordered_set的介紹

1.unordered_set是不按特定順序存儲鍵值的關(guān)聯(lián)式容器，其允許通過鍵值快速的索引到對應(yīng)的元素。

2.在unordered_set中，元素的值同時也是唯一的標(biāo)識它的key。

3.在內(nèi)部，unordered_set中的元素沒有按照任何特定的順序排序，為了能在常數(shù)范圍內(nèi)找到指定的key，unordered_set將相同哈希值的鍵值放在相同的桶中。

4.unordered_set容器通過key訪問單個元素要比set快，但它通常在遍歷元素子集的范圍迭代方面效率較低。

5.它的迭代器至少是前向迭代器。

三、unordered_set的使用

3.1 unordered_set的定義方式

• 方式一：構(gòu)造一個某類型的空容器。

unordered_set<int> s1;

• 方式二：拷貝構(gòu)造某同類型容器的復(fù)制品

unordered_set<int> s2(s1);

• 方式三：使用迭代器拷貝構(gòu)造某一段內(nèi)容。

string str("abcdef");
unordered_set<char> s3(str.begin(),str.end());

3.2 unordered_set接口的使用

unordered_set當(dāng)中常用的成員函數(shù)如下：

unordered_set當(dāng)中迭代器相關(guān)函數(shù)如下：

3.3 unordered_multiset

unordered_multiset 容器與unordered_set容器的底層數(shù)據(jù)結(jié)構(gòu)是一樣的，都是哈希表，其次，它們所提供的成員函數(shù)的接口都是基本一致的，這兩種容器的唯一區(qū)別就是，unordered_multiset容器允許鍵值冗余，即unordered_multiset容器當(dāng)中存儲的元素是可以重復(fù)的。

由于unordered_multiset容器允許鍵值冗余，因此該容器中成員函數(shù)find和count的意義與unordered_set容器中的也有所不同：

四、unordered_map的介紹

1. unordered_map是存儲<key, value>鍵值對的關(guān)聯(lián)式容器，其允許通過keys快速的索引到與其對應(yīng)的value。
2. 在unordered_map中，鍵值通常用于惟一地標(biāo)識元素，而映射值是一個對象，其內(nèi)容與此鍵關(guān)聯(lián)。鍵和映射值的類型可能不同。
3. 在內(nèi)部,unordered_map沒有對<kye, value>按照任何特定的順序排序, 為了能在常數(shù)范圍內(nèi)找到key所對應(yīng)的value，unordered_map將相同哈希值的鍵值對放在相同的桶中。
4. unordered_map容器通過key訪問單個元素要比map快，但它通常在遍歷元素子集的范圍迭代方面效率較低。
5. unordered_maps實現(xiàn)了直接訪問操作符(operator[])，它允許使用key作為參數(shù)直接訪問value。
6. 它的迭代器至少是前向迭代器。

五、unordered_map的使用

5.1 unordered_map的定義方式

• 方式一：指定key和value的類型構(gòu)造一個空容器

unordered_map<string, int> m1;

• 方式二：拷貝構(gòu)造某同類型容器的復(fù)制品

unordered_map<string, int> m2(m1);

• 方式三：使用迭代器拷貝構(gòu)造某一段內(nèi)容

unordered_map<string, int> m3(m2.begin(),m2.end());

5.2 unordered_map接口的使用

unordered_map當(dāng)中常用的成員函數(shù)如下：

除了上述的成員函數(shù)之外，unordered_map容器當(dāng)中還實現(xiàn)了[ ]運算符重載函數(shù)，該重載函數(shù)的功能非常強(qiáng)大：

• 若當(dāng)前容器中已有鍵值為key的鍵值對，則返回該鍵值對value的引用
• 若當(dāng)前容器中沒有鍵值對key的鍵值對，則先插入鍵值對<key, value>，然后再返回該鍵值對中value的引用

unordered_map當(dāng)中迭代器相關(guān)函數(shù)如下：

5.3 unordered_multimap

unordered_multimap容器與unordered_map容器的底層數(shù)據(jù)結(jié)構(gòu)是一樣的，都是哈希表，其次，它們所提供的成員函數(shù)的接口都是基本一致的，這兩種容器唯一的區(qū)別就是，unordered_multimao容器允許鍵值冗余，即unordered_multimap容器當(dāng)中存儲的鍵值對的key值是可以重復(fù)的。

由于unordered_multimap容器允許鍵值對的鍵值冗余，因此該容器中成員函數(shù)find和count的意義與unordered_map容器中的也有所不同：

其次，由于unordered_multimap容器允許鍵值對冗余，調(diào)用[ ]運算符重載函數(shù)時，應(yīng)該返回鍵值為key的哪一個鍵值對的value的引用存在歧義，因此在unordered_multimap容器當(dāng)中沒有實現(xiàn)[ ]運算符重載函數(shù)

六、完整代碼

6.1 test.cpp

#define _CRT_SECURE_NO_WARNINGS 1

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

void test_unordered_set1()
{
	unordered_set<int> s;
	s.insert(1);
	s.insert(3);
	s.insert(2);
	s.insert(7);
	s.insert(2);

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

	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

void test_unordered_map1()
{
	string arr[] = { "蘋果", "西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜",
	"蘋果", "香蕉", "蘋果", "香蕉" };
	unordered_map<string, int> countMap;
	
	for (auto& e : arr)
	{
		countMap[e]++;
	}

	for (auto& kv : countMap)
	{
		cout << kv.first << ":" << kv.second << endl;
	}
}


int main()
{
	test_unordered_set1();
	test_unordered_map1();

	return 0;
}

總結(jié)

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

最新評論