読者です 読者をやめる 読者になる 読者になる

リストを実装してメモリエディタで遊んでみる。

今回は解説というより半分遊びなので口調がいつもと違うかも。
標準STLばっか使っててデータ構造何一つ実装したことないので双方向リスト(実質単方向だけど)リスト実装してみた。とりあえずソースコード

//list.h

template <class TType> class List{
private:
	List* Next;
	List* Prev;
	TType Data;
		
public:
	TType& getData(){return Data;}
	List* getNext(){return Next;}


	//イテレータクラス
	class Iterator{
		private:
			List* iter;
		public:
			void operator++(int){iter=(iter->getNext());}
			TType& operator*(){return iter->getData();}
			void operator=(List* ptr){iter=ptr;}
			bool operator!=(List* it){return iter!=it;} 
	};


	List();
	~List();
	List(List<TType>* _Prev,TType _Data);
	void append(TType _Data);
	
	List* begin(){return Next;}
	List* end(){return NULL;}

};


template <class TType> List<TType>::List(){
		Next=NULL;
		Prev=NULL;
}

template <class TType> List<TType>::~List(){
		delete Next;
}


template <class TType> List<TType>::List(List<TType>* _Prev,TType _Data){
		Next=NULL;
		Prev=_Prev;		
		Data=_Data;
}



template <class TType> void List<TType>::append(TType _Data){
		if (Next==NULL){
			Next=new List<TType>(this,_Data);
			return;
		}
		Next->append(_Data);
		return ;
	
	}

mainの方は以下の通り

//main.cpp
#include<iostream>
#include "list.h"
 

int main(){
	List<int> hoge;
	hoge.append(1);
	hoge.append(2);
	List<int> foo;
	foo.append(3);
	foo.append(4);
	foo.append(5);
	
	std::cout<<&hoge<<std::endl;		
	std::cout<<&foo<<std::endl;
	
	List<int>::Iterator it;
	it=hoge.begin();
	while(it!=hoge.end()){
		 	std::cout<<*it<<std::endl;
			it++;
	}
	int num;
	std::cin >> num;//プログラムを一時停止するため
	
	it=hoge.begin();
	while(it!=hoge.end()){
		 	std::cout<<*it<<std::endl;
			it++;
	}	

}

簡単に解説しておくと、次のリストへのポインタと前のリストへのポインタを持っておく。これで先頭からも、後ろからもリストをたどれるはずなんだけど、だるかったので先頭からしか手繰れない仕様。ソース見ればわかると思うんだが、append、つまり追加するときはNextがNullになるまで再帰的に呼び出してNextがNullになったらそのなかにnewしたリストのアドレスを入れる。ってなわけでコンストラクタ2つもっていて、一方はクラス内部用、もう一方はリストとしてインスタンス化するよう。設計的にまずいような気もするけど。あと、イテレータも実装してある。こっちは演算子を適当にオーバーロード。内部でListのgetData()とかを呼び出していてこれってカプセル化危ないんじゃないかなとか思ったりもするけど、内部クラスをfriendにする方法がわからない...ってかfriendクラスを使ったことがないからわからないのでpublicにしてある。通常friendよくないっていわれるからつかってこなかったけど、こういう時は使いたいな。

実装できた。で終わりでもいいんだけど、それだけじゃイマイチおもしろくなかったのでメモリエディタで本当にNextポインタに次のリストのエレメントのアドレスが入っているか調べてみて手動でリストの連結してみようと思い立つ。とりあえず、mainを実行しただけだと1,2をいれたhogeのリストをイテレータで回しているので

1
2
(入力した数字)
1
2

って出力が得られるはず。次にこれの2を持っているリストのエレメントのNextにfooの次のアドレスを入れてみる。これをメモリエディタのうさみみハリケーンを使ってする。

【手順1:hogeリストを手繰る】

まず、「std::cout<<&hoge<<std::endl;」ってところでhogeのポインタを表示してる。コンソールの一番上に表示されてるやつだ。とりあえず、このアドレスに移動してみよう。移動先の最初の4byteがNextポインタの値、次の4byteがPrevの値(僕の環境では。)だ。Prevのほうは何もないからNULL(00 00 00)となってる。そしてその次の4byteがData。この場合int型のリストにしてるからってことで4byte。たぶん他の型のリストを作るとここの長さは変わるんじゃないかと思う。なんで、こんなことが分かったかというと...説明すると長いので省略。さてこれで次のエレメントのアドレスがわかっているわけだからそこに移動する。これでNextがNULLのところに行き着けばそこがリストの末端ということだ。僕の環境では次のアドレスは「D0 33 23 01」となっている。これは当然newで確保されている、つまりヒープ領域に確保されているので環境によって大きく異なると思う。sて、ここで注意しないといけないのはIntel系のCPUなんかを使っている場合リトルエンディアンということ。つまり逆転しているので僕が移動しなくてはいけないアドレスはややこしいけど「01 23 33 D0」となる。うまく移動できていればPrevの領域にはちゃんと移動前のアドレス、Dataの領域には「01 00 00 00」つまり1が入っているはずだ。次もも同じようにNextポインタのさしているアドレスに移動。データを確認すると確かにPrev,Dataの値は正しい。今回違うのはNextがNULLになっているということ。つまり末尾にたっしたというわけ。このNextにfooの3を格納しているエレメントを格納すれば終了だ。次にfooのリストを同様に検査する必要があるので今いるアドレスをメモ帳か何かに書き留めておく。

【手順2:fooリストを手繰る】

まったくおなじようにすればいい。最初のエレメントのNextの値が3のエレメントのアドレスのはずだ。このアドレスを先ほどのアドレスの位置に挿入する。ここで注意しなくてはいけないのはこのfooのNextポインタのアドレスをNULLにしておかないといけないということ。じゃないとデストラクタでfooが解放されたとき2重deleteされて予期せぬことが起こるかもしれない。

【手順3:結果】

書き換えてコンソールに戻り適当な数字(僕は1を入れた)を入力すると...無事に

f:id:ikaro1192:20111218123020p:image

という結果が出た。ちゃんとhogeとfooがつながってるね。めでたしめでたし。