基本 その２『ListとVectorの違い』
その２では『ListとVectorの違い』についてです。
この二つは同じ様に使われていますが、
使用用途を間違えると無駄な処理が発生する事が有ります。
vectorは使ってるけどlistは使ってないって方もいらっしゃるのでは？
自分自身vector有ればよくね？とか考えてました。
しかし、仕組みを知ると愚かさに気づきます。
まずすごく簡単なＬｉｓｔの使用例
#include
#include
#include
int main()
{
std::list
list_val.push_back(10);
list_val.push_back(20);
for each(int val in list_val)
std::cout << val << std::endl;
return 0;
}
出力：
10
20
本当にvectorとlistってかき方似てるなぁ…。
さて、有用な使い方のお話です。
単純にvectorとlistの違いはアクセス方法に有ります。
vectorは配列要素番号（インデックス）を保持して配列の中身の管理を行っています。
それに対し、listはアドレスのリンクによって配列の中身を管理します。
判りましたか？
つまり
vector
りんご_1 みかん_2 もも_3 ぶどう_4
インデックスが振られていきます。
list
りんご → みかん → もも → ぶどう
アドレスのリンクによって管理されます。
この二つは得意不得意が有ります。
例えば、削除や挿入を繰り返す時はどちらの構造がいいと思いますか？
正解はlistです。
その理由は以下の通り
りんご → みかん → もも → ぶどう
↑削除する
りんご → ↓ みかん → もも → ぶどう
→ → ↑
参照先のアドレスを変更するだけなので、速度が速い
しかし、このリストには弱点があり、ランダムアクセスを行った場合速度が
vectorより落ちる事が有ります。
理由はわかりますか？
インデックスで管理していないため、参照を行う場合
必ず最初のリストからみていかなければいけないのです。
ぶどうをアクセスしたくてもりんごから見ないといけないという事です。
ちなみに、配列要素を最初から連続でみていく場合、
例えば、シューティングとかの弾の当たり判定とか
その時は、速度は落ちません。
だいたい今の流れで分かったと思いますが、
vectorの場合はインデックスで管理しているので
参照を行う場合、１番目にアクセスしようが、１０００００番目にアクセスしようが
掛かる時間は一定です。
しかし、インデックスで管理している故に挿入削除は時間がかかってしまうのです。
りんご_1 みかん_2 もも_3 ぶどう_4
↑削除
りんご_1 もも_3 ぶどう_4
りんご_1 もも_2 ぶどう_3
インデックスの番号を全て書き換える為時間がかかっちゃう訳です。
その２しゅうりょうです。
お疲れ様でした。
