C++ 迭代器比索引慢得多？

Question

我有一个O(N^2) 程序，我注意到使用迭代器和索引之间的巨大差异，我将代码和数据粘贴在这里:

代码:

#include <string>
#include <cstdio>
#include <fstream>
#include <iostream> 
#include <sstream>
#include <vector>

using namespace std; 

int main(int argc, char* argv[]){
    ifstream ifile("csv.csv"); 
    string s; 

    vector<long> vec_frd;
    vector<long> vec_real_frd;

    while (getline(ifile, s)){
        string s2 = s.substr(0, s.find(','));
        vec_frd.push_back(stol(s.substr(0, s.find(',')))); 
    }    
    long real_frd;

    // using iterator 
    vector<long>::iterator it1, it2;
    for (it1=vec_frd.begin(); it1<vec_frd.end(); it1++){
        if (*it1 == -1){
            vec_real_frd.push_back(-1);
            continue; 
        }
        real_frd = *it1; 
        for (it2=it1; it2<it1+*it1 && it2<vec_frd.end(); it2++){
            if (*it2 == -1)
                real_frd --;
        }
        vec_real_frd.push_back(real_frd);
    }

    // using index 
    // for (unsigned int i=0; i<vec_frd.size(); i++){
    //     if (vec_frd[i] == -1){
    //         vec_real_frd.push_back(-1);
    //         continue; 
    //     }
    //     real_frd = vec_frd[i]; 
    //     for (unsigned int j=i; j<i+vec_frd[i] && j<vec_frd.size(); j++){
    //         if (vec_frd[j] == -1)
    //             real_frd --;
    //     }
    //     vec_real_frd.push_back(real_frd);
    // }        

    ifile.close();
    return 1; 
}

数据: https://www.dropbox.com/s/c2c7txhu24xy06r/csv.csv?dl=0

如果我们使用迭代器，在我的机器上需要将近 30 秒，如果我们改用索引，则需要 5 秒，我是 C++ 新手，这种性能差异是否正常？还是我哪里错了？

Answer 1

回答你的问题 - 不，这种行为对于优化代码来说绝对是不正常的。
我无法用 gcc 或 MSVC 重现它。我认为你最好的选择是仔细检查你的编译器选项。

附带说明一下，我相信您可以通过一些算法调整来大大加快此任务的速度。即使是渐进的，我也很确定你可以通过预先计算几个计数器从 O(N^2) 到 O(N)。