这个想法来自于数组链表，在数组链表中，数组的每一个元素对应一个指针，这个指针是下一个元素的index。用整数表示指针。
这是这个vector的源码：
#include <iostream>
using std::cout; template <typename T>
class Vector
{
private:
int m_block,m_size,m_asize;
int *ip,*rip;//ip:actual->visual;rip:v->a
T *tp;
void brushrip();
int partition(int,int);
void qsort(int,int); public:
Vector(int block=):m_block(block),m_asize(),m_size(),rip(NULL),ip(NULL),tp(NULL){}
// Vector(const Vector<T>& v,int block=100);
int size() const{return m_size;}
bool insert(const T& t,int pos=-,int num=);
bool erase(int pos);
bool erase(int pos,int num);
// bool thin();
T& operator[](const int key)const;
bool recover(const int const*);
int* getorder() const;
void sort();
void swap(int pos1,int pos2);
};
template <typename T>
void Vector<T>::swap(int pos1,int pos2)
{ ip[rip[pos1]]=pos2;
ip[rip[pos2]]=pos1;
int ac1=rip[pos1],ac2=rip[pos2];
rip[ip[ac1]]=ac1;
rip[ip[ac2]]=ac2;
} template <typename T>
void Vector<T>::sort()
{
qsort(,m_size-);
}
template <typename T>
void Vector<T>::qsort(int p,int r)
{
if(p<r)
{
int q=partition(p,r);
qsort(p,q-);
qsort(q+,r);
}
}
template <typename T>
int Vector<T>::partition(int p,int r)
{
T& x=tp[rip[r]];
int i=p-;
for(int j=p;j<=r-;j++)
{
if(tp[rip[j]]<x)
{
i++;
if(i!=j)swap(i,j);
}
}
if(r!=i+)swap(i+,r);
return i+;
}
template <typename T>
int* Vector<T>::getorder() const
{
if(m_size==)return NULL;
int *p=new int[m_size];
for(int i=;i<m_size;i++)p[i]=ip[i];
return p;
} template <typename T>
bool Vector<T>::recover(const int* p)
{
// if((sizeof(p)/sizeof(int))<m_size)return false;
for(int i=;i<m_size && p[i]<m_size && p[i]>=;i++)ip[i]=p[i];
brushrip();
return true;
} template <typename T>
void Vector<T>::brushrip()
{
if(m_size==){delete[] rip;rip=NULL;return;}
if(sizeof(rip)/sizeof(int)!=m_size)
{delete[] rip;rip=NULL;rip=new int[m_size];}
for(int i=;i<m_size;i++){rip[ip[i]]=i;}
} template <typename T>
bool Vector<T>::insert(const T& t,int pos,int num)
{
if(pos<)pos=m_size+pos+;
if(pos< || pos>m_size)return false;
int newblock=(m_size+num-m_asize)/m_block+;
if(newblock>)
{
m_asize+=newblock*m_block;
int *ipp=new int[m_asize];
T *tpp=new T[m_asize];
for(int i=;i<m_size;i++){tpp[i]=tp[i];ipp[i]=ip[i];}
delete[] tp;delete[] ip;
tp=tpp;ip=ipp;
}
for(int i=;i<m_size;i++)if(ip[i]>=pos)ip[i]=ip[i]+num;
for( i=;i<num;i++) {ip[i+m_size]=pos+i;tp[i+m_size]=t;}
m_size+=num;
brushrip();
return true;
} template <typename T>
bool Vector<T>::erase(int pos)
{
if( pos< || pos>=m_size)return false;
m_size--;
if(rip[pos]!=m_size)
{
T temp=tp[rip[pos]];
tp[rip[pos]]=tp[m_size];
tp[m_size]=temp;
ip[rip[pos]]=ip[m_size];
}
for(int i=;i<m_size;i++)if(ip[i]>pos)ip[i]--;
brushrip();
return true;
}
template <typename T>
bool Vector<T>::erase(int pos,int num)
{
for(int i=;i<num;i++)if(!erase(pos))return false;
return true;
} template <typename T>
T& Vector<T>::operator[](const int key)const
{
return tp[rip[key]];
} int main()
{
Vector<int> v;
v.insert(,,);
v.insert(,,);
v.insert(,,);
v.erase(,);
v.insert(,,);
v.swap(,);
cout<<"排序前:\n";
for(int i=;i<v.size();i++)cout<<v[i]<<" ";
int *p=v.getorder();
v.sort();cout<<"\n排序后:\n";
for( i=;i<v.size();i++)cout<<v[i]<<" ";
if(v.recover(p))cout<<"\n复原：\n";
for( i=;i<v.size();i++)cout<<v[i]<<" ";
cout<<"\n";
delete[] p; return ;
}
实现了operator[],快排,getorder,recover,insert,erase
内存的组织形式是这样的：
1.动态顺序存储，insert总将数据存储到顺序表的尾部。
2.另有有整型数组ip，与顺序表同长，建立数据存储的实际位置与表象未知的函数
3.数据交换的操作就不再直接操作数据本身，而是操作 数组ip
4.可以用getorder记录下数组ip，以后就可以用recover回复到这个状态了
也就是说，数据一旦被存储，他的实际位置就不再变了，变的只是 数组ip。而数组ip可以记录成不同的状态，所以这个vector可以用来做版本管理。