#pragma twice

KAB-studio > プログラミング > #pragma twice > 250 Version 13.14 リストのしくみ

#pragma twice 250 Version 13.14 リストのしくみ

前のページへ 表紙・目次へ 次のページへ

 Version 13.14
リストのしくみ

前々回は CStringArray を使ってみました。で、今回はその兄弟に当たる
CStringList と CMapStringToString を使ってみます
はーい
まず、この3つは一般的には次のように分類されます

CStringArray       :配列
CStringList        :リスト
CMapStringToString :マップ


どれも CString を格納するコレクションなんだけど、格納方法や扱い方
がそれぞれ違っています。その〈格納方法〉の分類がこの3つ
配列って、 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 ループが成り立たな
くなるので注意してください
削除しちゃいけないってことね……
では1行ずつ見ていきます。まず

    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)

この、要素の削除を配列でやると、実は大変なんです

[データ1][データ2][データ3][データ4][データ5][データ6]...

データ2を削除するときにはどうすればいい?
データ1の次にデータ3なんだから……あ”、データ2の場所にデータ3
を上書きして、データ3のところにデータ4を上書きして……って、かなり
大変
でしょう。だから、 CStringList は挿入、たとえば〈どんどん頭に追加
していく〉とかの処理には向いてるから、そういう場合に使うといいってこ

もひとつのインデックスナンバーは……あ、そっか
はい火美ちゃん
3番目、ってデータが欲しい時って、頭からデータ追っていかなきゃいけ
ないんだ
そういうこと。まず(a)を見て、〈次へのポインタ〉経由で(b)へ行って、
さらに〈次へのポインタ〉経由で(c)へ行って、やっと3番目だ、ってこと
でこの要素を返す、っていう手順
めんどくさー
だからそういう処理を何度もすると時間が掛かるかな、比較的だけど
比較的?
マシンパワーがあればカバーできるレベルだからね。ただ、2重3重の
ループだとバカにならないから
だから比較的、ね
リストにはこういうメリットとデメリットがあるから、それに併せて用途
を考えた方がいいかな
……? あのさ、リストってソートに向いてなくない?
向いてないよ

リストは〈途中からの検索〉は苦手だし、ソートは要素の増減がないから
リストのメリットもないし
じゃあ教わった意味ないじゃん
そうでもないよ。今は 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 最速・クイックソート >
につづく!
でもあまり使わないんだけどね
え”
 
del.icio.us 登録する
Yahoo!ブックマーク 詳細を表示 users
livedoorクリップ 詳細を表示 livedoorクリップ ブックマーク数
はてなブックマーク 詳細を表示 はてなブックマーク ブックマーク数
RSSに登録
del.icio.us 登録する
Yahoo!ブックマーク 詳細を表示 users
livedoorクリップ 詳細を表示 livedoorクリップ ブックマーク数
はてなブックマーク 詳細を表示 はてなブックマーク ブックマーク数
 
このページは、Visual C++ 6.0を用いた C++ 言語プログラミングの解説を行う#pragma twiceの一コンテンツです。
詳しい説明は#pragma twiceのトップページをご覧ください。