list（2）

sequential access

listにランダムアクセスはできないので、
これの速度を調べる。

const int   m = 1000;           // コンテナの大きさ

const int   n = (int)(1e10 / m);    // 繰り返し回数
void procVector() {

    vector v;

    for(int k = 0; k < m; k++)

        v.push_back(k);

    

    int     sum = 0;

    typedef vector::const_iterator CIT;

    for(int i = 0; i < n; i++) {

        for(CIT p = v.begin(); p != v.end(); ++p)

            sum += *p;

    }

    

    cerr << sum << endl;

}
void procList() {

    list   l;

    for(int k = 0; k < m; k++)

        l.push_back(k);

    

    int     sum = 0;

    typedef list::const_iterator   CIT;

    for(int i = 0; i < n; i++) {

        for(CIT p = l.begin(); p != l.end(); ++p)

            sum += *p;

    }

    

    cerr << sum << endl;

}

2桁多く繰り返して、ひたすら足す。
オーバーフローは気にしない。
これで、
vector : 6.645s、list : 36.436s
とにかくvectorのほうが圧倒的に速い。
ところで、単純な足し算と比べてみると、

void pureSum() {

    int     sum = 0;

    for(int i = 0; i < n; i++) {

        for(int k = 0; k < m; k++)

            sum += k;

    }

    

    cerr << sum << endl;

}

これで、6.942s
と何回やってもこちらのほうがvectorより遅くなる。
どういう仕組みになっているのだろう。