C++コンテナ備忘録 コンテナ探索速度比較

単純に探索の速いコンテナはどれなのかテストしてみました．
個人的な備忘録です．

今回対象とするコンテナは以下の通りです．

• std::vector
• std::list
• std::set
• std::unordered_set
• std::map
• std::unordered_map

テストの方法としては

1. 各コンテナに$N$個の乱数を格納
2. 計測開始
3. $0 \sim 100*N$をすべて探索
4. 計測終了

としました．

以下，ソースコードです．

test.cpp

#include<iostream>
#include<iterator>
#include<chrono>
#include<random>
#include<vector>
#include<list>
#include<algorithm>
#include <unordered_set>
#include<set>
#include<map>
#include<unordered_map>


template<class T>
void print_order_time(T start, T end) {
	std::cout<<std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
		<< "ms"<< std::endl;
}

typedef std::chrono::system_clock timer;

int main(void) {
	const int N = 10000;
	std::vector<int> vec;
	std::set<int> set;
	std::unordered_set<int>u_set;
	std::list<int> list;
	std::map<int, int> map;
	std::unordered_map<int, int> u_map;

	std::mt19937 engine;
	std::uniform_int_distribution<int> distribution(0, N);

	vec.resize(N);

	////各コンテナへ乱数の挿入
	for (int i = 0; i < N; i++) {
		int r = distribution(engine);
		vec.push_back(r);
		list.push_back(r);
		set.insert(r);
		u_set.insert(r);
		map[i] = r;
		u_map[i]=r;
	}

	//vectorの探索時間を調べる
	auto start = timer::now();
	for (int i = 0; i < k*100; i++) {
		auto itr = std::find(vec.begin(), vec.end(), i);
		//if (itr != vector.end()) std::cout << *itr << " ";
	}
	auto end = timer::now();
	std::cout << "vector find time is ";
	print_order_time(start, end);

	//リストの探索時間を調べる
	start = timer::now();
	for (int i = 0; i < N * 100; i++) {
		auto itr = std::find(list.begin(), list.end(), i);
		//if (itr != list.end()) std::cout << *itr << " ";
	}
	end = timer::now();
	std::cout << "list find time is ";
	print_order_time(start, end);


	//setの探索時間を調べる
	start = timer::now();
	for (int i = 0; i < N * 100; i++) {
		auto itr = set.find(i);
		//if (itr != myset.end()) std::cout << *itr << " ";
	}
	end = timer::now();
	std::cout << "set find time is ";
	print_order_time(start, end);


	//ハッシュセットの探索時間を調べる
	start = timer::now();
	for (int i = 0; i < N * 100; i++) {
		auto itr = u_set.find(i);
		//if (itr != u_set.end()) std::cout << *itr << " ";
	}
	end = timer::now();
	std::cout << "hashset find time is ";
	print_order_time(start, end);


	//mapの探索時間を調べる
	start = timer::now();
	for (int i = 0; i < N * 100; i++) {
		auto itr = map.find(i);
		//if (itr != map.end()) std::cout << (*itr).second << " ";
	}
	end = timer::now();
	std::cout << "map find time is ";
	print_order_time(start, end);

	//u_mapの探索時間を調べる
	start = timer::now();
	for (int i = 0; i < N * 100; i++) {
		auto itr = u_map.find(i);
		//if (itr != u_map.end()) std::cout << (*itr).second << " ";
	}
	end = timer::now();
	std::cout << "hashmap find time is ";
	print_order_time(start, end);

	return 0;
}

出力は以下の通りになりました・．

vector find time is 1222ms
list find time is 26962ms
set find time is 1084ms
hashset find time is 680ms
map find time is 1602ms
u_map find time is 583ms

考察としてはハッシュ探索アルゴリズムを使っているunordered_set,unordered_mapがつよいですね
おなじ探索アルゴリズムを使ってるはずなのに
秒数に差があるのはなぜなんでしょう．

それとリストの探索が異常に遅いことも気になります．
線形探索だから遅いのは仕方ないにしても遅すぎじゃないですか

理論値としては
vector : $O(N)$　:　線形探索
list : $O(N)$　:　線形探索
set : $O(\log(N))$　:　二分探索
hashset : $O(1)$　:　ハッシュ探索
map : $O(\log(N))$　:　二分探索
hashmap : $O(1)$　:　ハッシュ探索

だと思ってたのですが・・・
listとvectorとの差はなぞですね

mapとsetは赤黒木で実装されてると思います．
vectorも中では二分探索してるんでしょうか？？

本当はいくつかの$n$で探索して計算量算出してみたかったのですが．
今回はここまでです．

何か間違いがあったら報告お願いします．