將元素隨機插入向量時隨機放緩

Question

編輯： 我已修復插入。正如Blastfurnace所提到的，插入操作會使迭代器失效。我認爲需要循環來比較性能（請參閱我對Blastfurnance的回答的評論）。我的代碼已更新。對於列表，只有列表被向量替換時，我有完全相似的代碼。但是，通過代碼我發現，對於小數據類型和大數據類型，甚至對於線性搜索（如果刪除插入），列表的性能都優於矢量。根據http://java.dzone.com/articles/c-benchmark-%E2%80%93-stdvector-vs和其他網站，應該不是這種情況。任何線索如何可以？

我正在上數學軟件（星期一考試）的編程課程，爲此我想提出一個圖表，比較元素隨機插入矢量和列表之間的表現。但是，當我測試代碼時，我會隨機放慢速度。例如，我可能有2次迭代，將10個元素隨機插入一個大小爲500的向量需要0.01秒，然後進行3次類似的迭代，每次迭代需要大約12秒。這是我的代碼：

void AddRandomPlaceVector(vector<FillSize> &myContainer, int place) { 
    int i = 0; 

    vector<FillSize>::iterator iter = myContainer.begin(); 

    while (iter != myContainer.end()) 
    { 
     if (i == place) 
     { 
      FillSize myFill; 
      iter = myContainer.insert(iter, myFill); 
     } 
     else 
      ++iter; 

     ++i; 
    } 

    //cout << i << endl; 
} 

double testVector(int containerSize, int iterRand) 
{ 
    cout << endl; 
    cout << "Size: " << containerSize << endl << "Random inserts: " << iterRand << endl; 

    vector<FillSize> myContainer(containerSize); 
    boost::timer::auto_cpu_timer tid; 

    for (int i = 0; i != iterRand; i++) 
    { 
     double randNumber = (int)(myContainer.size()*((double)rand()/RAND_MAX)); 
     AddRandomPlaceVector(myContainer, randNumber); 
    } 

    double wallTime = tid.elapsed().wall/1e9; 

    cout << "New size: " << myContainer.size(); 

    return wallTime; 
} 

int main() 
{ 
    int testSize = 500; 
    int measurementIters = 20; 
    int numRand = 1000; 
    int repetionIters = 100; 


    ofstream tidOutput1_sum("VectorTid_8bit_sum.txt"); 
    ofstream tidOutput2_sum("ListTid_8bit_sum.txt"); 

    for (int i = 0; i != measurementIters; i++) 
    { 
     double time = 0; 

     for (int j = 0; j != repetionIters; j++) { 
      time += testVector((i+1)*testSize, numRand); 
     } 

     std::ostringstream strs; 
     strs << double(time/repetionIters); 
     tidOutput1_sum << ((i+1)*testSize) << "," << strs.str() << endl; 
    } 

    for (int i = 0; i != measurementIters; i++) 
    { 
     double time = 0; 

     for (int j = 0; j != repetionIters; j++) { 
      time += testList((i+1)*testSize, numRand); 
     } 

     std::ostringstream strs; 
     strs << double(time/repetionIters); 
     tidOutput2_sum << ((i+1)*testSize) << "," << strs.str() << endl; 
    } 
    return 0; 
} 

struct FillSize 
{ 
    double fill1; 
}; 

該結構只是爲了方便地添加更多值，以便我可以測試不同大小的元素。我知道這個代碼在性能測試方面可能並不完美，但他們寧願讓我舉一個簡單的例子，而不是簡單地參考我發現的東西。

我已經在兩臺電腦上測試了這段代碼，兩者都有相同的問題。怎麼可能？你能幫我解決問題嗎？我可以在星期一畫出它並呈現它嗎？也許在每次迭代之間增加幾秒鐘的等待時間會有所幫助？

親切的問候， Bjarke

Answer 1

你AddRandomPlaceVector功能有嚴重缺陷。使用insert()將invalidate iterators所以for循環是無效的代碼。

如果您知道所需的插入點，則沒有理由重複遍歷vector。

void AddRandomPlaceVector(vector<FillSize> &myContainer, int place) 
{ 
    FillSize myFill; 
    myContainer.insert(myContainer.begin() + place, myFill); 
}