發現這里被我荒廢了很久，自動腸粉--
最近在湊數據結構，發現要湊個稍微好看點的代碼難度好大，模仿了.NET改了自己以前的結構，憋了一天終于把可擴展的List折騰出來了
比較怪異的是迭代器iterator，怎么看怎么別扭，暫時先湊合著吧
IIterator.h
template<typename _Type>
class IIterator //迭代器
{
protected:
_Type Current;
public:
virtual ~IIterator()
{
}
virtual _Type CurrentItem()const=0; //Current是否有效
virtual void First()=0; //Current移到首位
virtual bool IsDone()const=0; //Current是否到達末尾，true的時候CurrentItem()失效
virtual bool IsFirst()const=0; //Current是否在首位
virtual bool IsLast()const=0; //Current是否到達末尾，ture的時候CurrentItem()有效
virtual bool IsAvailable()const=0; //Current是否有效
virtual void MoveNext()=0; //Current移到下一位置
};
template<typename _Type>
class IForwordIterator : public IIterator<_Type> //單向迭代器
{
public:
virtual ~IForwordIterator()
{
}
virtual _Type CurrentItem()const=0; //Current是否有效
virtual void First()=0; //Current移到首位
virtual bool IsDone()const=0; //Current是否到達末尾，true的時候CurrentItem()失效
virtual bool IsFirst()const=0; //Current是否在首位
virtual bool IsLast()const=0; //Current是否到達末尾，ture的時候CurrentItem()有效
virtual bool IsAvailable()const=0; //Current是否有效
virtual void MoveNext()=0; //Current移到下一位置
};
template<typename _Type>
class IBidirectionalIterator : public IIterator<_Type> //雙向迭代器
{
public:
virtual ~IBidirectionalIterator()
{
}
virtual _Type CurrentItem()const=0; //Current是否有效
virtual void First()=0; //Current移到首位
virtual bool IsDone()const=0; //Current是否到達末尾，true的時候CurrentItem()失效
virtual bool IsFirst()const=0; //Current是否在首位
virtual bool IsLast()const=0; //Current是否到達末尾，ture的時候CurrentItem()有效
virtual bool IsAvailable()const=0; //Current是否有效
virtual void MoveNext()=0; //Current移到下一位置
virtual void MovePrev()=0; //Current移到前一位置
};
template<typename _Type>
class IRandomIterator : public IIterator<_Type> //隨機迭代器
{
public:
virtual ~IRandomIterator()
{
}
virtual _Type CurrentItem()const=0; //Current是否有效
virtual void First()=0; //Current移到首位
virtual bool IsDone()const=0; //Current是否到達末尾，true的時候CurrentItem()失效
virtual bool IsFirst()const=0; //Current是否在首位
virtual bool IsLast()const=0; //Current是否到達末尾，ture的時候CurrentItem()有效
virtual bool IsAvailable()const=0; //Current是否有效
virtual void MoveNext()=0; //Current移到下一位置
virtual void MovePrev()=0; //Current移到前一位置
virtual void SkipPrev(const int n)=0; //Current前移n位
virtual void SkipNext(const int n)=0; //Current后移n位
};
template<typename _Type>
class IIterative //可迭代的
{
public:
virtual ~IIterative()
{
}
virtual AutoPtr<IIterator<_Type>> CreateIterator()const=0; //返回迭代器
};ListIterator
template<typename _Type>
class ListIterator : public IRandomIterator<_Type> //List迭代器
{
public:
const List<_Type>* Data;
int Index;
ListIterator(const List<_Type>* Object)
{
if (!Object || Object->IsEmpty()) throw L"List迭代器初始化出錯";
else
{
Data=Object;
Index=0;
}
}
ListIterator(const ListIterator<_Type>& Object)
{
Data=Object.Data;
Index=Object.Index;
Current=Object.Current;
}
virtual ~ListIterator()
{
}
virtual _Type CurrentItem()const //Current是否有效
{
if (IsAvailable()) return Current;
else throw L"非法訪問當前元素";
}
virtual void First() //Current移到首位
{
if (Data->IsEmpty()) throw L"List為空";
else
{
Index=0;
Current=Data->operator [](0);
}
}
virtual bool IsDone()const //Current是否到達末尾，true的時候CurrentItem()失效
{
return Index>=Data->GetCount();
}
virtual bool IsFirst()const //Current是否在首位
{
return Index==0;
}
virtual bool IsLast()const //Current是否到達末尾，ture的時候CurrentItem()有效
{
return Index==Data->GetCount()-1;
}
virtual bool IsAvailable()const //Current是否有效
{
return (Index>=0 && Index<=Data->GetCount()-1);
}
virtual void MoveNext() //Current移到下一位置
{
++Index;
if (IsAvailable()) Current=Data->operator [](Index);
}
virtual void MovePrev() //Current移到前一位置
{
--Index;
if (IsAvailable()) Current=Data->operator [](Index);
}
virtual void SkipPrev(const int n) //Current前移n位
{
Index-=n;
if (IsAvailable()) Current=Data->operator [](Index);
}
virtual void SkipNext(const int n) //Current后移n位
{
Index+=n;
if (IsAvailable()) Current=Data->operator [](Index);
}
};
ICollecion.h
template<typename _Type>
class ICollection : public IIterative<_Type>
{
protected:
int Count; //元素個數
public:
virtual ~ICollection()
{
}
virtual AutoPtr<IIterator<_Type>> CreateIterator()const=0; //返回迭代器，繼承自IIterative
virtual const int GetCount()const=0; //返回元素個數
virtual bool IsEmpty()const=0; //是否為空
virtual bool Add(const _Type& Object)=0; //從尾部添加元素
virtual void Clear()=0; //刪除所有元素
virtual bool Contains(const _Type& Object)const=0; //是否包含指定元素
virtual bool Remove(const _Type& Object)=0; //刪除指定元素，若有多個，則刪除第一個
};
IList.h
template<typename _Type>
class IList : public ICollection<_Type>
{
public:
virtual ~IList()
{
}
virtual AutoPtr<IIterator<_Type>> CreateIterator()const=0; //返回迭代器，繼承自IIterative
virtual const int GetCount()const=0; //返回元素個數，繼承自ICollection
virtual bool IsEmpty()const=0; //是否為空，繼承自ICollection
virtual bool Add(const _Type& Object)=0; //從尾部添加元素，繼承自ICollection
virtual void Clear()=0; //刪除所有元素，繼承自ICollection
virtual bool Contains(const _Type& Object)const=0; //是否包含指定元素，繼承自ICollection
virtual bool Remove(const _Type& Object)=0; //刪除指定元素，若有多個，則刪除第一個，繼承自ICollection
virtual int IndexOf(const _Type& Object)const=0; //返回指定元素所在位置，若不存在返回-1，若有多個，返回第一個
virtual bool Insert(const int Index, const _Type& Object)=0; //在指定位置插入指定元素
virtual bool RemoveAt(const int Index)=0; //在指定位置刪除元素
};
List.h
template<typename _Type>
class List : public IList<_Type>
{
private:
bool Grow(); //如果Capacity有增大，則返回真
void Update(); //Capacity增大導致Items需要更新
protected:
_Type* Items;
int Capacity; //List可容納元素個數
static const int GRAW_CAPACITY; //List每次增大的容量
public:
bool IsFixedSize; //List大小是否固定
List(const bool Fixed=false);
List(const int ObjectCount, const bool Fixed=false);
List(const List<_Type>& Object);
virtual ~List();
virtual AutoPtr<IIterator<_Type>> CreateIterator()const; //返回迭代器，繼承自IIterative
virtual void Clear(); //刪除所有元素，繼承自ICollection
virtual const int GetCount()const; //返回元素個數，繼承自ICollection
virtual int IndexOf(const _Type& Object)const; //返回指定元素所在位置，若不存在返回-1，繼承自IList
virtual int LastIndexOf(const _Type& Object)const //返回指定元素所在位置，若不存在返回-1，若有多個，返回最后一個
virtual bool IsEmpty()const; //是否為空，繼承自ICollection
virtual bool Add(const _Type& Object); //從List尾部添加元素，繼承自ICollection
virtual bool Add(const List<_Type>& Object); //在List末尾添加列表
virtual bool Contains(const _Type& Object)const; //是否包含指定元素，繼承自ICollection
virtual bool Remove(const _Type& Object); //刪除指定元素，若有多個，則刪除第一個，繼承自ICollection
virtual bool Remove(const int Index, const int n); //從Index開始刪除n個元素
virtual bool RemoveAt(const int Index); //在指定位置刪除元素，繼承自IList
virtual bool Insert(const int Index, const _Type& Object); //在指定位置插入指定元素，繼承自IList
virtual bool Insert(const int Index, const List<_Type>& Object); //從Index開始插入Object
virtual List<_Type> Sub(const int Index, const int n)const; //從Index開始取n個元素
virtual List<_Type> Left(const int n)const; //取左邊n個元素
virtual List<_Type> Right(const int n)const; //取右邊n個元素
_Type operator[](const int Index)const;
_Type& operator[](const int Index);
List<_Type> operator=(const List<_Type>& Object);
bool operator==(const List<_Type>& Object)const;
bool operator!=(const List<_Type>& Object)const;
List<_Type> operator+(const _Type& Object)const;
List<_Type> operator+(const List<_Type>& Object)const;
};
例子：
void Print(AutoPtr<ListIterator<int>> Iterator)
{
for (Iterator->First(); !Iterator->IsDone(); Iterator->MoveNext()) cout<<Iterator->CurrentItem()<<" ";
cout<<endl;
}
void main(int argc , char* argv[])
{
setlocale(LC_ALL,"chs");
List<int> A(1);
A[0]=1;
AutoPtr<ListIterator<int>> Iterator=A.CreateIterator();
Print(Iterator);
A.Add(2);
cout<<"After A.Add(2) : ";
Print(Iterator);
if (A.Contains(1)) cout<<"A contains 1"<<endl;
if (!A.Contains(3)) cout<<"A doesn't contain 3"<<endl;
cout<<"index of 1 is "<<A.IndexOf(1)<<endl;
cout<<"index of 3 is "<<A.IndexOf(3)<<endl;
A.Insert(0,0);
cout<<"After A.Insert(0,0) : ";
Print(Iterator);
A.Insert(1,3);
cout<<"After A.Insert(1,3) : ";
Print(Iterator);
A.RemoveAt(1);
cout<<"After A.RemoveAt(1) : ";
Print(Iterator);
List<int> B=A.Right(2);
A.Insert(1, B);
cout<<"After B=A.Right(2); A.Insert(1, B) : ";
Print(Iterator);
A=A.Sub(1,3);
cout<<"After A=A.Sub(1,3) : ";
Print(Iterator);
B=A.ToArray();
A=A+B;
cout<<"After B=A.ToArray(); A=A+B : ";
Print(Iterator);
cout<<"last index of 2 is "<<A.LastIndexOf(2)<<endl;
_getch();
}
結果如下：
1
After A.Add(2) : 1 2
A contains 1
A doesn't contain 3
index of 1 is 0
index of 3 is -1
After A.Insert(0,0) : 0 1 2
After A.Insert(1,3) : 0 3 1 2
After A.RemoveAt(1) : 0 1 2
After B=A.Right(2); A.Insert(1, B) : 0 1 2 1 2
After A=A.Sub(1,3) : 1 2 1
After B=A.ToArray(); A=A+B : 1 2 1 1 2 1
last index of 2 is 4
C#在用delegate的確很爽，無奈C++沒得爽，本來很天真地想實現一下功能
template<typename _Type>
class List : public IList<_Type>
{
template<typename T>
typedef bool Predicate(T& Object);
bool Exists(Predicate<_Type> Match)
{
if (Match(*this)) return true;
else return false;
}
};
網上搜了下，才發現C++沒有這個特性，delegate暫時湊不出來，于是折騰了個難看的辦法，沒想到還是不行，至今不知道為啥
template<typename _Type>
class List : public IList<_Type>
{
bool Exists ((bool(*Predicate)(List<_Type>& Object)) Match)
{
if (Match(*this)) return true;
else return false;
}
};
歡迎大家來噴哈～
posted on 2009-09-23 11:20
Lyt 閱讀(1960)
評論(5) 編輯 收藏 引用 所屬分類:
數據結構