list（1）

仕事でlistを使っているところがあって、
こんなところでなにもわざわざlistを使わなくてもと思っていたが、
最近全部vectorにしたら、想像以上に速くなった。

listはどういうときに使えるか考えてみる。
以下のベンチマークは、
VC2003＋Windows XPで行っている。

push_back

末尾に追加する。
これはさすがにvectorが速い。

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

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

void procList();

bool del_rand(int a);
void main(void) {

    timeBeginPeriod(1);

    

    int     t0 = timeGetTime();

#if 0

    procVector();

#else

    procList();

#endif

    int     t1 = timeGetTime();

    cerr << (t1 - t0) / 1000.0 << "s" << endl;

    

    timeEndPeriod(1);

}
void procVector() {

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

        vector v;

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

            v.push_back(k);

    }

}
void procList() {

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

        list   l;

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

            l.push_back(k);

    }

}

これで、vectorなら1.083s、listなら31.161s。
たぶんほとんど領域確保の時間である。
こんなときにlistを使ってはいけない。

挿入

vectorというのは、一列に真っ直ぐ並んでいるようなものである。
並んだ列の途中に誰かが入ろうとすると、
後ろから順に一人分ずつ下がらないといけない。

一方、listというのはどう並んでいてもいい。
手さえつながっていればいい。
途中に入るにはそこだけ手をつなぎなおせばいいだけである。

だから挿入を多く使うときはvectorよりlistを使うのがよい。

というのは、誰でも思うことだが、
実際はどうだろう。
常に頭に挿入するよう、
こんなコードでベンチマークしてみた。

void procVector() {

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

        vector v;

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

            v.insert(v.begin(), k);

    }

}
void procList() {

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

        list   l;

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

            l.push_front(k);

    }

}

これでかかった秒数は、

m	2	10	100	1000
vector	36.143	25.298	20.719	59.041
list	49.320	36.061	31.393	29.819

実際には、
vectorのほうはあらかじめ領域確保してあるのがふつうなので、
こうすると、

void procVector() {

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

        vector v;

        v.reserve(m);

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

            v.insert(v.begin(), k);

    }

}

m	2	10	100	1000
vector(reserve)	20.854	9.895	16.959	57.650
list	49.320	36.061	31.393	29.819

m=400程度でvectorとlistが同等だろうか。
実際には平均して真ん中に挿入とすると、
m=800程度で同等、
すなわち、おおざっぱに言って、
コンテナの大きさが1000程度にならないと、
listのvectorに対するアドバンテージは見えてこないということである。