データ構造 第04講「動的なデータ構造ってどうやってるのさ」 08/12加筆
目次→美祢『データ構造』 目次 - 武蔵高中 ＣＰＵ愛好会 活動日誌
前回までは
要素の追加に応じて、動的にメモリを確保してくれる動的配列、「vector」について学びました。
今回は、前回扱わなかった「途中に要素を挿入する関数」等を扱っていきましょう。
vectorのイテレーター
途中で要素を挿入する関数は、vectorだけではできません。理由は後で説明します。ではそれに必要なiteratorについて説明しましょう。
std::vector<int>::iterator it;
この様にして、iteratorは宣言します。iteratorというのは、ポインタに似たような働きがありますが、さらにvectorや後述のlist等と言った、「コンテナ」と称される配列的なデータ構造の上で、指す先を前後の要素に動かせられるという特長があります。どうやって使うかというと、
#include <vector> //00 int main(){ //01 std::vector<int> vi; //02 std::vector<int>::iterator vi_it; //03 //04 for(int i=0;i<12;i++){vi.push_back(i);} //05 vi_it=vi.begin()+6; //06 vi.insert(vi_it,100); //07 for(vi_it=vi.begin();vi_it!=vi.end();vi_it++){*vi_it++} //08 vi_it--; //09 vi.erase(vi_it); //10 } //11
02行目でint型動的配列「vi」を、03行目でint型動的配列のiterator「vi_it」を宣言しています。
05行目で、viの要素は{0,1,2,3,4,5,6,7,8,9,10,11}となります。
06行目で、vi_itは、「vi[0]から６つ後」、つまりvi[6]を指すようになります。（この「+」「-」の使えるのは「ランダムアクセスイテレータ」という種類のiteratorだけで。後述するlist::iterator等では+や-が使用できません。）
07行目で、vi_itの指している「vi[6]」として、２番目の引数で指定した値（100）が挿入されます。。ここで、vi[7]以降を指していたポインタ・iteratorは無効になると考えてください。なぜなら、動的配列は配列の名の通り、「要素がメモリ上に続いて並んでいる」ものなので、確保していたメモリが足りなかったら、今度は２倍ぐらいの要素が確保できる、新しいメモリの領域が確保されて、vectorの内容はそちらに移動してしまうからです。
※vi={0,1,2,3,4,5,100,6,7,8,9,10,11}
08行目では、vi.end()は、viの最後の要素「の一つ次」（実際には何も無い所）を指します。また、「vi_it++」の様に、インクリメント・デクリメントも使用できます。（list::iteratorでも、この「++」「--」は使用できます）つまり、for文は「vi[0]から１つずつ後ろを見て、最後の一つ次にならない間」つまり「viの要素数だけ繰り返す」表現です。
iteratorの内容を見る時は、「*」を使います。また、構造体・クラスをvectorの要素の型に指定した場合、そのメンバーを見る時はアロー演算子「->」を使って、「vi_it->status」の様にします。
※vi={1,2,3,4,5,6,101,7,8,9,10,11,12}
09行目では、for文の最後に「vi.end()」を指してるvi_itを、一個戻します。ここではvi[12]を指すようになります。
10行目では、vi_itの指す要素、vi[12]の中身を消します。
※vi={1,2,3,4,5,6,101,7,8,9,10,11}
vectorのiteratorの動き
vectorは配列のように、つまり下の図のようになってメモリ上にいます。
なので、内部的には「+」「++」とか「-」「--」する分だけsizeof(Type)を足し引きしていけばいいわけです。（Typeは、vector生成の時に、「<>」の中に入れた型名）
リストという考え方
配列以外にも複数のデータを順序づけてまとめる方法はあって、この「リスト」という考え方では、「ある要素は次の要素とへのポインタを持っている」という構造で順序を付けます。
特に、「前の要素へのポインタ」を持っている物を、「双方向リスト」と呼びます。双方向リストの実装であるlistを例に図にするとこんな感じです。
listにもiteratorはあります。というか、listではvectorの様に「」が使えず、iteratorを使わないと中身を見られないので、必ず使うこととなります。
図の矢印は、それぞれ、「begin()の返り値はここを指すiterator」「end()の返り値はここを指すiterator」（begin(),end()はlistのメンバ関数）、「ここを指してるiteratorに++演算を行うとこっちを指す様になる」「ここを指してるiteratorに--演算を行うとこっちを指す様になる」ことを意味します。
この図の様に、各要素は前後の要素へのポインタで繋がっていて、iteratorのポインタ部分に前後を指すポインタを代入する事で++,--演算を行っている訳です。また、listの場合には、最初の要素の一個前と、最後の要素の一個後に、空白の（要素数に数えられない）要素が用意されています。end()等に使うためでしょう。
listのiteratorは大方vectorのiteratorと同じですが、vectorの時に使えた「+」「-」は使えず、「++」「--」による移動となります。それは図を見ても何をしているのか明らかでしょう。
また、この繋ぎ方の優れている点として、「要素の挿入や削除が一瞬でできる」という点があります。例えば、「５番目の要素として新しいのを入れたい」と思ったら、
[f:id:musashi_cpu:20110806035436j:image]
「(3)→(4)」だったのを「(3)→(8)→(4)」と繋ぎ直すだけです。一瞬ですね。vectorの様な「確保してるメモリで足りるか」って考える時間が無い訳です。
しかし、iteratorの「+,-,」でほぼ直接添字を指定するという事ができないので、一概に挿入が早いとは言えないかもしれません。順番を特に気にして、最初から最後まで読んでいく風に見ていく事の多いデータをまとめる時にlistを使ってみてはいかがでしょうか。
vectorとlistの共通点
「vectorのイテレーター」の項でやった例文をlistで行うと、
#include <vector> //00 int main(){ //01 std::ist<int> li; //02 std::list<int>::iterator li_it; //03 //04 for(int i=0;i<12;i++){li.push_back(i);} //05 for(li_it=li.begin(),int i=0;i<6;i++){li_it++;} //06 li.insert(li_it,100); //07 for(li_it=li.begin();li_it!=li.end();li_it++){*li_it++} //08 li_it--; //09 li.erase(li_it); //10 } //11
こうなります。06行目（+,-が使えないので++,--をループして添字を指定する）以外は同じですね。
08/21加筆:listとvectorの相違点としては、iteratorの仕様の他に、 listにはあるpush_front(),pop_front()という関数がvectorにはないという事も挙げられます。 おそらく、vectorではbackとfrontで処理の仕方が圧倒的に違う （backなら普通に追加するけれど、frontなら全部後ろに動かしてから最初の要素として入れ込む）ためだと思います。
Ｃ++にはこの様にどれを使っても同じ名前の関数・演算子で動かせるような「STL」というものがあるので、利用すると便利でしょう。
今回の終わりに
今回学んだ、「リスト」の考え方は、プログラミングの深い世界に入るととても重要になってきます。
例えば、↓の画像の様な、各マスが６角形のマップがあるとします。これ全体を管理したい時に、二次元配列を使う方法や、一次元配列を使う方法がありますが、こういう「まっすぐ一列」と言いづらい形のものの位置を配列の添字で扱うと、間違いや混乱を招きやすいです。
それならば、各マスを「マスの情報（地形等）、左上・上・右上・右下・下・左下のマスへのポインタ」という情報の入ったクラスにする事で、リストの様にポインタで隣のマスに移るというデータ構造が出来上がります。
次回やることは、今のところ未定です。今までやったデータ構造の応用か、新たなデータ構造かのどちらかになります。
記事の完成が１週間遅れて申し訳ありませんでした。
参考
Programming Place Plus「●アルゴリズムとデータ構造編 第１２章 双方向リスト」http://www.geocities.jp/ky_webid/algorithm/012.html
C/C++ リファレンス「C++ イテレータ」http://www.cppll.jp/cppreference/iterators.html
