Question

stl vector 内部是用什么实现

Answer 1

　　《STL系列》之vector原理及实现
　　最近忙得蛋疼，但还是想写点属于自己的东西。也不知道写点啥，最后决定试着自己实现STL中常用的几个集合，一来加深自己对STL的理解，二来看看自己是否有这个能力实现。实现目标就是：1能和STL兼容；2最大化的实现STL中的接口并保持一致。即将STL中的集合换成我写的也能用。这篇博客介绍的是vector的原理及实现。
　　先把vector的大致实现说一下，后面会给出完整的源码。
　　新增元素：Vector通过一个连续的数组存放元素，如果集合已满，在新增数据的时候，就要分配一块更大的内存，将原来的数据复制过来，释放之前的内存，在插入新增的元素。插入新的数据分在最后插入push_back和通过迭代器在任何位置插入，这里说一下通过迭代器插入，通过迭代器与第一个元素的距离知道要插入的位置，即int index=iter-begin()。这个元素后面的所有元素都向后移动一个位置，在空出来的位置上存入新增的元素。
　　

　　void insert(const_iterator iter,const T& t )
{
int index=iter-begin();
if (index<size_)
{
if (size_==capacity_)
{
int capa=calculateCapacity();
newCapacity(capa);
}
memmove(buf+index+1,buf+index,(size_-index)*sizeof(T));
buf[index]=t;
size_++;
}
}

　　
　　删除元素：删除和新增差不多，也分两种，删除最后一个元素pop_back和通过迭代器删除任意一个元素erase(iter)。通过迭代器删除还是先找到要删除元素的位置，即int index=iter-begin();这个位置后面的每个元素都想前移动一个元素的位置。同时我们知道erase不释放内存只初始化成默认值。
　　删除全部元素clear：只是循环调用了erase，所以删除全部元素的时候，不释放内存。内存是在析构函数中释放的。
　　

　　iterator erase(const_iterator iter)
{
int index=iter-begin();
if (index<size_ && size_>0)
{
memmove(buf+index ,buf+index+1,(size_-index)*sizeof(T));
buf[--size_]=T();
}
return iterator(iter);
}

　　
　　迭代器iteraotr是STL的一个重要组成部分,通过iterator可以很方便的存储集合中的元素.STL为每个集合都写了一个迭代器, 迭代器其实是对一个指针的包装,实现一些常用的方法,如++,--,!=,==,*,->等, 通过这些方法可以找到当前元素或是别的元素. vector是STL集合中比较特殊的一个,因为vector中的每个元素都是连续的,所以在自己实现vector的时候可以用指针代替,如typedef T* iterator;typedef const T* const_iterator，如果STL中的函数能方便的操作自己写的集合，实现的迭代器最好继承std::iterator<std::forward_iterator_tag,T>。我实现vector的迭代器大概是这个样子：
　　template<typename T>
　　class viterator:public std::iterator<std::forward_iterator_tag,T>{}
　　后面会给出完整的代码，std::iterator<std::forward_iterator_tag,T>的源码如下：

　　template<class _Category,
class _Ty,
class _Diff = ptrdiff_t,
class _Pointer = _Ty *,
class _Reference = _Ty&>
struct iterator
{ // base type for all iterator classes
typedef _Category iterator_category;
typedef _Ty value_type;
typedef _Diff difference_type;
typedef _Diff distance_type; // retained
typedef _Pointer pointer;
typedef _Reference reference;
};

　　
　　Iterator其中没有任何成员，只是定义了一组类型，所以继承它并不会让你的struct变大，这组类型是STL的内部契约，STL中的函数假设每个迭代器都定义了这些类型，所以只要你的迭代器定义了这些类型，就可以和STL函数集合一起使用。
　　我的vector实现源码如下：
　　View Code
　　
　　实例代码级运行结果如下：

　　struct Point
{
Point(int x_=0,int y_=0):x(x_),y(y_){}
int x,y;
};

bool operator<(const Point& p1,const Point& p2)
{
if(p1.x<p2.x)
{
return true;
}else if(p1.x>p2.x)
{
return false;
}
return p1.y<p2.y;
}

void cvectorTest()
{
cvector<Point> vect;
for (int i=0;i<10;i++)
{
Point p(i,i);
vect.push_back(p);
}

cvector<Point>::iterator iter=vect.begin();
while (iter!=vect.end())
{
cout<< "[" << iter->x << " " << iter->y <<"], ";
++iter;
}
iter=vect.begin()+5;
vect.insert(iter,Point(55,55));
iter=vect.end()-3;
vect.insert(iter,Point(77,77));
cout<<endl<<endl<<"插入两个元素后："<<endl;
iter=vect.begin();
while (iter!=vect.end())
{
cout<< "[" << iter->x << " " << iter->y <<"], ";
++iter;
}
std::sort(vect.begin(),vect.end());
cout<<endl<<endl<<"排序后："<<endl;
iter=vect.begin();
while (iter!=vect.end())
{
cout<< "[" << iter->x << " " << iter->y <<"], ";
++iter;
}
vect.erase(vect.begin()+10);
vect.erase(vect.begin()+10);
cout<<endl<<endl<<"删除之前新增的两个元素"<<endl;
iter=vect.begin();
while (iter!=vect.end())
{
cout<< "[" << iter->x << " " << iter->y <<"], ";
++iter;
}
vect.clear();
cout<<endl<<endl<<"执行clear之后"<<endl;
cout<<"size="<<vect.size()<<",capacity="<<vect.capacity();

cvector<Point> vect1;
for (int i=10;i<20;i++)
{
Point p(i,i);
vect1.push_back(p);
}
cout<<endl<<endl<<"从别的cvector复制数据:"<<endl;

cvector<Point> vect2(vect1.begin(),vect1.end());
vect2.pop_back();
vect2.pop_back();
for(int i=0;i<vect2.size();i++)
{
cout<<"["<<vect2[i].x<<","<<vect2[i].y<<"], ";
}

cout<<endl;
}

　　之后还会有list，set，map等的实现，敬请期待......

Answer 2

　《STL系列》之vector原理及实现
　　最近忙得蛋疼，但还是想写点属于自己的东西。也不知道写点啥，最后决定试着自己实现STL中常用的几个集合，一来加深自己对STL的理解，二来看看自己是否有这个能力实现。实现目标就是：1能和STL兼容；2最大化的实现STL中的接口并保持一致。即将STL中的集合换成我写的也能用。这篇博客介绍的是vector的原理及实现。
　　先把vector的大致实现说一下，后面会给出完整的源码。
　　新增元素：Vector通过一个连续的数组存放元素，如果集合已满，在新增数据的时候，就要分配一块更大的内存，将原来的数据复制过来，释放之前的内存，在插入新增的元素。插入新的数据分在最后插入push_back和通过迭代器在任何位置插入，这里说一下通过迭代器插入，通过迭代器与第一个元素的距离知道要插入的位置，即int index=iter-begin()。这个元素后面的所有元素都向后移动一个位置，在空出来的位置上存入新增的元素。
　　

　　void insert(const_iterator iter,const T& t )
{
int index=iter-begin();
if (index<size_)
{
if (size_==capacity_)
{
int capa=calculateCapacity();
newCapacity(capa);
}
memmove(buf+index+1,buf+index,(size_-index)*sizeof(T));
buf[index]=t;
size_++;
}
}

　　
　　删除元素：删除和新增差不多，也分两种，删除最后一个元素pop_back和通过迭代器删除任意一个元素erase(iter)。通过迭代器删除还是先找到要删除元素的位置，即int index=iter-begin();这个位置后面的每个元素都想前移动一个元素的位置。同时我们知道erase不释放内存只初始化成默认值。
　　删除全部元素clear：只是循环调用了erase，所以删除全部元素的时候，不释放内存。内存是在析构函数中释放的。
　　

　　iterator erase(const_iterator iter)
{
int index=iter-begin();
if (index<size_ && size_>0)
{
memmove(buf+index ,buf+index+1,(size_-index)*sizeof(T));
buf[--size_]=T();
}
return iterator(iter);
}