10年前の学生時代に勉強のために作ったSTLのListをまねたコードを晒す
自分の今日のために、どのように実装することでSTLのListのような機能が出来るのかお試し感覚で作ったクラスです。
稚拙ですみませんが、iteratorのような機能を組込むときに、内部をどのように実装すると実現できるかのノウハウを確認するために最適かと思います。
リストをインクリメント演算や配列の形でアクセス出来る機能を自作できるようになれば、ポインタの概念は捉えたも同然だと思いますよ。
注: 学生時代のコードですので、稚拙かもしれませんがご容赦ください。
list.cpp
template < typename DataClass > class CListData
{
DataClass m_Data;
public:
CListData< DataClass > *m_Next;
CListData< DataClass > *m_Prev;
//**********************************************************************************
// CListData()
//
// 引数:
// なし
//
// コンストラクタ
//
//**********************************************************************************
CListData()
{
this->m_Next = NULL;
this->m_Prev = NULL;
}
//**********************************************************************************
// CListData( DataClass data )
//
// 引数:
// data: データ
//
// コンストラクタ
//
//**********************************************************************************
CListData( DataClass data )
{
this->m_Data = data;
this->m_Next = NULL;
this->m_Prev = NULL;
}
//**********************************************************************************
// デストラクタ
//**********************************************************************************
~CListData()
{
}
//**********************************************************************************
// GetData()
//
// 引数:
// なし
//
// 戻り値:
// なし
//
// データの取得
//
//**********************************************************************************
DataClass GetData()
{
return this->m_Data;
}
};
template < typename DataClass > class CMyList
{
CListData< DataClass >* m_list;
public:
CListData< DataClass >* m_pBegin;
CListData< DataClass >* m_pEnd;
unsigned long m_size;
class iterator
{
friend class iterator;
private:
CListData< DataClass >* m_Data;
CListData< DataClass >* m_Next;
CListData< DataClass >* m_Prev;
public:
//**********************************************************************************
// iterator()
//
// 引数:
// なし
//
// コンストラクタ
//
//**********************************************************************************
iterator()
{
m_Data = NULL;
}
//**********************************************************************************
// iterator( CListData< DataClass > *Data, char pattern = 0 )
//
// 引数:
// Data: データ
// pattern: データをアクセスするパターン(省略時: 0)
// 0: Dataそのものにアクセス
// 0x01: Dataの次のデータにアクセス
//
// コンストラクタ
//
//**********************************************************************************
iterator( CListData< DataClass > *Data, char pattern = 0 )
{
if( !pattern )
{
this->m_Data = Data;
if( this->m_Data )
{
this->m_Next = this->m_Data->m_Next;
this->m_Prev = this->m_Data->m_Prev;
}
}
else
{
this->m_Data = Data->m_Next;
if( Data )
{
this->m_Next = NULL;
this->m_Prev = Data;
}
}
}
//**********************************************************************************
// operator ++()
//
// 引数:
// なし
//
// 戻り値:
// 自分自身を返す
//
// リストを次へ移動する
//
//**********************************************************************************
iterator& operator ++()
{
if( this->m_Next )
this->m_Data = this->m_Next;
else if( this->m_Data )
this->m_Data = this->m_Data->m_Next;
if( this->m_Data )
{
this->m_Next = this->m_Data->m_Next;
this->m_Prev = this->m_Data->m_Prev;
}
return *this;
}
//**********************************************************************************
// operator ++( int tmp )
//
// 引数:
// tmp: 意味はない
//
// 戻り値:
// 自分自身を返す
//
// リストを次へ移動する
//
//**********************************************************************************
iterator& operator ++( int tmp )
{
if( this->m_Next )
this->m_Data = this->m_Next;
else if( this->m_Data )
this->m_Data = this->m_Data->m_Next;
if( this->m_Data )
{
this->m_Next = this->m_Data->m_Next;
this->m_Prev = this->m_Data->m_Prev;
}
return *this;
}
//**********************************************************************************
// operator --()
//
// 引数:
// なし
//
// 戻り値:
// 自分自身を返す
//
// リストを前へ移動する
//
//**********************************************************************************
iterator& operator --()
{
if( this->m_Prev )
this->m_Data = this->m_Prev;
if( this->m_Data )
{
this->m_Next = this->m_Data->m_Next;
this->m_Prev = this->m_Data->m_Prev;
}
return *this;
}
//**********************************************************************************
// operator --( int tmp )
//
// 引数:
// tmp: 意味はない
//
// 戻り値:
// 自分自身を返す
//
// リストを前へ移動する
//
//**********************************************************************************
iterator& operator --( int tmp )
{
if( this->m_Prev )
this->m_Data = this->m_Prev;
if( this->m_Data )
{
this->m_Next = this->m_Data->m_Next;
this->m_Prev = this->m_Data->m_Prev;
}
return *this;
}
//**********************************************************************************
// operator *()
//
// 引数:
// なし
//
// 戻り値:
// 今さしているデータの中身を返す
//
// リストのデータの取得
//
//**********************************************************************************
DataClass operator *()
{
return this->m_Data->GetData();
}
//**********************************************************************************
// operator =( CListData< DataClass > *Data )
//
// 引数:
// Data: データ
//
// 戻り値:
// なし
//
// データのリンク先を変える
//
//**********************************************************************************
void operator =( CListData< DataClass > *Data )
{
this->m_Data = Data;
}
//**********************************************************************************
// operator !=( iterator &Itor )
//
// 引数:
// Itor: ノード
//
// 戻り値:
// true: 一致した
// false: 一致しない
//
// 一致しないか確認する
//
//**********************************************************************************
bool operator !=( iterator &Itor )
{
if( Itor.m_Data )
return this->m_Data != Itor.m_Data;
else
return this->m_Data != NULL;
}
};
//**********************************************************************************
// CMyList()
//
// 引数:
// なし
//
// コンストラクタ
//
//**********************************************************************************
CMyList()
{
this->m_list = NULL;
this->m_pBegin = this->m_pEnd = NULL;
this->m_size = 0;
}
//**********************************************************************************
// デストラクタ
//**********************************************************************************
~CMyList()
{
clear();
}
//**********************************************************************************
// push_front( DataClass data )
//
// 引数:
// data: データ
//
// 戻り値:
// なし
//
// データをリストの先頭に入れる
//
//**********************************************************************************
void push_front( DataClass data )
{
//先頭に入れる
if( this->m_list )
{
this->m_list->m_Prev = new CListData< DataClass >( data );
this->m_list->m_Prev->m_Next = this->m_list;
this->m_list = this->m_list->m_Prev;
}
else
{
this->m_list = new CListData< DataClass >( data );
}
this->m_pBegin = this->m_list;
if( !this->m_size )
this->m_pEnd = this->m_pBegin;
this->m_size ++;
}
//**********************************************************************************
// push_back( DataClass data )
//
// 引数:
// data: データ
//
// 戻り値:
// なし
//
// データをリストの後尾に入れる
//
//**********************************************************************************
void push_back( DataClass data )
{
//後尾に入れる
if( this->m_pEnd )
{
//双方向にリンクする
this->m_pEnd->m_Next = new CListData< DataClass >( data );
this->m_pEnd->m_Next->m_Prev = this->m_pEnd;
this->m_pEnd = this->m_pEnd->m_Next;
}
else
{
//まだデータが無いので先頭に入れる
this->m_list = new CListData< DataClass >( data );
this->m_pBegin = this->m_list;
this->m_pEnd = this->m_list;
}
this->m_size ++;
}
//**********************************************************************************
// begin()
//
// 引数:
// なし
//
// 戻り値:
// リストの最前列ノード
//
// リストの先頭データを渡す
//
//**********************************************************************************
iterator begin()
{
iterator itor( this->m_pBegin );
return itor;
}
//**********************************************************************************
// end()
//
// 引数:
// なし
//
// 戻り値:
// リストの最後尾ノード
//
// リストの後尾データを渡す
//
//**********************************************************************************
iterator end()
{
if( this->m_pEnd )
return iterator( this->m_pEnd, 1<<1 );
return iterator();
}
//**********************************************************************************
// erase( iterator &Itor )
//
// 引数:
// Itor: 削除したいデータを持つノード
//
// 戻り値:
// なし
//
// 対象となるデータを削除
//
//**********************************************************************************
void erase( iterator &Itor )
{
CListData< DataClass >* listdata = this->m_list;
char flag = NULL;
//検索
while( listdata != NULL )
{
if( listdata->GetData() == *Itor )
{
flag |= 1<<1;
break;
}
listdata = listdata->m_Next;
}
if( flag & 1<<1 )
{
//データがあった
//どの位置のデータか
if( listdata->m_Next == NULL )
flag |= 1<<2; //後ろに何も無いとき
if( listdata->m_Prev == NULL )
flag |= 1<<3; //前に何も無いとき
if( flag & 1<<2 && flag & 1<<3 ) //前後に何も無いデータ
{
this->m_pBegin = this->m_pEnd = NULL;
this->m_list = NULL;
delete listdata;
listdata = NULL;
Itor = NULL;
}
else if( flag & 1<<3 ) //一番前のデータ
{
this->m_pBegin = listdata->m_Next;
listdata->m_Next->m_Prev = NULL;
this->m_list = listdata->m_Next;
delete listdata;
listdata = NULL;
}
else if( flag & 1<<2 ) //一番後ろのデータ
{
this->m_pEnd = listdata->m_Prev;
listdata->m_Prev->m_Next = NULL;
delete listdata;
listdata = NULL;
}
else if( flag & 1<<1 ) //前後にデータがある
{
listdata->m_Prev->m_Next = listdata->m_Next;
listdata->m_Next->m_Prev = listdata->m_Prev;
delete listdata;
listdata = NULL;
}
this->m_size --;
}
}
//**********************************************************************************
// clear()
//
// 引数:
// なし
//
// 戻り値:
// なし
//
// リストデータをすべて削除
//
//**********************************************************************************
void clear()
{
for( iterator Itor = this->begin(); Itor != this->end(); Itor++ )
erase( Itor );
}
//**********************************************************************************
// size()
//
// 引数:
// なし
//
// 戻り値:
// リストのノードの数
//
// リストの要素数を返す
//
//**********************************************************************************
unsigned long size()
{
return this->m_size;
}
//**********************************************************************************
// empty()
//
// 引数:
// なし
//
// 戻り値:
// true: 要素がない
// false: まだデータノードが残っている
//
//**********************************************************************************
bool empty()
{
return this->m_size == 0;
}
};
まとめ
既にある機能やアルゴリズムがあっても、自分で実装してみるって大事です。
基礎なので、与えられたものをそのまま使うんじゃなくて、自分ならどう書くかなって試作してみると良いですよ♪
為にならないかもしれませんが、少しでも参考になると嬉しです。。