C++ push_back vs插入vs emplace

我目前正在製作一個使用C++向量的應用程序。C++ push_back vs插入vs emplace

我知道預優化是如何成爲萬惡的根源。

但我真的不禁好奇。

我將其他矢量的部分添加到另一個矢量中。
我們會說的載體將有一個大小永遠的300

變化由於我一直追加到矢量

的到底是快做：
a.reserve(300);
a.insert(a.end(), b.begin(), b.end());

或者是否會更快地循環遍歷我想追加的矢量，並分別在push_back或emplace之間單獨添加每個項目（雖然仍在預先保留）。（不確定哪個更快）

任何人都可以幫助我嗎？

來源

2013-02-21 Darkalfx

「有效STL」第5項：不想區間成員函數自己的單元素 – Cubbi 2013-02-21 18:19:57

去爲更清晰的代碼，用什麼STL爲您提供...不重複，除非你要。在大多數情況下重用代碼將勝過這種簡單操作的手工定製版本。這些功能在設計時考慮到了效率。 – eazar001 2013-02-21 18:22:32

'insert'可能更快，或者它可能差不多，但是（缺少一個不好的庫實現）將永遠不會比循環更糟糕。 – 2013-02-21 18:23:06

這裏有一個基本原則：當庫提供兩種do_x_once和do_x_in_batch，則後者至少應儘可能快地在一個簡單的循環中調用do_x_once。如果不是這樣，那麼這個庫很難實現，因爲一個簡單的循環足以獲得更快的版本。通常，這樣的批次函數/方法可以執行額外的優化，因爲他們具有數據結構內部的知識。

所以，insert應至少快在一個循環push_back。在這種情況下，智能實現insert可以爲您想要插入的所有元素執行單個reserve。 push_back每次都必須檢查向量的容量。不要試圖智取圖書館:)

來源

2013-02-21 18:31:00

這確實對我有幫助。我對C++比較陌生。對於我想插入的所有元素，單個保留是什麼意思？想你可以給我更多的細節？ – Darkalfx 2013-02-21 19:13:18

@Darkalfx：對於某些類型的迭代器，'insert'可以使用'b.begin（） - b.end（）'計算要插入的元素的數量。當它知道元素的數量時，它可以在矢量中爲一個操作中的那個數字創建空間。 – 2013-02-21 19:30:11

正如larsmans所說，你在單個圖書館電話中做得越多，更有可能更有效率。在insert, 的情況下，該庫通常至多會執行一次單獨的重新分配，並且最多複製每個移位的元素一次。如果您使用循環和push_back，它可能會重新分配幾次次，這可能會顯着較慢（如大小爲的次序）。

根據不同的類型，但是，它也可能會更快做類似：

a.resize(300); 
std::copy(b.begin(), b.end(), a.end() - 300);

我發現這是更快簡單標量類型（如 int）使用G ++上英特爾機器。

來源

2013-02-21 18:40:26

作爲一個方面說明：'resize'不應該循環爲'push_back'（甚至一個功能，這是一個循環內內）內部調用（我假設'insert'）需要攤銷固定的時間（指數增長步）而保守的「調整大小」打破了這一點。 – BCS 2013-09-26 23:00:10

@BCS'resize'通常會在循環之前調用，而不是在循環中調用。這裏的問題是'resize' +'[]'vs.'reserve' +'push_back'。 – 2013-09-27 08:32:22

我想這確實取決於編譯器（庫實現），編譯選項和體系結構。英特爾®至強®在VS2005做一個快速的基準，而不優化（/ OD）：

std::vector<int> a; 
std::vector<int> b; 

// fill 'a' with random values for giggles 

timer.start() 
// copy values from 'a' to 'b' 
timer.stop()

我得到這些結果使用「複製值的這些不同的方法10 000 000項...「：

爲 'B' 預留空間，然後循環使用b.push_back(a[i]);：0.808秒
調整大小 'B'，然後循環利用指標分配b[i] = a[i];：0.264秒
沒有大小調整'b'，只是b.insert(b.end(), a.begin(), a.end());：0.021秒（與儲備第一無顯著差異）
std::copy(a.begin(), a.end(), std::back_inserter(b));：0.944秒（0.871與儲備第一）
調整尺寸 'b'，然後MEMCOPY在基指針memcpy(&(b[0]), &(a[0]), 10000000*sizeof(int));：0.061秒

隨着優化開啓（/ OX），然而，這是一個不同的故事。我不得不增加尺寸爲100 000 000，以獲得更多的分化：

的push_back循環：0.659秒
指數環：0.482秒
插入：0.210秒（與儲備第一無顯著差異）
標準::複製：0.422秒，預留第一。沒有它就得到了bad_alloc。
的memcpy：0.329秒

什麼有趣的是，有或沒有優化，插入方法線性縮放。其他方法在沒有優化的情況下明顯效率低下，但仍然無法與它們一樣快。正如James Kanze指出的那樣，它在g ++上有所不同。用自己的平臺運行測試來驗證。

來源

2013-03-22 14:56:23 OlivierD

C++ push_back vs插入vs emplace

回答

相關問題