[問題] 在特定條件下，deque與vector的效能比較
我已經知道原因了，詳情我會發在另一篇
開發平台(Platform): (Ex: VC++, GCC, Linux, ...)
vc++ 14.0
問題(Question)：
原本我都是信奉，如果只是要存放資料，則使用vector
如果有需要放在頭，則使用deque
如果有需要在中間插入，則使用forward_list
不過讀了GotW #54之後，改變了我一些想法
這邊先講一下我對vector與deque的了解
vector的實作，就是一塊連續的記憶體空間
當空間不夠時，會跟記憶體要求一個更大的空間，並且copy or move原本的資料
優點：
1. 記憶體空間是連續的，可以很快traverse所有資料
2. 如果已經知道需要多少數量，可以使用reserve，這樣不需要再跟記憶體要求空間
3. 承上，不需要copy or move原本的資料
缺點：
1. 記憶體的使用比較嚴苛，因為需要是連續的
2. 如果不知道到時候會需要多少數量，則resize時容易造成記憶體空間的浪費（當然，
可?
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不
需?
2. 假設只需要存放資料，且知道會放幾筆資料，那應該是deque比vector慢（vector不需
要
但理論只是理論，實際上還是要跑程式才知道，因此我在這邊放上我的code
http://ideone.com/LqQbqW
環境：
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?
code分析：vector的emplace_back（與push_back）的增大
VC++ 14.0：
max(capacity()*1.5,capacity()+1)
gcc 5.2.0：
capacity()+max(capacity(),1)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.161.61.190
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1456907774.A.C67.html
推
03/02 17:20, , 1F
03/02 17:20, 1F
→
03/02 17:20, , 2F
03/02 17:20, 2F
感謝幫忙
能請教一下你的編譯器、編譯參數、環境嗎？ 謝謝
推
03/02 21:15, , 3F
03/02 21:15, 3F
→
03/02 21:15, , 4F
03/02 21:15, 4F
推
03/02 21:20, , 5F
03/02 21:20, 5F
恩...，我是想說測多一點比較準，所以才弄那麼高
推
03/02 23:03, , 6F
03/02 23:03, 6F
推
03/02 23:57, , 7F
03/02 23:57, 7F
→
03/02 23:58, , 8F
03/02 23:58, 8F
→
03/03 00:00, , 9F
03/03 00:00, 9F
→
03/03 00:01, , 10F
03/03 00:01, 10F
→
03/03 00:06, , 11F
03/03 00:06, 11F
→
03/03 00:12, , 12F
03/03 00:12, 12F
感謝各位提供數據
→
03/03 09:21, , 13F
03/03 09:21, 13F
→
03/03 09:21, , 14F
03/03 09:21, 14F
→
03/03 09:22, , 15F
03/03 09:22, 15F
好，那我再研究看看deque內部好了
推
03/03 13:56, , 16F
03/03 13:56, 16F
effective c++我有整本讀完，exceptional c++我是跳著看的 XD
不過effective modern c++很讚，雖然大部分都已經懂了
推
03/03 14:41, , 17F
03/03 14:41, 17F
→
03/03 14:42, , 18F
03/03 14:42, 18F
我之前很無聊的把GotW全部看一遍，首先是放在這網站的
http://herbsutter.com/gotw/
這是新的，建議都看
如果是舊的，建議只看
GotW #54: Using Vector and Deque
GotW #56: Exception-Safe Function Calls
還有這篇文章
http://www.gotw.ca/publications/mill18.htm
其他的GotW，我覺得比較沒那麼重要
exceptional c++不太合我口味，但pimpl一定要看
推
03/03 16:29, , 19F
03/03 16:29, 19F
→
03/03 16:30, , 20F
03/03 16:30, 20F
→
03/03 16:31, , 21F
03/03 16:31, 21F
swap不會產生第三點問題，但仍然會有第二點問題
因為swap只是把內部的begin, end（記憶體最後一個）, last（現在的最後一個）交換，
因此若另一個vector有使用過多的記憶體，swap後，記憶體使用量仍然不變
※ 編輯: Caesar08 (223.136.12.0), 03/05/2016 11:27:37
討論串 (同標題文章)