Lyt
posts - 16,comments - 61,trackbacks - 0

发现这里被我荒废了很久,自动肠粉--

最近在凑数据结构,发现要凑个稍微好看点的代码难度好大,模仿了.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 阅读(1758) 评论(5)  编辑 收藏 引用 所属分类: 数据结构

FeedBack:
# re: Collection::List
2009-09-23 14:56 | OwnWaterloo
如果以GP而非OOP的方式构建集合,你会发现C++的template即使没有delegate也会很爽。C#没得这么爽。   回复  更多评论
  
# re: Collection::List
2009-09-23 18:30 | 陈梓瀚(vczh)
@OwnWaterloo
我的VL++2.0推掉重写,最近再写3.0,实践了一下同时GP+OOP,最后发现可行,而且我也实现了delegate,将linq搬过来了。  回复  更多评论
  
# re: Collection::List
2009-09-23 18:35 | OwnWaterloo
@陈梓瀚(vczh)
支持推倒……  回复  更多评论
  
# re: Collection::List
2009-09-24 12:15 | 陈梓瀚(vczh)
@OwnWaterloo
原来同是宅人……  回复  更多评论
  
# re: Collection::List[未登录]
2009-09-28 11:21 | a
不用GP, 很多情况下都可以忽略Iterator,很多人用it无非是rbtree。我就喜欢直接用int遍历hash(directory), vector, list之类的。。  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理