首页 > 代码库 > c++ 能够记录状态的vector
c++ 能够记录状态的vector
这个想法来自于数组链表，在数组链表中，数组的每一个元素对应一个指针，这个指针是下一个元素的index。用整数表示指针。
这是这个vector的源码：
1 #include <iostream> 2 using std::cout; 3 4 template <typename T> 5 class Vector 6 { 7 private: 8 int m_block,m_size,m_asize; 9 int *ip,*rip;//ip:actual->visual;rip:v->a 10 T *tp; 11 void brushrip(); 12 int partition(int,int); 13 void qsort(int,int); 14 15 public: 16 Vector(int block=100):m_block(block),m_asize(0),m_size(0),rip(NULL),ip(NULL),tp(NULL){} 17 // Vector(const Vector<T>& v,int block=100); 18 int size() const{return m_size;} 19 bool insert(const T& t,int pos=-1,int num=1); 20 bool erase(int pos); 21 bool erase(int pos,int num); 22 // bool thin(); 23 T& operator[](const int key)const; 24 bool recover(const int const*); 25 int* getorder() const; 26 void sort(); 27 void swap(int pos1,int pos2); 28 }; 29 template <typename T> 30 void Vector<T>::swap(int pos1,int pos2) 31 { 32 33 ip[rip[pos1]]=pos2; 34 ip[rip[pos2]]=pos1; 35 int ac1=rip[pos1],ac2=rip[pos2]; 36 rip[ip[ac1]]=ac1; 37 rip[ip[ac2]]=ac2; 38 } 39 40 template <typename T> 41 void Vector<T>::sort() 42 { 43 qsort(0,m_size-1); 44 } 45 template <typename T> 46 void Vector<T>::qsort(int p,int r) 47 { 48 if(p<r) 49 { 50 int q=partition(p,r); 51 qsort(p,q-1); 52 qsort(q+1,r); 53 } 54 } 55 template <typename T> 56 int Vector<T>::partition(int p,int r) 57 { 58 T& x=tp[rip[r]]; 59 int i=p-1; 60 for(int j=p;j<=r-1;j++) 61 { 62 if(tp[rip[j]]<x) 63 { 64 i++; 65 if(i!=j)swap(i,j); 66 } 67 } 68 if(r!=i+1)swap(i+1,r); 69 return i+1; 70 } 71 template <typename T> 72 int* Vector<T>::getorder() const 73 { 74 if(m_size==0)return NULL; 75 int *p=new int[m_size]; 76 for(int i=0;i<m_size;i++)p[i]=ip[i]; 77 return p; 78 } 79 80 template <typename T> 81 bool Vector<T>::recover(const int* p) 82 { 83 // if((sizeof(p)/sizeof(int))<m_size)return false; 84 for(int i=0;i<m_size && p[i]<m_size && p[i]>=0;i++)ip[i]=p[i]; 85 brushrip(); 86 return true; 87 } 88 89 template <typename T> 90 void Vector<T>::brushrip() 91 { 92 if(m_size==0){delete[] rip;rip=NULL;return;} 93 if(sizeof(rip)/sizeof(int)!=m_size) 94 {delete[] rip;rip=NULL;rip=new int[m_size];} 95 for(int i=0;i<m_size;i++){rip[ip[i]]=i;} 96 } 97 98 template <typename T> 99 bool Vector<T>::insert(const T& t,int pos,int num)100 {101 if(pos<0)pos=m_size+pos+1;102 if(pos<0 || pos>m_size)return false;103 int newblock=(m_size+num-m_asize)/m_block+1;104 if(newblock>0)105 {106 m_asize+=newblock*m_block;107 int *ipp=new int[m_asize];108 T *tpp=new T[m_asize];109 for(int i=0;i<m_size;i++){tpp[i]=tp[i];ipp[i]=ip[i];}110 delete[] tp;delete[] ip;111 tp=tpp;ip=ipp;112 }113 for(int i=0;i<m_size;i++)if(ip[i]>=pos)ip[i]=ip[i]+num;114 for( i=0;i<num;i++) {ip[i+m_size]=pos+i;tp[i+m_size]=t;}115 m_size+=num;116 brushrip();117 return true;118 }119 120 template <typename T>121 bool Vector<T>::erase(int pos)122 {123 if( pos<0 || pos>=m_size)return false;124 m_size--;125 if(rip[pos]!=m_size)126 {127 T temp=tp[rip[pos]];128 tp[rip[pos]]=tp[m_size];129 tp[m_size]=temp;130 ip[rip[pos]]=ip[m_size];131 }132 for(int i=0;i<m_size;i++)if(ip[i]>pos)ip[i]--;133 brushrip();134 return true;135 }136 template <typename T>137 bool Vector<T>::erase(int pos,int num)138 {139 for(int i=0;i<num;i++)if(!erase(pos))return false;140 return true;141 }142 143 template <typename T>144 T& Vector<T>::operator[](const int key)const145 {146 return tp[rip[key]];147 }148 149 int main()150 {151 Vector<int> v;152 v.insert(5,0,2);153 v.insert(6,0,8);154 v.insert(7,4,3);155 v.erase(3,20);156 v.insert(10,0,2);157 v.swap(1,2);158 cout<<"排序前:\n";159 for(int i=0;i<v.size();i++)cout<<v[i]<<" ";160 int *p=v.getorder();161 v.sort();cout<<"\n排序后:\n";162 for( i=0;i<v.size();i++)cout<<v[i]<<" ";163 if(v.recover(p))cout<<"\n复原：\n";164 for( i=0;i<v.size();i++)cout<<v[i]<<" ";165 cout<<"\n";166 delete[] p;167 168 return 0;169 }
实现了operator[],快排,getorder,recover,insert,erase
内存的组织形式是这样的：
1.动态顺序存储，insert总将数据存储到顺序表的尾部。
2.另有有整型数组ip，与顺序表同长，建立数据存储的实际位置与表象未知的函数
3.数据交换的操作就不再直接操作数据本身，而是操作 数组ip
4.可以用getorder记录下数组ip，以后就可以用recover回复到这个状态了
也就是说，数据一旦被存储，他的实际位置就不再变了，变的只是 数组ip。而数组ip可以记录成不同的状态，所以这个vector可以用来做版本管理。
c++ 能够记录状态的vector
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。