1
我對我的代碼性能測試std::vector和std::list的性能感到困惑。當涉及到find_if和max_element時，這兩者之間是否有區別？std :: vector和std :: list find_if和max_element性能
A
回答
7
就big-O符號而言，它們都具有相同的O（n）性能。 （find_if可以少如果元件越早發現，但這是兩個容器也同樣如此。）
在實際掛鐘時間而言，載體將由於高速緩存一致性更好的表現;所有向量元素在內存中都是順序的，因此訪問它們將更好地利用CPU緩存。鏈接列表的元素可以散佈在整個內存中，並且您還需要遵循需要時間的列表鏈接。
4
兩種算法都在計算複雜性方面爲O（n），但在矢量存儲的連續區域，分配其元件，其將最有可能導致更高的高速緩存命中率。遍歷一個列表，在另一方面，涉及到這是更有可能導致更高的速度高速緩存未命中的分散存儲訪問模式。
與往常一樣，當涉及到性能，反正，做決策之前進行測量。
0
對於max_element，列表和數組的所有元素都將被遍歷。所以，在性能方面都是O（n）。
再次爲了find_if，遍歷將是線性（O（N））兩者的數據結構。
我不認爲應該沒有太大相對於每一個常數分開的差別。
相關問題
- 1. std :: list vs std :: vector迭代
- 2. std :: vector與std :: list與std :: slist的相對性能？
- 3. boost :: variant和std :: find_if
- 4. std :: vector vs std :: list用於插入頻率和動態大小
- 5. 容器數據結構類似於std :: vector和std :: list
- 6. boost :: python：python list to std :: vector
- 7. 徵和std :: vector的
- 8. unique_ptr push_back和std :: list
- 9. std :: set和std :: vector有什麼區別？
- 10. C++ std :: map和std :: vector的優點？
- 11. 的std :: vector和std ::分鐘行爲
- 12. std :: vector <std :: vector <T>> vs std :: vector <T*>
- 13. std :: vector vs std :: insert
- 14. 內存管理與std :: list和std :: shared_ptr
- 15. std :: list和std :: map的常用算法？
- 16. 常量莢和std :: vector的
- 17. std :: vector和winapi窗口
- 18. OpenMP和減少std :: vector？
- 19. 如何編寫接受std :: vector或std :: list的函數？
- 20. 不能刪除std :: vector＆std :: array？
- 21. std :: bad_alloc錯誤與std :: vector
- 22. std ::在std :: string和std :: vector之間移動<unsigned char>
- 23. 使用std :: vector <T*> :: push_back與std :: mem_fun和std :: bind1st
- 24. 使用std :: find_if用的std :: string
- 25. iterate std :: vector <std :: vector <char>>？
- 26. 是std :: unique_ptr移入std :: vector
- 27. boost :: interprocess - std :: string與std :: vector
- 28. 我怎樣才能使std :: find_if和std :: map一起使用一些boost庫？
- 29. emplace_back on std :: vector
- 30. 使用迭代器從std :: list初始化std :: vector
[Bjarne Stroustrup：C++ 11 Style]（http://channel9.msdn.com/Events/GoingNative/GoingNative-2012/Keynote-Bjarne-Stroustrup-Cpp11-Style） - 從幻燈片43開始。 – Naszta