其他数据结构通过泛化的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