C++コンテナの速度比較

# 概要
C++は様々なコンテナを持っていますがそれぞれ内部的なアルゴリズムが異なるので、特性や得意分野を知ることは効率の良いプログラムを作る上で有用だと考え、比較してみようと思いました。

# unordered_mapとmapの速度比較
unordered_mapとmapですが、全く異なるデータ構造で作られているので面白い結果を出してくれると思います。

## 使ったプログラム
```cpp
#include <chrono>
#include <iostream>

#ifdef TEST_USE_MAP
#   include <map>
namespace {
    template<class K, class V>using map=std::map<K, V>;
}
#else
#   include <unordered_map>
namespace {
    template<class K, class V>using map=std::unordered_map<K, V>;
}
#endif


namespace {
    template<class TimePoint>void elapsed_time(const std::string& msg, const TimePoint& start, const TimePoint& end) {
        std::cout<<msg<<" : "<<std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count()<<" ミリ秒"<<std::endl;
    }
}

int main() {
    constexpr std::size_t ELEMENT_COUNT=10000000;

    map<std::string, std::string> str_str_umap;

    std::string s;
    // 要素の追加
    auto start=std::chrono::high_resolution_clock::now();
    for(std::size_t i=0; i<ELEMENT_COUNT; ++i) {
        s=std::to_string(i);
        str_str_umap[s]=s;
    }
    auto end=std::chrono::high_resolution_clock::now();
    elapsed_time("要素の追加", start, end);

    // 要素の走査(キーからの走査)
    start=std::chrono::high_resolution_clock::now();
    for(std::size_t i=0; i<ELEMENT_COUNT; ++i) {
        s=std::to_string(i);
        str_str_umap.at(s);
    }
    end=std::chrono::high_resolution_clock::now();
    elapsed_time("要素の走査(キー)", start, end);

    // 要素の走査(範囲for)
    start=std::chrono::high_resolution_clock::now();
    for(const auto& sp : str_str_umap) {
    }
    end=std::chrono::high_resolution_clock::now();
    elapsed_time("要素の走査(範囲for)", start, end);

    // 要素の削除
    start=std::chrono::high_resolution_clock::now();
    for(std::size_t i=0; i<ELEMENT_COUNT; ++i) {
        s=std::to_string(i);
        str_str_umap.erase(s);
    }
    end=std::chrono::high_resolution_clock::now();
    elapsed_time("要素の削除", start, end);
}
```

```bash
# std::mapバージョン
$ clang++ -std=c++14 -O0 -DTEST_USE_MAP -o map map.cpp

# std::unordered_mapバージョン
$ clang++ -std=c++14 -O0 -DTEST_USE_UMAP -o umap map.cpp
```

## 結果
### 要素の追加
| 回数 | map | unordered_map |
|:---:|:---:|:-------------:|
|1|17823|9643|
|2|17644|9601|
|3|17641|9674|
|4|17617|9888|
|5|17836|9672|
|平均|17712.2|9695.6|

unordered_mapのほうが1.8倍速いようです。

### 要素の走査(キー)
| 回数 | map | unordered_map |
|:---:|:---:|:-------------:|
|1|10952|5168|
|2|10727|5315|
|3|10715|5343|
|4|10702|5463|
|5|10689|5193|
|平均|10757|5296.4|

unordered_mapのほうが2倍速いです。

### 要素の走査(範囲for)
| 回数 | map | unordered_map |
|:---:|:---:|:-------------:|
|1|375|874|
|2|374|854|
|3|376|849|
|4|373|892|
|5|373|858|
|平均|374.2|865.4|

これは意外だったのですがmapのほうが2.3倍速いようです。

### 要素の削除
| 回数 | map | unordered_map |
|:---:|:---:|:-------------:|
|1|13363|6643|
|2|13565|6815|
|3|13214|6558|
|4|13178|6839|
|5|13301|6481|
|平均|13324.2|6667.2|

unordered_mapのほうが2倍程度速いです。

## 結論
範囲for以外はunordered_mapのほうが2倍近く速いです。

# vectorとdeque
コンテナとしてはvectorが割と有名ですが、dequeもqueueやstackに使われます。

## 使ったプログラム
```cpp
#include <iostream>
#include <string>
#include <chrono>

#ifdef TEST_USE_DEQUE
#   include <deque>
namespace {
    template<class T>using list=std::deque<T>;
}
#else
#   include <vector>
namespace {
    template<class T>using list=std::vector<T>;
}
#endif

namespace {
	template<class Duration> void print_time(const std::string& msg, const Duration& time, const std::string& t="ミリ秒") {
        std::cout<<msg<<" : "<<time.count()<<" "<<t<<std::endl;
	}
	
    template<class Duration, class TimePoint>
    void elapsed_time(const std::string& msg, const TimePoint& start, const TimePoint& end, const std::string& t="ミリ秒") {
        print_time(msg, std::chrono::duration_cast<Duration>(end-start), t);
    }
}

int main() {
	constexpr std::chrono::milliseconds _0ms(0);
    constexpr std::size_t ELEMENT_COUNT=10000000;

    list<std::string> str_list;

    std::string s="1";

    // 要素の追加(push_back)
    auto start=std::chrono::high_resolution_clock::now();
    for(std::size_t i=0; i<ELEMENT_COUNT; ++i) {
        str_list.push_back(s);
    }
    auto end=std::chrono::high_resolution_clock::now();
    elapsed_time<std::chrono::milliseconds>("要素の追加(push_back)", start, end);

    // 要素の追加(insert)
   	std::chrono::milliseconds time(_0ms);
    for(std::size_t i=0; i<ELEMENT_COUNT; i+=100000) {
    	auto itr=std::begin(str_list);
    	start=std::chrono::high_resolution_clock::now();
		str_list.insert(itr, s);
		end=std::chrono::high_resolution_clock::now();
		time+=std::chrono::duration_cast<std::chrono::milliseconds>(end-start);
    }
    print_time("要素の先頭への追加(insert)", time);

    str_list.clear();

    // 要素の追加(emplace_back)
    start=std::chrono::high_resolution_clock::now();
    for(std::size_t i=0; i<ELEMENT_COUNT; ++i) {
        str_list.emplace_back(s);
    }
    end=std::chrono::high_resolution_clock::now();
    elapsed_time<std::chrono::milliseconds>("要素の追加(emplace_back)", start, end);

    // 要素の追加(emplace)
    time=_0ms;
    for(std::size_t i=0; i<ELEMENT_COUNT; i+=100000) {
    	auto itr=std::begin(str_list);
    	start=std::chrono::high_resolution_clock::now();
		str_list.emplace(itr, s);
		end=std::chrono::high_resolution_clock::now();
		time+=std::chrono::duration_cast<std::chrono::milliseconds>(end-start);
    }
    print_time("要素の先頭への追加(emplace)", time);

    // 要素の走査(すべての要素)
    start=std::chrono::high_resolution_clock::now();
    for(std::size_t i=0; i<ELEMENT_COUNT; ++i) {
        str_list.at(i);
    }
    end=std::chrono::high_resolution_clock::now();
    elapsed_time<std::chrono::milliseconds>("要素の走査(すべての要素)", start, end);

    // 要素の走査(範囲for)
    start=std::chrono::high_resolution_clock::now();
    for(const auto& sp : str_list) {
    }
    end=std::chrono::high_resolution_clock::now();
    elapsed_time<std::chrono::milliseconds>("要素の走査(範囲for)", start, end);

    // 要素の走査(最初と最後)
    start=std::chrono::high_resolution_clock::now();
    str_list.front();
    str_list.back();
    end=std::chrono::high_resolution_clock::now();
    elapsed_time<std::chrono::nanoseconds>("要素の走査(最初と最後)", start, end, "ナノ秒");

    // 要素の削除
    start=std::chrono::high_resolution_clock::now();
    for(std::size_t i=0; i<ELEMENT_COUNT; i+=10000) {
        str_list.erase(std::begin(str_list));
    }
    end=std::chrono::high_resolution_clock::now();
    elapsed_time<std::chrono::nanoseconds>("要素の削除", start, end, "ナノ秒");
}
```
```bash
# std::dequeバージョン
$ clang++ -std=c++14 -O0 -DTEST_USE_DEQUE -o deque list.cpp

# std::vectorバージョン
$ clang++ -std=c++14 -O0 -DTEST_USE_VECTOR -o vector list.cpp
```
forの再初期化式が+=になっているものはどちらかの処理が遅すぎるものです。

## 結果
### 要素の追加(push_back)
| 回数 | vector | deque |
|:---:|:---:|:-------------:|
|1|973|338|
|2|989|336|
|3|860|342|
|4|896|343|
|5|984|381|
|平均|940.4|348|

領域を大きくするときのコピー量の違いかdequeのほうが速い結果になりました。

### 要素の先頭への追加(insert)
| 回数 | vector | deque |
|:---:|:---:|:-------------:|
|1|9051|0|
|2|8994|0|
|3|8872|0|
|4|9124|0|
|5|9037|0|
|平均|9015.6|0|

先頭への追加は圧倒的にdequeのほうが速いという結果になりました。

### 要素の追加(emplace_back)
| 回数 | vector | deque |
|:---:|:---:|:-------------:|
|1|233|284|
|2|236|284|
|3|235|285|
|4|236|287|
|5|235|281|
|平均|235|284.2|

やっぱりpush_backよりは速いです。
vectorとdequeは僅差でvectorの勝利です。

### 要素の先頭への追加(emplace)
| 回数 | vector | deque |
|:---:|:---:|:-------------:|
|1|9022|0|
|2|8835|0|
|3|8923|0|
|4|8997|0|
|5|9030|0|
|平均|8961.4|0|

dequeのほうが圧倒的に速いです。
insertよりも速いという結果になりました。

### 要素の走査(すべての要素)
| 回数 | vector | deque |
|:---:|:---:|:-------------:|
|1|106|1099|
|2|106|1094|
|3|105|1093|
|4|105|1098|
|5|105|1087|
|平均|105.4|1094.2|

これはすごい差がでました。
vectorは安定して速いという感じですね。

### 要素の走査(範囲for)
| 回数 | vector | deque |
|:---:|:---:|:-------------:|
|1|95|114|
|2|95|111|
|3|95|112|
|4|95|111|
|5|96|111|
|平均|95.2|111.8|

範囲forはvectorのほうが速いという結果になりました。
これもvectorは安定して速いです。

### 要素の走査(最初と最後)
| 回数 | vector | deque |
|:---:|:---:|:-------------:|
|1|350|371|
|2|382|409|
|3|358|395|
|4|315|356|
|5|320|384|
|平均|345|383|

そんなに差がでませんでした。
一応全部vectorのほうが速いです。

### 要素の削除(先頭)
| 回数 | vector | deque |
|:---:|:---:|:-------------:|
|1|103401672961|151526|
|2|103364671055|151700|
|3|103953655253|150569|
|4|104234321618|149700|
|5|102828393379|151875|
|平均|103556542853.2|151074|

これは見てもらえば解ると思いますが、vectorで先頭の要素を何度も削除してはいけません。
この数値はナの秒単位なので、桁が大きすぎますがdequeのほうが圧倒的に速いです。

## 結論
先頭やその近くの要素の削除を頻繁に行うときはdequeを使ったほうが良さそうです。

# 環境
CPU : Intel Core i5 2500 3.30GHz
メモリ : 16GiB DDR3 1333MHz
OS : Linux Mint 18 x64