線形リストを作ってみる その３

programming C++

その２の続き。。。
線形リストのようなデータ構造は、int型以外にもfloat,double,boolなどいろいろな型を扱うことができると便利です。いろいろな数値型を扱えるように改造してみたいと思います。

Nodeクラスのテンプレートクラス化

Nodeに好きな型を入れられるようにするため、テンプレートクラスにしてみます。
テンプレートクラスは、実装部分をヘッダに記述しなければいけないので、hppファイルとして一つにまとめてみます。

Node.hpp

ヘッダ部分です。templateによって一般的な型Typeを要素として持つことができるようにするため、intと書かれていた部分をTypeに変更します。

#ifndef __Node_H
#define __Node_H
#define TEMPLATE template<class Type>

TEMPLATE
class Node
{
public:
	Node();
	~Node();
	Node*& next();	//次のノードのアドレスを取得する
	Node*& prev();	//前のノードのアドレスを取得する
	Type& data();		//ノードが保持するデータを取得する

	void print();//メンバ変数を出力する(テスト用)
private:
	Node* m_next;	//次のノードのアドレス
	Node* m_prev;	//前のノードのアドレス
	Type m_data;	//ノードが保持するデータ
};

メンバ関数のテンプレート関数化

実装部分もNode.hppに記述します。テンプレート化のコードを追加して、intをtypeへ変更します。変更点は、各メンバ関数をテンプレート化するので、templateを付けます。メンバ関数が定義されるクラスのスコープは、Type型によって決まるので、Node→Nodeに書き換えます。さらに、引数や返却型がNodeに依存する場合もNode→Nodeに直します。

Node.hppの続き
TEMPLATE
Node<Type>::Node(void):
m_next(0),
m_prev(0),
m_data(0)
{
}

TEMPLATE
Node<Type>::~Node(void)
{
}

TEMPLATE
Node<Type>*& Node<Type>::next(){
	return m_next;
}

TEMPLATE
Node<Type>*& Node<Type>::prev(){
	return m_prev;
}

TEMPLATE
Type& Node<Type>::data(){
	return m_data;
}

#include <iostream>
using namespace std;
TEMPLATE
void Node<Type>::print(){
		cout <<"prev["<<m_prev<<"]\t";
		cout <<"["<<this<<",data="<<m_data<<"]\t";
		cout <<"next["<<m_next<<"]";
}
#endif

Listクラスのテンプレート化

Nodeクラスと同様にListクラスもテンプレートクラスに書き換えることにします。templateによってリストの要素の型を指定します。例えばrootノードなどのように、リストが扱うノードは、Node型にするとよいでしょう。リストのヘッダ、実装部分も同様にList.hppとして一つのファイルにまとめる必要があります。

List.hpp
#ifndef __List_H
#define __List_H

#include "Node.hpp"

#define TEMPLATE template<class Type>

TEMPLATE
class List
{
public:
	List(void);
	~List(void);
	void push_back(const Type& data);	//要素を最後尾に追加する
	void pop_back();			//最後の要素を削除する
	void clear();				//全てのノードを削除する
	Type& operator[](unsigned int i);	//i番目の要素を取り出す

	void print();				//要素を表示する
private:
	void insert_next(Node<Type>* node,const Type& data);	//指定したnodeの後に追加
	void insert_prev(Node<Type>* node,const Type& data);	//指定したnodeの前に追加
	void erase(Node<Type>* node);				//指定したノードを削除する
	Node<Type>* node(unsigned int i);			//i番目のノードを取得する
	Node<Type>* m_root;
	int m_size;
};

テンプレートListクラスの実装部分

List.hppの続き
TEMPLATE
List<Type>::List(void):
m_size(0)
{
	m_root = new Node<Type>();
	m_root->next() = m_root;	//rootノードの前後を自分自身にしておく
	m_root->prev() = m_root;
}
TEMPLATE
List<Type>::~List(void)
{
	clear();
	delete m_root;
}
TEMPLATE
Type& List<Type>::operator[](unsigned int i){
	return node(i)->data();
}
TEMPLATE
void List<Type>::push_back(const Type& data){
	insert_prev(m_root,data);
}
TEMPLATE
void List<Type>::pop_back(){
	erase(m_root->prev());
}
TEMPLATE
void List<Type>::clear(){
	for(Node<Type>* node=m_root->next();node!=m_root;node=m_root->next()){
		erase(node);
	}
	m_size=0;
}
TEMPLATE
void List<Type>::insert_next(Node<Type>* node,const Type& data){
	if(node==0){
		return;
	}
	Node<Type>* new_node=new Node<Type>();//新たに追加したnode

	new_node->prev()=node;
	new_node->next()=node->next();
	node->next()->prev()=new_node;
	node->next()=new_node;
	new_node->data()=data;	//追加したnodeの値を設定
	m_size++;
}
TEMPLATE
void List<Type>::insert_prev(Node<Type>* node,const Type& data){
	if(node==0){
		return;
	}
	Node<Type>* new_node=new Node<Type>();//新たに追加したnode

	new_node->prev()=node->prev();
	new_node->next()=node;
	node->prev()->next()=new_node;
	node->prev()=new_node;
	new_node->data()=data;//追加したnodeの値を設定
	m_size++;
}
TEMPLATE
void List<Type>::erase(Node<Type>* node){
	if(node==0 || node==m_root){	//rootは削除しない
		return;
	}
	node->prev()->next()=node->next();
	node->next()->prev()=node->prev();
	delete node;
	m_size--;
}
TEMPLATE
Node<Type>* List<Type>::node(unsigned int i){
	int count=0;
	for(Node<Type>* node=m_root->next();node!=m_root;node=node->next()){
		if(count==i){
			return node;
		}
		count++;
	}
	return m_root;//out of range
}

#include <iostream>
using namespace std;
//要素を表示する
TEMPLATE
void List<Type>::print(){
	cout <<"(root) "<<"\t\t";
	m_root->print();	cout<<endl;
	int count=0;
	for(Node<Type>* node=m_root->next();node!=m_root;node=node->next()){
		cout <<"(node"<<count<<") "<<"\t";
		node->print();	cout<<endl;
		count++;
	}
}
#endif

リストクラスの利用

float型でテストした例は下のようになります。

TestList.cpp
#include "List.hpp"
#include <iostream>
using namespace std;

int main(){
 	List<float> list;

	const float x=11.0f;
	list.print();	cout << endl;
	list.push_back(x);
	list.print();	cout << endl;
	list.push_back(2.2f);
	list.print();	cout << endl;
	list.push_back(3.2f);
	list.print();	cout << endl;

	list.pop_back();
	list.print();		cout << endl;
	cout<<list[1]<<endl;;
	
	list.clear();
	list.print();	cout << endl;

	list.pop_back();
	list.print();	cout << endl;
	cout<<(list[2]=1.09f)<<endl;;

	return 0;
}


(root) prev[00888FC8] [00888FC8,data=0] next[00888FC8]

(root) prev[00882328] [00888FC8,data=0] next[00882328]
(node0) prev[00888FC8] [00882328,data=11] next[00888FC8]

(root) prev[00882360] [00888FC8,data=0] next[00882328]
(node0) prev[00888FC8] [00882328,data=11] next[00882360]
(node1) prev[00882328] [00882360,data=2.2] next[00888FC8]

(root) prev[00882398] [00888FC8,data=0] next[00882328]
(node0) prev[00888FC8] [00882328,data=11] next[00882360]
(node1) prev[00882328] [00882360,data=2.2] next[00882398]
(node2) prev[00882360] [00882398,data=3.2] next[00888FC8]

(root) prev[00882360] [00888FC8,data=0] next[00882328]
(node0) prev[00888FC8] [00882328,data=11] next[00882360]
(node1) prev[00882328] [00882360,data=2.2] next[00888FC8]

2.2
(root) prev[00888FC8] [00888FC8,data=0] next[00888FC8]

(root) prev[00888FC8] [00888FC8,data=0] next[00888FC8]

1.09