将元素随机插入向量时随机放缓

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); 
}