在特定條件下，deque與vector的效能比較

大家好，胎嘎賀

我如果只是要存放資料，則使用vector

如果有需要放在頭，則使用deque

如果有需要在中間插入，則使用forward_list

不過讀了GotW #54之後，改變了我一些想法

這邊先講一下我對vector與deque的了解

vector的實作，就是一塊連續的記憶體空間
當空間不夠時，會跟記憶體要求一個更大的空間，並且copy or move原本的資料
優點：
1. 記憶體空間是連續的，可以很快traverse所有資料
2. 如果已經知道需要多少數量，可以使用reserve，這樣不需要再跟記憶體要求空間
3. 承上，不需要copy or move原本的資料
缺點：
1. 記憶體的使用比較嚴苛，因為需要是連續的
2. 如果不知道到時候會需要多少數量，則resize時容易造成記憶體空間的浪費（當然，
可以用shrink_to_fit試試）
3. 承上，需要copy or move原本的資料

deque的實作，應該如同這張圖一樣http://i.stack.imgur.com/dbPA6.jpg
因此，deque在增大的時候，會跟記憶體要求一個固定size的memory
優點：
1. 記憶體的使用比較不嚴苛，能更有效利用零碎的空間

2. 在增大的時候，不需要copy or move原本的資料
缺點：
2. traverse比vector慢
3. operator[]比vector慢一點點（這影響應該不大）

接下來就是要探討的問題
1. 假設只需要存放資料，且不知道會放幾筆資料，那應該是deque比vector快（deque不
需要copy or move原本的資料）
2. 假設只需要存放資料，且知道會放幾筆資料，那應該是deque比vector慢（vector不需
要跟記憶體要求空間，也不需要copy or move原本的資料）

但理論只是理論，實際上還是要跑程式才知道，因此我在這邊放上我的code

#include<chrono>
#include<deque>
#include<iostream>
#include<vector>
#include<utility>	//forward
using namespace std;
 
template<class Func,class ... Args>
chrono::milliseconds::rep calc_time(Func &&func,Args &&...args)
{
	chrono::high_resolution_clock::time_point begin{chrono::high_resolution_clock::now()};
	std::forward<Func>(func)(std::forward<Args>(args)...);
	chrono::high_resolution_clock::time_point end{chrono::high_resolution_clock::now()};
	return chrono::duration_cast<std::chrono::milliseconds>(end-begin).count();
}
 
constexpr int iteration{100000000};
const vector<int> test(100,0);
size_t de;
size_t ve;
size_t ve2;
 
void test_deque()
{
	deque<vector<int>> deq;
	for(int i{0};i!=iteration;++i)
		deq.emplace_back(test);
	de=deq.size();
}
 
void test_vector()
{
	vector<vector<int>> vec;
	for(int i{0};i!=iteration;++i)
		vec.emplace_back(test);
	ve=vec.size();
}
 
void test_vector2()
{
	vector<vector<int>> vec;
	vec.reserve(iteration);
	for(int i{0};i!=iteration;++i)
		vec.emplace_back(test);
	ve2=vec.size();
}
 
int main()
{
	cout<<calc_time(test_deque)<<endl;
	cout<<calc_time(test_vector)<<endl;
	cout<<calc_time(test_vector2)<<endl;
}

環境：
CPU: intel i7 4930k
OS: windows 7 enterprise sp1, 64 bit
Memory： 64G
Compiler: visual c++ 2015 （vc++ 14.0）
Compiler Option: release, x64, full optimization （/Ox）

輸出：
165497（deque）
331978（vector沒有reserve）
271584（vector有reserve）

回到問題1，deque的確比vector快（165497<331978），實驗數據符合預期結果

回到問題2，？？？
不對阿，我的test_vector2裡面有做reserve，test_vector2比test_vector快，這很正常
但是test_vector2不可能比test_deque慢才對啊
如果根據理論分析，vector只要使用reserve，他就不可能輸給deque才對
如果問題2的推論是正確的，那為什麼實驗數據不符合預期結果呢？

補一台
環境：
CPU: intel i7 4700HQ
OS: windows 10 1511, 64 bit
Memory： 4G
Compiler: gcc 5.2.0
Compiler Option: -std=c++14 -O3

輸出：
iteration為5000000（原本的1/20），執行5次取平均
1706
1275
1170
（皆不符合預期結果）

再補一台：
環境：
同上，除了
Compiler: visual c++ 2015 （vc++ 14.0）
Compiler Option: release, x64, full optimization （/Ox）

輸出：
iteration為5000000（原本的1/20），執行5次取平均
2814
2664
2420
（皆不符合預期結果）

難道在資料沒有很多的情況下，vector比deque快？
（可是這樣很怪，那什麼原因會造成資料很多的情況下，vector比deque慢？）

原本是覺得可能跟實作有關，可是最後那兩台的數據，都是1>2>3，真是怪了（不過VC的O
x居然比gcc的O3慢）