《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

{ } int index=iter-begin(); if (index0) { } return iterator(iter); memmove(buf+index ,buf+index+1,(size_-index)*sizeof(T)); buf[--size_]=T(); 迭代器 iteraotr 是 STL 的一个重要组成部分,通过 iterator 可以很方便的存储集合中的元 素.STL 为每个集合都写了一个迭代器, 迭代器其实是对一个指针的包装,实现一些常用的 方法,如++,--,!=,==,*,->等, 通过这些方法可以找到当前元素或是别的元素. vector 是 STL 集合中比较特殊的一个,因为 vector 中的每个元素都是连续的,所以在自己实现 vector 的时候可以用指针代替,如 typedef T* iterator;typedef const T* const_iterator，如 果 STL 中的函数能方便的操作自己写的集合，实现的迭代器最好继承 std::iterator。我实现 vector 的迭代器大概是这个样 子： template class viterator:public std::iterator{} 后面会给出完整的代码，std::iterator的源码如下： template struct iterator { // base type for all iterator classes typedef _Category iterator_category; typedef _Ty value_type; typedef _Diff difference_type; typedef _Diff distance_type; typedef _Pointer pointer; typedef _Reference reference; // retained }; 

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.xp2.x) { return false; } return p1.y vect; for (int i=0;i<10;i++) { Point p(i,i); vect.push_back(p); } } cvector::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<x << " " << iter->y <<"], "; ++iter; } std::sort(vect.begin(),vect.end()); cout<x << " " << iter->y <<"], "; ++iter; } vect.erase(vect.begin()+10); vect.erase(vect.begin()+10); cout<x << " " << iter->y <<"], "; ++iter; } vect.clear(); cout< vect2(vect1.begin(),vect1.end()); vect2.pop_back(); vect2.pop_back(); for(int i=0;i

{ } cout<<"["<