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の利用例は以下の通りである。やや長くなっているので、「続きを読む」で格納しておく。
int main(){ list<std::string> lst; while(true){ int num; std::cin >> num; if(num == 0){ //push std::string st; std::cin >> st; lst.push(st); lst.show(); } else if(num == 1){ //pop int pop_num; std::cin >> pop_num; std::cout << lst.pop(pop_num) << std::endl; lst.show(); } else if(num == 2){ //find std::string st; std::cin >> st; std::cout << lst.find(st) << std::endl; } else if(num == 3){ //pop_element std::string st; std::cin >> st; lst.pop_element(st); lst.show(); } else if(num == 4){ //clear lst.clear(); lst.show(); } else if(num == 5){ //size std::cout << lst.size() << std::endl; } else break; } lst.show(); return 0; }
実行例と出力例は以下の通り。
list<T>::list() 0 apple 0:apple 0 orange 0:orange 1:apple 0 apple 0:apple 1:orange 2:apple 0 melon 0:melon 1:apple 2:orange 3:apple 0 lemon 0:lemon 1:melon 2:apple 3:orange 4:apple 0 apple 0:apple 1:lemon 2:melon 3:apple 4:orange 5:apple 0 grape 0:grape 1:apple 2:lemon 3:melon 4:apple 5:orange 6:apple 0 fruit 0:fruit 1:grape 2:apple 3:lemon 4:melon 5:apple 6:orange 7:apple 5 8 0 ooo 0:ooo 1:fruit 2:grape 3:apple 4:lemon 5:melon 6:apple 7:orange 8:apple 5 9 2 orange 7 2 apple 3 1 5 melon 0:ooo 1:fruit 2:grape 3:apple 4:lemon 5:apple 6:orange 7:apple 5 8 3 apple 0:ooo 1:fruit 2:grape 3:lemon 4:orange 5 5 3 apple 0:ooo 1:fruit 2:grape 3:lemon 4:orange 5 5 4 5 0 1 0 invalid num:0 -- error in list<T>::pop 7 list<T>::~list()
