其他數據結構通過泛化的Pair,Array,Chain,Auto,Tree,Graphi衍生,不獨立設計新的容器,這樣可以集中寫自己想要的目標實現.
向量 vector
0 沒有SmartPtr去控制指針,而是把所有可能的基本操作封裝到結點本身的結構體內.
1 為鏈表的小操作如插入刪除列出內部結構體函數,方便以后代碼優化,以后增加迭代器的操作就無關內存回收,因為最小粒度操作被封裝進結點本身的結構體內方法中.
2 類似python下標的智能索引,-1 是last,-2是倒數第二個,這個功能是可選的.
3 這次特意注意了命名規則,盡量簡潔而有據可查.
如果各位路過的有興趣仔細看下代碼,并且指點一二，那就非常感謝了.
/**//* vector.h :base::adt::vector */
#ifndef VECTOR__
#define VECTOR__
#pragma warning (disable: 4138)/**//* comment warning */
#include "base.h"
namespace adt
{
#define SMART_INDEX
template<typename VType>
class /**//*Adt: Double Chain Table*/ vector:public base::adt
{
public:
int smartindex(int & _i,const int& _n)
{
#ifdef SMART_INDEX
if(_n==1)
{
_i=0;
return 0;
}
if(_i<0)
{
_i=-_i;
_i=_i%_n;
_i = _n - _i;
}else
{
_i=_i%_n;
}
#endif
return 1;
}
typedef struct VNode
{
VNode*/**//*prior node*/ prev;
VNode*/**//*following node*/ next;
VType elem;
int extend_prev(VType _prev_elem)
{
prev=new VNode;
prev->elem=_prev_elem;
prev->next=this;
return 1;
}
int extend_prev()
{
prev=new VNode;
prev->next=this;
return 1;
}
int extend_next(VType _nextend_elem)
{
next=new VNode;
next->elem=_nextend_elem;
next->prev=this;
return 1;
}
int extend_next()
{
next=new VNode;
next->prev=this;
return 1;
}
int inst_node(const VType &_inst_elem)
/**//* inserts a node between obj and obj's following */
{
VNode* _ins_node=new VNode;
_ins_node->elem=_inst_elem;
_ins_node->next=this->next;
_ins_node->next->prev=_ins_node;
this->next=_ins_node;
_ins_node->prev=this;
return 1;
}
int remove()
/**//* deletes the middle node and close its prev and next */
{
if(!this->prev||!this->next)
{
return 0;
}
this->prev->next=this->next;
this->next->prev=this->prev;
delete this;
return 1;
}
};
public :
VNode* head;
VNode* tail;
VNode* p;
int n;
vector(VType *_init_elem=0,int _len=0)
{
if(_len<=-1)return;
p=head=new VNode;
p->prev=0;
for(int j=0;j!=_len;j++)
{
p->extend_next(_init_elem[j]);
p=p->next;
}
p->extend_next();
n=_len;
}
int rebirth(VType *_re_init_elem,int _len=0)
{
vector(_re_init_elem,_len);
return 1;
}
int index(VType _value)
{
p=head->next;
for(int j=0;j!=n;j++)
{
if(p->elem==_value)
{
return j;
}
p=p->next;
}
return -1;
}
VType & operator [](int _i)
{
smartindex(_i,n);
p=head->next;
for(int j=0;j!=_i;j++)
{
p=p->next;
}
return p->elem;
}
int insert(int _i,VType _obj_elem)
{
p=head;
for(int j=0;j!=_i;j++)
{
p=p->next;
}
p->inst_node(_obj_elem);
++n;
return 1;
}
int isNull()
{
if(n==0)return 1;
else return 0;
}
int push(VType _obj)
{
insert(n,_obj);
return 1;
}
VType pop()
{
#ifdef TEST_OPEN
if(n==0)
TEST_THROW("Exception in vector pop-function")
#endif
return remove(-1);
}
VType remove(int _i)
{
smartindex(_i,n);
p=head->next;
for(int j=0;j!=_i;j++)
{
p=p->next;
}
VType buf=p->elem;
p->remove();
--n;
return buf;
}
void operator = (vector& _copy)
{
p=head;
_copy.p=_copy.head;
for(int i=0;i!=_copy.n;i++)
{
_copy.p=_copy.p->next;
p->extend_next(_copy.p->elem);
p=p->next;
}
p->extend_next();
n=_copy.n;
}
int free()
{
if(n==0)return 1;
for(int j=0;j!=n;j++)
{
head=head->next;
delete head->prev;
}
delete head->next;
delete head;
n=0;
p=0;
head=0;
return 1;
}
~vector()
{
free();
}
};
};
#endif