1.3.1 動的確保
動的確保についてのお話。
今回、スタックやキューに動的確保を適用するところまで行かなかった(記事が長くなり過ぎる)ので、1.3.1という番号を振った。次回はスタック・キューに動的確保を導入する。
CやC++において、配列を宣言する時は以下のようにしなくてはならない。
float hoge[10]; const int num = 5; float fuga[num];
つまり、宣言時に配列のサイズを確定させなくてはならないということ。
で、以下のような宣言サイズに変数を用いるケースではコンパイルエラーが発生する。
int num = 5; float fuga[num]; //error!
これは、C/C++のコンパイラがコンパイル時に配列に必要なメモリを確保する為であるらしい。
しかし、場合によっては配列の要素数を可変長にしたいこともある。データ数が未知である場合などである。そういう時は、少し特殊な形式で配列を宣言する必要がある。占有メモリ数が固定である今までの例が静的確保と呼ばれるのに対して、このように占有メモリ数が可変長である配列を宣言することは、動的確保と呼ばれる。
動的確保では、メモリの管理はプログラマに任される。今までコンパイラが自動化していた処理をプログラマが担うということである。メモリ管理では、メモリの確保と解放が大切である。
Cの場合
こちらは自分があまり利用する機会が無いだろうが、一応書いておく。
Cの場合、stdlib.h内にあるmalloc()とfree()を用いて確保と解放を行う。
//mallocによる動的確保 #include <stdio.h> #include <stdlib.h> int main(){ int *lst; int lst_size; int i; scanf("%d", &lst_size); lst = (int *)malloc( sizeof(int)*lst_size ); for(i=0; i<lst_size; i++) scanf("%d", &lst[i]); for(i=0; i<lst_size; i++) printf("%d:%d\n", i, lst[i]); free(lst); return 0; }
動的に確保したい配列を、ポインタ変数として宣言する(int *lst)。
malloc()の返り値はvoid*型なので、キャストによって正しい形式に揃える。確保メモリは引数で指定する。
最後に、確保したメモリをfree()で解放するのを忘れないこと。
C++の場合
Cでいうmalloc()とfree()を、newとdeleteが肩代わりする。これらは関数では無く演算子である点に注意する。
//newによる動的確保 #include <iostream> using namespace std; int main(){ int *lst; int lst_size; cin >> lst_size; lst = new int[lst_size]; for(int i=0; i<lst_size; i++) cin >> lst[i]; for(int i=0; i<lst_size; i++) cout << i << ":" << lst[i] << endl; delete[] lst; return 0; }
「new (型)[確保サイズ]」で「(型*)malloc(sizeof(型)*確保サイズ)」と同じ意味を表す。解放にはdelete[ ]を用いる。確保サイズが1で良い場合は、[ ]を省く。このとき、解放はdeleteを用いる点に注意([ ]が要らない)。*1
listの表現
さて、動的確保を用いてlistを表現しよう。
listの要求仕様は以下であるとする。
データ(型未定)は動的に確保される。
push(obj)でデータをリストの先頭に追加。
pop(num)でnum番目の要素を取り出す。
pop_element(elem)でリストからelem要素を削除し、削除数を返す。
find(value)でリストからvalue要素を検索し、最近pushされた要素番号を返す。
clear()でリストを初期化。
size()でリストサイズを返す。
show()でリストの内容を展開する。
//list #include <iostream> template<class T> class list{ class set_of_datum{ //valueとnextのセット private: T value; set_of_datum *next; public: set_of_datum(T value){ this->value = value; next = NULL; } int set_next(set_of_datum *next){ this->next = next; } set_of_datum *get_next(){return next;} T get_value(){return value;} }; private: set_of_datum *data; //先頭データ public: list(); //コンストラクタ ~list(); //デストラクタ void clear(); //メモリの全解放 int size(); //listサイズを返す void push(T value); //valueをpushする T pop(int num); //num番目の要素をpopする int pop_element(T elem); //elementを消去する int find(T value); //valueを持つデータが何番目にあるか void show(); //listの要素を見せる }; template<class T> list<T>::list(){ data = NULL; std::cout << "list<T>::list()" << std::endl; } template<class T> list<T>::~list(){ clear(); std::cout << "list<T>::~list()" << std::endl; } template<class T> void list<T>::clear(){ set_of_datum *next = data; //listの次のポインタを示す while(next != NULL){ set_of_datum *target = next; //delete対象 next = (*next).get_next(); delete target; } data = NULL; } template<class T> int list<T>::size(){ int value = 0; set_of_datum *next = data; //listの次のポインタを示す while(next != NULL){ next = (*next).get_next(); value++; } return value; } template<class T> void list<T>::push(T value){ set_of_datum *new_datum = new set_of_datum(value); (*new_datum).set_next(data); data = new_datum; } template<class T> T list<T>::pop(int num){ T dummy; //エラー発生時に返すもの if(num<0){ std::cout << "invalid num:" << num << " -- error in list<T>::pop" << std::endl; return dummy; } set_of_datum *target = data; set_of_datum *before = NULL; for(int i=0; i<num; i++){ if(target == NULL) break; before = target; target = (*target).get_next(); } if(target == NULL){ std::cout << "invalid num:" << num << " -- error in list<T>::pop" << std::endl; return dummy; } if(before == NULL){ //listの最初をpopした data = (*target).get_next(); } else{ (*before).set_next((*target).get_next()); } T value = (*target).get_value(); delete target; return value; } template<class T> int list<T>::pop_element(T elem){ int value = 0; while(true){ int num = find(elem); if(num == -1) return value; pop(num); value++; } } template<class T> int list<T>::find(T value){ set_of_datum *d = data; for(int i=0; d!=NULL; i++){ if((*d).get_value() == value) return i; d = (*d).get_next(); } return -1; } template<class T> void list<T>::show(){ set_of_datum *d = data; for(int i=0; d!=NULL; i++){ std::cout << i << ":" << (*d).get_value() << std::endl; d = (*d).get_next(); } }
簡単に仕組みを説明すると、listの本体である*dataは、値であるvalueと次要素へのポインタであるnextを持っている。初期*dataはNULLである。
リストのn番目がpopされた場合、n-1番目の要素のnextをn+1番目の要素に繋ぎ、n番目の要素をdeleteすれば平和的に解決される。
口で言うのは簡単だが、これをコーディングするのはなかなか骨が折れた。大学の実験でもC言語でlistを組んだが、一発合格が貰えたのはクラスの優秀な人たち3人ほどだった(私はもちろん入っていない)。興味が持てた人は一度自分で組んでみることを薦める。
上記listの利用例は以下の通りである。やや長くなっているので、「続きを読む」で格納しておく。
1.2 スタックとキュー
今回は、スタック(stack)とキュー(queue)について纏める。
なお、今回使用する画像は、http://www.akita-nct.ac.jp/yamamoto/lecture/2005/2E/test_4/html/node2.html から引用している。こちらのページに、スタックとキューについてより詳しい内容が載っている。
スタック・キューは、単にデータ構造を表しているに過ぎない。
スタックとは、上のような画像で表されるデータ構造で、後に入れたデータから取り出されていく仕組みを持っている。ゲームの箱を上に積んでいき、上から順に消化していく、というのがスタックの分かりやすいたとえではないだろうか。スタックにデータを突っ込むことをpushと言い、データを取り出す(最近pushされたデータに限る)ことをpopという。
キューとは、上のような画像で表されるデータ構造で、スタックとは対照的に、先に入れたデータから取り出されていく仕組みを持っている。キューにデータを突っ込むことをenqueueと言い、データを取り出すことをdequeueという。
というわけで、テンプレートを用いてまずはスタックを組んだ。
//スタック #include <iostream> #define MAX_STACK_SIZE 100 template <class d_type> class stack{ private: d_type data[MAX_STACK_SIZE]; int data_num; public: stack(); //コンストラクタ void clear(); //スタックの中身を空にする void push(d_type obj); //スタックにobjを追加する d_type pop(); //スタックからobjを取り出す void show(); //スタックの中身を見せる int get_data_num(){return data_num;} }; template <class d_type> stack<d_type>::stack(){ data_num = 0; } template <class d_type> void stack<d_type>::clear(){ data_num = 0; } template <class d_type> void stack<d_type>::push(d_type obj){ if(data_num+1 < MAX_STACK_SIZE){ data[data_num] = obj; data_num++; } else{ std::cout << "This stack is FULL! -- error in stack<d_type>::push" << std::endl; } } template <class d_type> d_type stack<d_type>::pop(){ if(data_num>0){ data_num--; return data[data_num]; } else{ std::cout << "This stack is EMPTY! -- error in stack<d_type>::pop" << std::endl; } } template <class d_type> void stack<d_type>::show(){ for(int i=0; i<data_num; i++){ std::cout << i << ":" << data[i] << std::endl; } }
特に説明すべき点は無いと思う。
いずれ、dataは動的に宣言して可変長にするつもりだが、とりあえず今は静的に宣言しておく。
また、今回using namespaceを使っていないが、これは今回組んだコードを汎用探索パッケージに流用する予定がある為である。
単純なデータ構造であるスタックに対して、キューはやや複雑な構造をしている。格納されているデータ数と、キューの占有メモリは正比例の関係に無いのである。
そこで、以下のような構造が考えられる。
今回は静的宣言の為、このような逃げ道を用意したが、動的宣言の場合はもっと話が単純になる。取り出したデータのメモリをその都度解放してやれば良いだけである。この点に関しては、動的宣言の場合スタックとほとんど仕組みが変わらない為、ある意味楽なのかもしれない。
//キュー #include <iostream> #define MAX_QUEUE_SIZE 100 template <class d_type> class queue{ private: d_type data[MAX_QUEUE_SIZE]; int first_num; //最初のデータ格納番号 int data_num; public: queue(); //コンストラクタ void clear(); //キューの中身を空にする void enqueue(d_type obj); //キューにobjを追加する d_type dequeue(); //キューからobjを取り出す void show(); //キューの中身を見せる int get_data_num(){return data_num;} int get_first_num(){return get_first_num;} }; template <class d_type> queue<d_type>::queue(){ first_num = 0; data_num = 0; } template <class d_type> void queue<d_type>::clear(){ first_num = 0; data_num = 0; } template <class d_type> void queue<d_type>::enqueue(d_type obj){ if(data_num+1 < MAX_QUEUE_SIZE){ data[(first_num+data_num)%MAX_QUEUE_SIZE] = obj; data_num++; } else{ std::cout << "This queue is FULL! -- error in queue<d_type>::enqueue" << std::endl; } } template <class d_type> d_type queue<d_type>::dequeue(){ if(data_num>0){ data_num--; int value = first_num; first_num = (first_num + 1) % MAX_QUEUE_SIZE; return data[value]; } else{ std::cout << "This queue is EMPTY! -- error in queue<d_type>::pop" << std::endl; } } template <class d_type> void queue<d_type>::show(){ for(int i=0; i<data_num; i++){ std::cout << i << ":" << data[(first_num+i)%MAX_QUEUE_SIZE] << std::endl; } }
さて、ここで「何故、スタックとキューの2種類のデータ構造を学ぶ必要があるか？」について、少しだけ書いておく。
実は、この2つのデータ構造は深さ優先探索と幅優先探索に密接に関係する。前者がスタック、後者がキューに関係しているのである。この点に関しては、探索の話に入った時により詳しく纏める。
データ構造を簡潔に理解しておくことで、厄介な探索アルゴリズムが非常にスッキリ理解できる。
しかし、今回の私の最終到達目標はそこではない。スタックもキューも、実は最終的には使用する予定が無い。まぁ、教養として知っておくべきことだろうということで、とりあえずこれを使って基本探索アルゴリズムは組む予定だが。
1.1 テンプレート ～汎用探索パッケージ制作～
ようやく余裕が出てきたので、この辺で作業を進めておく。
汎用探索パッケージを制作するに当たって、まずはC++のテンプレートについて基本を押さえる。
テンプレートはC++に後年標準化された機能(?)で、あらゆる型に対応したオーバーロード関数・クラスをコンパイル時に自動生成する。
つまり、テンプレートが実装される前は、int型とfloat型に対応したswapは以下のように定義しなければならなかった。*1
void swap(int &a, int &b){ int c = a; a = b; b = c; } void swap(float &a, float &b){ float c = a; a = b; b = c; }
このように、実質やっていることは同じだが、引数の型に応じていちいち関数を書かなければならなかったのである。
その問題を解決するのがテンプレートで、上のようなswapを表現するには、以下のように書けばよい。
template <class d_type> void swap(d_type &a, d_type &b){ d_type c = a; a = b; b = c; }
上のコードで言うと、d_typeが様々な変数の型の肩代わりをしてくれて(ギャグでは無い)、コンパイル時に必要な型のオーバーロード関数を自動生成してくれる。便利である。
テンプレートを使用するには、以下のキーワードが必要だ。
template <class hoge>
この直後に、テンプレートを使用する関数(あるいはクラス、構造体)を宣言する。classはtypenameと置換可能である。typenameを使うと、テンプレート内で新たなテンプレートを宣言することが出来るらしい(独習C++には詳しく書いていなかった)。
被テンプレート雛形の宣言はtemplate
template <class hoge> int i; //error! void foo(hoge x){ // ... }
ここで、独習C++の練習問題11.1.3を解こう。
テンプレート関数の好例として、find()という関数があります。この関数は、配列内であるオブジェクトを検索します。オブジェクトが見つかった場合はそのオブジェクトのインデックスを返し、オブジェクトが見つからなかった場合は-1を返します。
template <class d_type> int find(d_type object, d_type *list, int size){ for(int i=0; i<size; i++){ if(object == list[i]) return i; } return -1; }
