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$で探索して計算量算出してみたかったのですが．
今回はここまでです．

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