連接兩個std :: vector - 哪種方法更高效，以及如何/爲什麼？

考慮以下情形：連接兩個std :: vector - 哪種方法更高效，以及如何/爲什麼？

std::vector<int> A; 
std::vector<int> B; 
std::vector<int> AB;

我想AB擁有的A內容，然後B以相同的順序內容。

方法1：

AB.reserve(A.size() + B.size()); // preallocate memory 
AB.insert(AB.end(), A.begin(), A.end()); 
AB.insert(AB.end(), B.begin(), B.end());

方法2：

std::vector<int> AB (A.begin(), A.end()); // calling constructor 
AB.insert (AB.end(), B.begin(), B.end());

哪個的上述方法之一是更有效率？爲什麼？有沒有更高效的不同方法？

來源

2014-10-09 CinCout

您是否嘗試過測量它？ – 2014-10-09 09:22:17

這很大程度上取決於這兩個向量的大小以及向量分配器算法的實現 – EdChum 2014-10-09 09:22:22

不確定您是否檢查過，但請記住，性能是您一旦確定它是_problem的唯一問題。除非你的矢量是巨大的，或者它們中的項目構造/複製成本高昂，你不會注意到很大的區別。不要花大量的時間將0.2ms的操作減少到0.1ms，除非你需要每秒處理數千次:-) – paxdiablo 2014-10-09 09:25:21

我認爲第一個會比第二個快，因爲它只執行一次內存分配，第二個可能不得不重新分配至少一次。但my measurements似乎表明，對於尺寸小於約100,000，這是更快：

我猜這是因爲，這不僅只執行一次分配和再分配沒有，它甚至不需要檢查它是否應該做任何重新分配。缺點是它可能必須初始化所有的內存，但我認爲CPU是擅長的。

來源

2014-10-09 12:22:24

*缺點是它必須將所有內存清零* - 我看着生成的程序集，我無法解釋這麼大的差異，但是什麼是顯而易見的是優化器將內存清零。第一個和你的風格基本生成的代碼是相同的，但代碼的結構略有不同，它看起來像優化器更好地準備處理這最後一個選項... – 2014-10-10 22:42:03

@DavidRodríguez-dribeas有趣。這並不是我第一次感到驚訝，與「保留內存和插入」方法相比，「內存覆蓋和覆蓋」方法有多好。 E.g'std :: vector A（size）; for（size_t i = 0; i！= size; ++ i）A [i] = func（i）;'[出人意料地表現出色]（http://coliru.stacked-crooked.com/a/deef69909146f580）。也許你是對的，原因是優化器將內存清零。 – 2014-10-11 06:28:43

第一個可能更高效一點，因爲您可以保證只執行一次內存分配。在第二種情況下，很可能（大多數實現方式）在向量構建期間將分配A.size()，然後insert將觸發第二次分配，因爲它需要增長B.size()個元素。

來源

2014-10-09 09:23:27

方法1執行否重新分配，而方法2可能重新分配多次，並且實際上很可能重新分配一次。所以方法1更好。

來源

2014-10-09 09:24:59

正在插入的迭代器範圍使用RandomAccessIterators，因此插入的元素數量可以計算在O（1）中，因此在方法2中不能再重新分配一次。 – 2014-10-09 09:26:21

@JonathanWakely：實際上是保證，還是隻是一個共同的實現？（我知道範圍構造函數有一個實際的保證。） – 2014-10-09 09:28:25

@KerrekSB：即使標準不能保證它會被認爲是一個bug，但它是其中的一個。 – 2014-10-09 09:30:22

連接兩個std :: vector - 哪種方法更高效，以及如何/爲什麼？

回答

相關問題