迭代器範圍向量構造或向量擦除是否更快？

Question

考慮其中丟棄x元件從所述前一函數的這兩種不同的實現方式：

template <typename T> 
std::vector<T> drop(int size, const std::vector<T>& coll){ 
    if (size<0) return std::vector<T>(); 
    auto sized = size > coll.size() ? coll.size() : size; 
    typename std::vector<T>::const_iterator first = coll.begin()+sized; 
    typename std::vector<T>::const_iterator last = coll.end(); 
    return std::vector<T>(first,last); 
} 

template <typename T> 
std::vector<T> drop2(int size, std::vector<T> coll){ 
    if (size<0) return std::vector<T>(); 
    auto sized = size > coll.size() ? coll.size() : size; 
    coll.erase(coll.begin(),coll.begin()+sized); 
    return coll; 
} 

在兩個版本中，一個新的std::vector被分配（在第二，它被複製作爲一個參數，它是不是一個參考）。其中一個結果由erase()創建，而另一個則使用原始向量的迭代器創建結果。

有沒有什麼理由相信其中的一個在性能上會比另一個有顯着的不同？

另外，RVO是其中之一還是兩者的保證？

編輯：

下面是測試我沒有，其示出了第一個是相當多的比第二慢：

template<typename F> 
void dropExample(F f){ 
    std::cout<<"drop example"<<std::endl; 
    auto t1 = Clock::now(); 
    for (auto x: range(100000)){ 
     f(2, range(100)); 
    } 
    auto t2 = Clock::now(); 

    std::cout << "Delta t2-t1: " 
    << std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count() 
    << " ms" << std::endl; 
} 

輸出：

dropExample(drop<int>); 
dropExample(drop2<int>); 

drop example 
Delta t2-t1: 625 ms 
drop example 
Delta t2-t1: 346 ms 

否關於我在for循環中添加了多少次迭代，數字大致是這樣的，即使對於數十秒的操作秒。

編輯2：

我已經擴充了左值的測試，所建議的意見：

主

template<typename F, typename T> 
void dropExample2(F f, T vec){ 
    std::cout<<"drop example 2"<<std::endl; 
    auto t1 = Clock::now(); 
    for (auto x: range(1000)){ 
     f(2, vec); 
    } 
    auto t2 = Clock::now(); 

    std::cout << "Delta t2-t1: " 
    << std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count() 
    << " ms" << std::endl; 
} 

然後：

int main(int argc, const char * argv[]) { 

    auto testrange=range(100000); 

    dropExample(drop<int>); 
    dropExample(drop2<int>); 

    dropExample2(drop<int>,testrange); 
    dropExample2(drop2<int>,testrange); 

    return 0; 
} 

輸出還是暗示第二快得多：

drop example 
Delta t2-t1: 564 ms 
drop example 
Delta t2-t1: 375 ms 
drop example 2 
Delta t2-t1: 2318 ms 
drop example 2 
Delta t2-t1: 698 ms 

下面是本例中使用輔助功能：

std::vector<int> range(int start, int end, int step); 

std::vector<int> range(int start, int end){ 
    if (end<start){ 
     return range(start,end,-1); 
    }else if (start == end){ 
     return std::vector<int> {start}; 
    }else{ 
     std::vector<int> nums(end-start); 
     std::iota(nums.begin(),nums.end(),start); 
     return nums;} 
} 

std::vector<int> range(int end){ 
    return range(0,end); 
} 

std::vector<int> range(int start, int end, int step){ 
    std::vector<int> nums{start}; 
    auto next=start+step; 
    while ((next<end&&start<=end&&step>0)|| 
      (next>end&&start>end&&step<0)) 
    { 
     nums.push_back(next); 
     next+=step; 
    } 
    return nums; 
} 

Answer 1

你的第二個例子將創建一大堆對象（在複製輸入參數時），以便稍後（在調用擦除時）擺脫它們。性能上的差異將取決於T是什麼，但我懷疑第一個會更慢。
由於擦除不會重新分配內存，第二個版本中使用的內存量也會更大。

編輯
您當前的測試是有缺陷的，因爲你傳遞載體將子集作爲臨時，讓編譯器移動構造輸入參數drop2，從而完全eliding副本。簡單地改變：

for (auto x: range(100000)) 
     f(200, range(10000)); 

到

auto v = range(10000); 
    for (auto x: range(100000)) 
     f(200, v); 

變卦了相當顯着的成果。然而，第二種方法對我來說還是比較快，直到載體大得多。值得注意的是，因爲您使用的是int，所以不同的方法可以針對memcpy和幾個指針操作進行最優化優化。

drop可能變成簡單的(coll.size() - size) * sizeof(int)字節的memcpy，而drop2可能成爲coll.size() * sizeof(int)字節的備忘錄。這是因爲int的析構函數是不可操作的，所以擦除調用可能簡單地從__last指針中減去size。

如果你感興趣的是這樣的原始類型，那麼沒關係，但是如果你也想有一個最佳實現，例如std::string那麼它的析構函數和複製構造函數就成爲非常重要的因素。我曾嘗試將std::vector<int>作爲向量中的類型，儘管整體速度較慢，但​​對於較小的尺寸，看起來drop2仍然更快。然而，drop在更低的閾值下變得更有效率。我非常懷疑這就是我們在這裏看到的，所以我們最終運行的代碼只是在某種程度上處於memcpy的狀態，並且是我們逐字寫的。

我到底想我們正在測試的編譯器優化不同功能的能力（std::uninitialized_copy，std::move（迭代器爲基礎的一個），呼籲在一個循環get_allocator().destroy(p)瑣碎和不平凡的類型，等等）。我現在所能說的就是結果可以在優化的方面以及在代碼中看起來很小的變化的情況下變化很大。

但是，我仍然對drop2的運行速度比drop的運行速度還要驚訝，即使只適用於某個尺寸以下的範圍。

Answer 2

真的，答案就在這兩個版本的一個廣泛的基準。但是，作出評估時，我傾向於認爲第一個版本會更快，因爲在一般情況下，您必須將較少的元素從初始向量複製到輸出向量，而不是在第二個你複製他們全部。

Answer 3

第一個幾乎肯定會更快，除非你給drop一個右值，在這種情況下，你必須測量。

假設有N個元素入手，和M元素砸：

• 頭份N-M的元素;第二個拷貝N個元素。
• 第一個不執行任務;第二個執行N-M個移動分配，這可能退化以複製分配。
• 第一個可能，並在實踐中，RVO。第二個需要一個無法消除的舉措。然而，移動向量足夠便宜，額外成本可能最小。