c++ list と vector

C++のSTLにはlistとvectorなどとよく似たコンテナ型がありますが、 何が違うのか？どう使い分けるか？

と、気になりましたので少し試してみました。

実行環境は、

• OS: Windows 8.1　(64bit)
• CPU: Core 2 Quad Q9550 2.83GHz
• コンパイラ: Visual Studio 2013のVC

まずは要素追加の関数push_backから。 このようなコードで追加個数(N)を変えながら試してみました。

#include <iostream>
#include <list>
#include <vector>
#include <ctime>

int main()
{
    const int N = 40000000;
    std::list<int>  l;
    std::vector<int> v;

    clock_t s, e;
    s = clock();
    for ( int i=0; i<N; i++ ) {
        l.push_back(0);
    }
    e = clock();
    std::cout << "clock=" << (e-s) << "[tick]" << std::endl;

    s = clock();
    for ( int i=0; i<N; i++ ) {
        v.push_back(0);
    }
    e = clock();
    std::cout << "clock=" << (e-s) << "[tick]" << std::endl;

    return 0;
}

結果、

	N=10000000	N=20000000	N=40000000
vector	109	266	422
list	847	1672	3375

のように、およそ比例しているようです。 要素の追加は要素数にかかわらず定数時間(o(1))で行います。

リストの先頭への要素追加push_frontについては、vector型は不可能で、 list型はやはり定数時間で行います。

ランダムアクセスはlist型は不可能で、vector型はやはり定数時間で行います。

ここまでをまとめると、

	push_back	push_front	ランダムアクセス
vector	o(1)	不可	o(1)
list	o(1)	o(1)	不可

以上、もちろん実装にもよりますが、使い分けるときの参考になれば。