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) | 不可 |
以上、もちろん実装にもよりますが、使い分けるときの参考になれば。