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