map/set與unordered_map/unordered_set的區別

xxx容器與unordered_xxx容器對上層所提供函數介面的名字和功能雖然一致，但它們的底層實現卻大不相同，xxx容器和unordered_xxx容器的區別如下：

容器	底層資料結構	是否有序	實現版本	增刪查改的效率	迭代器型別
unordered_map/unordered_set	雜湊表/雜湊表	遍歷無序	C++11	$O(1)$	單向迭代器
map/set	紅黑樹	遍歷有序	C++98	$O(logN)$	雙向迭代器

map/set與unordered_map/unordered_set的效能測試

map容器與unordered_map容器的差別和set容器與unordered_set容器的差別類似，下面我們以set容器和unordered_set容器的測試為例。

說到一個容器的效能，我們最關心的實際就是該容器增刪查改的效率。我們可以通過下列程式碼測試set容器和unordered_set容器insert、find以及erase的效率。

#include <iostream>
#include <set>
#include <unordered_set>
#include <time.h>
using namespace std;

int main()
{
	int N = 1000;
	vector<int> v;
	v.reserve(N);
	srand((unsigned int)time(NULL));
	//隨機生成N個數位
	for (int i = 0; i < N; i++)
	{
		v.push_back(rand());
	}

	/****************插入效率測試****************/
	//將這N個數插入set容器
	set<int> s;
	clock_t begin1 = clock();
	for (auto e : v)
	{
		s.insert(e);
	}
	clock_t end1 = clock();

	//將這N個數插入unordered_set容器
	unordered_set<int> us;
	clock_t begin2 = clock();
	for (auto e : v)
	{
		us.insert(e);
	}
	clock_t end2 = clock();

	//分別輸出插入set容器和unordered_set容器所用的時間
	cout << "set insert: " << end1 - begin1 << endl;
	cout << "unordered_set insert: " << end2 - begin2 << endl;

	/****************查詢效率測試****************/
	//在set容器中查詢這N個數
	clock_t begin3 = clock();
	for (auto e : v)
	{
		s.find(e);
	}
	clock_t end3 = clock();

	//在unordered_set容器中查詢這N個數
	clock_t begin4 = clock();
	for (auto e : v)
	{
		us.find(e);
	}
	clock_t end4 = clock();

	//分別輸出在set容器和unordered_set容器中查詢這N個數所用的時間
	cout << "set find: " << end3 - begin3 << endl;
	cout << "unordered_set find: " << end4 - begin4 << endl;

	/****************刪除效率測試****************/
	//將這N個數從set容器中刪除
	clock_t begin5 = clock();
	for (auto e : v)
	{
		s.find(e);
	}
	clock_t end5 = clock();

	//將這N個數從unordered_set容器中刪除
	clock_t begin6 = clock();
	for (auto e : v)
	{
		us.find(e);
	}
	clock_t end6 = clock();

	//分別輸出將這N個數從set容器和unordered_set容器中刪除所用的時間
	cout << "set erase: " << end5 - begin5 << endl;
	cout << "unordered_set erase: " << end6 - begin6 << endl;
	return 0;
}

對1000個數做增刪查改操作

當N為1000時，set容器和unordered_set容器增刪查改的效率差異並不大，在Debug版本下的測試結果如下：

在Release版本下，set容器和unordered_set容器對1000個數做增刪查改操作所用的時間更是被優化到了接近0毫秒。

對10000000個數做增刪查改操作

而當N為10000000時，set容器和unordered_set容器增刪查改的效率的差異就很明顯了，在Debug版本下的測試結果如下：

而經過Release版本優化後，unordered_set容器對10000000個數做查詢和刪除操作所用的時間還是被優化到了接近0毫秒，插入操作所用的時間也僅僅是0.1秒左右。但是set容器對10000000個數做增刪查改操作所用的時間還是需要1秒左右，與unordered_set容器相比就佔了下風。

注意： 這裡給出的N值僅作參考，在不同的測試環境下可能不同。

測試結論

根據測試結果可以得出以下結論：

• 當處理資料量小時，map/set容器與unordered_map/unordered_set容器增刪查改的效率差異不大。
• 當處理資料量大時，map/set容器與unordered_map/unordered_set容器增刪查改的效率相比，unordered系列容器的效率更高。

因此，當處理資料量較小時，選用xxx容器與unordered_xxx容器的差異不大；當處理資料量較大時，建議選用對應的unordered_xxx容器。

補充一點： 當需要儲存的序列為有序時，應該選用map/set容器。