リスト構造とは「自己参照構造体」とも呼ばれ、構造体のメンバとして自身の構造体のポインタ変数を持っています。
イメージとしては↓のような感じです。
struct Shot {
int x;
int y;
Shot *pNext;
};
|
このデータ構造はこれまでの配列のイメージとは全く異なる考え方で作られています。
分かりづらいかも知れませんが、図にしてみます。
番地などは適当に設定しています。
最初のデータ
番地 00285F3A
+--------+
x | 10 |
+--------+
y | 5 |
+--------+
pNext |002849DC|
+--------+
次のデータ
番地 002849DC
+--------+
x | 25 |
+--------+
y | 18 |
+--------+
pNext |0028824E|
+--------+
最後のデータ
番地 0028824E
+--------+
x | 25 |
+--------+
y | 18 |
+--------+
pNext | NULL |
+--------+
構造体の中のポインタ変数に次のデータのアドレスが入っているのです。
最後のデータは次のデータが無いのでポインタ変数にNULLを入れています。（があくまでもイメージです）
配列のように連続した領域にデータが入っているのでは無く、ポインタ変数に入っているアドレスでつながっています。
なぜこのような形になっているかと言うと、途中のデータの挿入や削除を素早く出来るように考えてあるからです。
例えば、上の図の２番目のデータを削除しようとすると↓のようになります。
最初のデータのポインタ変数の中身を最後のデータの番地に変更する。
最初のデータ
番地 00285F3A
+--------+
x | 10 |
+--------+
y | 5 |
+--------+
pNext |0028824E|
+--------+
次のデータ
番地 002849DC
+--------+
x | 25 |
+--------+
y | 18 |
+--------+
pNext |0028824E|
+--------+
最後のデータ
番地 0028824E
+--------+
x | 25 |
+--------+
y | 18 |
+--------+
pNext | NULL |
+--------+
データはポインタでつながっていますので、こうするだけで２番目のデータは飛ばされてしまいます。
配列ベースのデータ構造ではこのように簡単には途中のデータを削除出来ません。
配列を使って、途中のデータを削除することを考えてみます。
０ １ ２ ３ ４
+--+--+--+--+--+
data |５|７|３|９|１|
+--+--+--+--+--+
↑
このデータを削除したい！
１．添え字３のデータを添え字２へコピーする
０ １ ２ ３ ４
+--+--+--+--+--+
data |５|７|９|９|１|
+--+--+--+--+--+
２．添え字４のデータを添え字３へコピーする
０ １ ２ ３ ４
+--+--+--+--+--+
data |５|７|９|１|１|
+--+--+--+--+--+
３．確保した領域を４つに減少させる
０ １ ２ ３
+--+--+--+--+
data |５|７|９|１|
+--+--+--+--+
単純に削除するのでは無く、データを「寄せる」事が必要になるのです。
※実際にはもう少し工夫があるのですが、ここでは説明しません。
前回のベクタもデータの途中に挿入したり削除したりする事は不向きです。
頻繁にデータの挿入や削除がある場合、リスト構造の方が向いています。
リストの特徴を書きます。
・配列ベースでは無いデータ構造 （添え字でのアクセスは不可） ・データの挿入や削除が得意 ・ランダムアクセスは苦手 （先頭からデータを辿らなければならない） |
ゲームにおいては、シューティングの弾の管理などに向いていると思います。
では実際に作ってみましょう。
リストの宣言方法から書いていきます。
<sample program cpp016-01>
#include <iostream>
#include <list>
int main()
{
std::list<int> lstData;
return 0;
}
|
ヘッダファイルとして「list」をインクルードします。
基本はベクタと同じです。
ベクタと同じくデータを追加してみたいと思いますが、単純なデータの追加は２つの関数で行えます。
１つはpush_back関数、ベクタでも使いました。
もう１つはpush_front関数、リストの先頭にデータを追加出来ます。
早速両方使ってみましょう。
<sample program cpp016-02>
#include <iostream>
#include <list>
int main()
{
std::list<int> lstData;
lstData.push_back(3);
lstData.push_front(5);
return 0;
}
|
これでデータの追加が出来ました。
イメージ的には「５」→「３」の順番でリストにデータが入っています。
イメージを図にしてみます。
番地や変数名などは適当に設定しています。
最初のデータを追加した状態
番地 00285F3A
+--------+
data | 3 |
+--------+
pNext | NULL|
+--------+
次のデータを先頭に追加した状態
番地 002849DC
+--------+
data | 5 |
+--------+
pNext |00285F3A|
+--------+
番地 00285F3A
+--------+
data | 3 |
+--------+
pNext | NULL|
+--------+
ただ、配列ベースのデータ構造では無いため、添え字を使って中身を確認することが出来ません。
そこで「イテレータ」の出番になります。
イテレータとは、各種データ構造を使用する際に「共通したアクセス方法を提供する」仕組みです。
※実際の中身はポインタ変数です。
とりあえず、今回のリストの中身を全て辿って表示してみます。
<sample program cpp016-03>
#include <iostream>
#include <list>
int main()
{
std::list<int> lstData;
lstData.push_back(3);
lstData.push_front(5);
std::list<int>::iterator it;
for (it = lstData.begin(); it != lstData.end(); it++) {
std::cout << *it << std::endl;
}
return 0;
}
|
<実行結果>
5 3 続行するには何かキーを押してください・・・
イテレータは「型」です。
このリストのイテレータは、itという名前で宣言されています。
std::list<int>::iterator it; |
データの型（今回はint型）によって実際の動きが変わります。
が、プログラマは気にしなくて良いです。
データの型に合わせたイテレータを宣言すれば良いだけです。
for文の初期値として、
it = lstData.begin(); |
begin関数の戻り値を使っています。
これで最初のデータの番地を受け取ります。
次に繰り返し条件として、
it != lstData.end(); |
と書いてあります。
end関数は「最後のデータの次のデータの番地」を指しています。
最後のデータの次のデータの番地と等しくなった場合ループを終えます。
増分にあたるところは、
it++ |
と書いてあります。
これは「次のデータに移動する」という意味で、どのようなデータ構造でも次のデータに移動します。
std::cout << *it << std::endl; |
イテレータは「ポインタ変数」なので、中身にアクセスするには「＊演算子」を使います。
もちろん、データが構造体の場合は「->演算子」を使います。
イテレータは「共通したアクセス方法を提供する」仕組みと書きました。
ベクタでも同様にイテレータは使えますので、サンプルを書いてみます。
<sample program cpp016-04>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> vecData;
vecData.push_back(4);
vecData.push_back(2);
vecData.push_back(8);
std::vector<int>::iterator it;
for (it = vecData.begin(); it != vecData.end(); it++) {
std::cout << *it << std::endl;
}
}
|
<実行結果>
4 2 8 続行するには何かキーを押してください・・・
イテレータを使えば、「signedとunsignedの比較」の問題も防げますね。
次回はリスト構造の特性を生かしたプログラムを作ってみましょう。