Version 13.14
リストのしくみ
「前々回は CStringArray を使ってみました。で、今回はその兄弟に当たる
CStringList と CMapStringToString を使ってみます」
『はーい』
「まず、この３つは一般的には次のように分類されます」
CStringArray ：配列
CStringList ：リスト
CMapStringToString ：マップ
『？』
「どれも CString を格納するコレクションなんだけど、格納方法や扱い方
がそれぞれ違っています。その〈格納方法〉の分類がこの３つ」
『配列って、 CStringArray は配列じゃないけど』
「ところが、 CStringArray 中では配列のように扱ってるんです」
『へー』
「実際には動的に作成したメモリ領域だけど、扱い方は配列と同じ」
『……ちょっと待って。配列以外でデータの格納、ってイメージわかないん
だけど、リストとかマップってどんなんなの？』
「それをこれから説明します。まぁとりあえず使用方法から」
void Use_CStringList()
{
CStringList cStrList;
cStrList.AddTail( "CCC" );
cStrList.AddTail( "BBB" );
cStrList.AddTail( "AAA" );
cStrList.AddTail( "EEE" );
cStrList.AddTail( "DDD" );
for( POSITION pos = cStrList.GetHeadPosition()
; pos != NULL
;
)
{
CString cStr = cStrList.GetNext( pos );
TRACE( "%s ", cStr );
}
TRACE( "\n" );
// CCC BBB AAA EEE DDD
}
『 CStringArray とだいぶ違うね』
「まず、データの追加には CStringList::AddTail() を使用します」
『ているってしっぽだよね』
「そう、だから末尾に追加ってこと。同じように CStringList::AddHead()
っていう頭に追加するメンバ関数もあります」
『もうこの辺から CStringArray と違うわけね』
「というか、この例で使っているメンバ関数は全部違うかも。次の for
ループはちょっと難しいかな」
for( POSITION pos = cStrList.GetHeadPosition()
; pos != NULL
;
)
{
CString cStr = cStrList.GetNext( pos );
TRACE( "%s ", cStr );
}
「実はこの for ループ、中の CStringList::GetNext() を呼ぶところまで
がひとつなんです」
『え？』
「この CStringList::GetNext() を呼ばないと、 for ループが成り立たな
くなるので注意してください」
『削除しちゃいけないってことね……』
「では１行ずつ見ていきます。まず」
for( POSITION pos = cStrList.GetHeadPosition()
「 POSITION っていうのは CStringList 用の型で、〈今どこを指している
か〉を格納します」
『？？？』
「ひとつ飛ばして」
CString cStr = cStrList.GetNext( pos );
「この pos の中に〈今どこを指しているか〉が入っていて、 GetNext() は
その pos の情報を元にデータを取り出して、 cStr に返すんです」
『配列のインデックスナンバーみたいなもん？』
「ほとんどそれと同じ。で、この GetNext() を呼ぶと、 pos の位置がひと
つ進んで、次のデータの位置へ移動します」
『 ++iF1 みたいな感じね』
「そして for の判断文」
; pos != NULL
「 GetNext() は、最後のデータを取り出したときに、 pos に NULL をセッ
トするから」
『これが NULL だったら最後、ループから出るってわけね』
「そういうこと」
『でもさ、なんでインデックスナンバー使わないの？』
「それは、リストは配列と構造が違うから。配列は」
[データ][データ][データ][データ][データ][データ]...
「って、メモリ上に連続して並んで入ってます。これは CStringArray とか
も同じ。ところが、 CStringList とかのリストは、それぞれのデータがバ
ラバラになっているんです」
[前へのポインタ＋データ＋次へのポインタ](a)
[前へのポインタ＋データ＋次へのポインタ](b)
[前へのポインタ＋データ＋次へのポインタ](c)
「リストはひとつのデータを入れる変数の中に〈前の要素へのポインタ〉と
〈後ろの要素へのポインタ〉を持っているんです」
『前後の要素へのポインタ……』
「上の例で、(a)(b)(c)と並んでいるとすると、(a)の〈次へのポインタ〉は
(b)のアドレスが入ってます。そうすれば、(a)から(b)へたどれるでしょ」
『そか、ポインタで数珠繋ぎ！』
「そういうこと。具体的に書くとこんな感じかな
[ NULL ＋データ＋ (b) ](a)
[ (a) ＋データ＋ (c) ](b)
[ (b) ＋データ＋ NULL ](c)
『切れ目は NULL 入れておくんだね』
「こうすることでリストの各要素は継ながるわけです。リストを使うメリッ
トとデメリットは以下の通り」
・挿入と削除が簡単にできる。
・インデックスナンバーで検索するのに時間が掛かる。
「まず挿入と削除について。たとえば上の例で(b)を削除する場合、どうす
ればいい？」
『んーと、(a)の次に(c)が来ればいいんだから、(a)の〈次へのポインタ〉
に(c)のアドレス入れて、逆に(c)の〈前へのポインタ〉に(a)のアドレスを
入れる、かな？』
「そう！ つまりポインタのつなぎ換えだけでできるんです。こんな感じに
ね」
[ NULL ＋データ＋ (c) ](a)
[ (a) ＋データ＋ NULL ](c)
「この、要素の削除を配列でやると、実は大変なんです」
[データ１][データ２][データ３][データ４][データ５][データ６]...
「データ２を削除するときにはどうすればいい？」
『データ１の次にデータ３なんだから……あ”、データ２の場所にデータ３
を上書きして、データ３のところにデータ４を上書きして……って、かなり
大変』
「でしょう。だから、 CStringList は挿入、たとえば〈どんどん頭に追加
していく〉とかの処理には向いてるから、そういう場合に使うといいってこ
と」
『もひとつのインデックスナンバーは……あ、そっか』
「はい火美ちゃん」
『３番目、ってデータが欲しい時って、頭からデータ追っていかなきゃいけ
ないんだ』
「そういうこと。まず(a)を見て、〈次へのポインタ〉経由で(b)へ行って、
さらに〈次へのポインタ〉経由で(c)へ行って、やっと３番目だ、ってこと
でこの要素を返す、っていう手順」
『めんどくさー』
「だからそういう処理を何度もすると時間が掛かるかな、比較的だけど」
『比較的？』
「マシンパワーがあればカバーできるレベルだからね。ただ、２重３重の
ループだとバカにならないから」
『だから比較的、ね』
「リストにはこういうメリットとデメリットがあるから、それに併せて用途
を考えた方がいいかな」
『……？ あのさ、リストってソートに向いてなくない？』
「向いてないよ」
『げ』
「リストは〈途中からの検索〉は苦手だし、ソートは要素の増減がないから
リストのメリットもないし」
『じゃあ教わった意味ないじゃん』
「そうでもないよ。今は CStringArray と CStringList 、違いがわかるで
しょ」
『わかんないと困る？』
「このふたつは使い道似てるから、どっちが向いてるかとかは、仕組みがわ
からないと」
『そか、選べないね』
「それに、 CStringList そのものはメリット多いからね。こんなふうに、
CStringArray に変換することもできるし」
// CStringArray にコピー。
CStringArray cStrAry;
for( POSITION pos = cStrList.GetHeadPosition()
; pos != NULL
;
)
{
cStrAry.Add( cStrList.GetNext( pos ) );
}
『そか、そうすればソートもできるんだね』
「そういうこと。コレクションには色々な種類があって、それぞれ特徴があ
るから、うまく使っていくようにしてください」
/*
Preview Next Story!
*/
『なーんかこまごまとしたのばっか続くね』
「というわけでバブルソートは今回で終わり」
『お！』
「次回からはクイックソート編！」
「というわけで次回」
＜ Version 13.15 最速・クイックソート ＞
『につづく！』
「でもあまり使わないんだけどね」
『え”』
users
users
