对于STL，我们不仅学会使用STL,还要了解其底层原理，这样一来，我们就能知道什么时候用string好，什么时候用vector，什么时候用list，哪种方法效率高等等。其次了解了STL的底层原理，也助于我们的C++功力大增！
先来看看vector类的成员变量：下图是从《STL源码剖析》书中截取的
vector类的成员变量有三个，分别是iterator start、iterator finish和iterator end_of_storage。我们可以用string类的成员变量来理解这三个变量：
string 类的成员变量有：T* a , size_t _size , size_t _capacity
start也就是a,finish也就是a+_size,end_of_storage也就是a+_capacity。
源码中的vector类：
template<classT, classAlloc=alloc>classvector { public: typedefTvalue_type; typedefvalue_type*iterator; typedefconstvalue_type*const_iterator; //......protected: iteratorstart; iteratorfinish; iteratorend_of_storage; }
开始模拟实现->
为了避免冲突，先创建一个命名空间，然后在命名空间里面创建vector类：
namespacemy_vector{ template<classT>classvector { public: typedefT*iterator;//迭代器typedefconstT*const_iterator;//const迭代器private: iterator_start; iterator_finish; iteratorend_of_storge; }; }
1.构造函数：
①无参构造，将成员变量全部置为空即可
vector() :_start(nullptr) ,_finish(nullptr) ,_end_of_storge(nullptr) {}
②迭代器区间构造：
template<classInputIterator>vector(InputIteratorfirst, InputIteratorlast) :_start(nullptr) , _finish(nullptr) , _end_of_storge(nullptr) { while (first!=last) { push_back(*first); ++first; } }
其它的接口就先实现，方便后续使用：
交换接口：
voidswap(vector<T>&v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storge, v._end_of_storge); }
析构函数：
~vector() { delete[] _start; _start=_finish=_end_of_storge=nullptr; }
清空数据：
voidclear() { _finish=_start; }
③拷贝构造
传统写法：
先初始化，然后开空间，最后是将被拷贝对象的值弄到拷贝对象中。在范围for循环中，最好是引用。
vector(constvector&v) :_start(nullptr) , _finish(nullptr) , _end_of_storge(nullptr) { //先开辟空间reserve(v.capacity); for (auto&e : v) { push_back(e); } }
现代写法：
vector(constvector&v) :_start(nullptr) , _finish(nullptr) , _end_of_storge(nullptr) { vector<T>tmp(v.begin, v.end);//用迭代器区间构造，找个打工人swap(tmp); }
2.插入数据的相关函数接口：
①reserve()的模拟实现：
因为在插入数据时，不管是最初状态还是空间满的时候，都得扩容，所以就先实现reserve()。因为reserve是不会缩容的，缩容和扩容是需要代价的，而扩容是不可避免的，但是缩容就不必要了，采用空间换时间的策略。
在最初状态，_start是指向空指针的，因此在扩容的时候需要判断一下。
voidreserve(size_tn)//不止是在插入数据的时候使用，也可以单独使用 { if (n>capacity())//因为不缩容，所以判断一下，大的时候才处理 { size_toldSize=size(); T*tmp=newT[n]; if (_start)//判断一下_start是否为空，因为如果一开始的capacity是空的，然后赋值为4，但是此时的_start是nullptr，给不了数据 { //不建议用memcpy，因为它是浅拷贝，如果T是string、vector等等，就会出错//memcpy(tmp, _start, sizeof(T) * size());for (size_ti=0; i<oldSize; i++) { tmp[i] =_start[i]; } delete_start; } _start=tmp; _finish=tmp+oldSize; _end_of_storge=_start+n; } }
②size()和capacity():
实现size()和capacity()，方便操作，并且这也是需要实现的一部分。
size_tsize() const { return_finish-_start; } size_tcapacity() const { return_end_of_storge-_start; }
③push_back()：
因为_finish表示的是有效元素的个数，指向的是最后一个元素的下一个位置，因此不管是否需要扩容，尾插的位置必然是_finish指向的位置。
voidpush_back(constT&x) { if (_finish==_end_of_storge)//判断空间是否满了 { size_tnewCapacity=capacity() ==0?4 : capacity() *2; reserve(newCapacity); } *_finish=x;//直接在_finish这个位置插入数据++_finish; }
④insert接口/迭代器失效问题
void insert(iterator pos, const T& val)；
这部分很重要，因为涉及了迭代器失效问题！我们都知道，在插入数据前，我们需要进行一次判断，判断容器的容量是否满了，如果满了，则需要扩容，而问题也就发生在这里，扩容会导致迭代器失效的问题！（当然，迭代器失效的问题不仅仅会出现在这）
在扩容的时候，是重新开辟一块大的空间，然后释放原来的空间，看下图：
这样就导致了插入数据失败。解决问题呢，就是更新pos，让pos指向新空间的同一块位置：在扩容前记录一下pos距离_start的长度，在扩容后，让pos重新指向新空间的_start+len处。
//迭代器失效问题voidinsert(iteratorpos, constT&val) { assert(pos>=_start); assert(pos<_finish); if (_finish==_end_of_storge) { size_tlen=pos-_start;//算出pos距离_start的长度size_tnewCapacity=capacity() ==0?4 : capacity() *2; reserve(newCapacity); //待空间更新，就更新pos的位置，解决pos失效的问题pos=_start+len; } iteratorend=_finish-1; //挪动数据while (end>=pos) { *(end+1) =*end; --end; } *pos=val++_finish; }
当然，不扩容的话，就可能不会导致失效的问题了。其实迭代器失效，也就是野指针的问题。
解决迭代器哦失效，便是
3.实现迭代器
普通对象迭代器：
刚好，迭代器的begin刚好就是_start,end也刚好是_finish。
iteratorbegin() { return_start; } iteratorend() { return_finish; }
const迭代器：
const_iteratorbegin() const { return_start; } const_iteratorend() const { return_finish; }
4.访问接口[]：
T&operator[](size_tpos) { assert(pos<size()); return_start[pos]; } constT&operator[](size_tpos) const { assert(pos<size()); return_start[pos]; }
5.判空
当_finish等于_start的时候，说明此时容器是空的，没有空间，没有数据。
boolempty() const { return_finish==_start; }
6.resize()
对于resize(size_t n,T val = T())，是针对有效元素个数的。当n是大于容器当前的容量，则代表着是扩容+插入数据，当n小于容器的当前容量，大于当前有效元素个数，那么代表着不扩容，但是插入数据，当n小于当前容量，那么就是相当于删除数据。
那么插入的数据的话，缺省值是T()，即匿名对象，因为T有可能是string类型，是Date类型，是各种各样的类型，因此需要它的构造函数去初始化。
voidresize(size_tn, Tval=T())//T()是匿名对象，初始化resize的空间 { if (n>capacity())//扩容 { reserve(n); } if (n>size())//不扩容，但是插入数据 { //从_finish开始填数据while (_finish<_start+n) { *_finish=val; ++_finish; } } else//删除数据 { _finish=_start+n;//相当于把有效元素的个数减少到n个 } }
7.删除数据的接口：
①pop_back();
voidpop_back() { assert(empty());//如果容器已经空， 再次调用的话，直接报错--_finish; }
②erase()接口以及其引起的迭代器失效
删除任意位置，即挪动要删除的数据的后面的位置，将他们往前挪即可。
voiderase(iteratorpos) { //pos的位置要合理assert(pos>=_start); assert(pos<_finish); iteratorbegin=pos+1; while (begin<_finish) { *(begin-1) =*begin; ++begin; } --——finish; }
删除操作，会让pos迭代器会失效，但注意，在Linux下g++中不会报错，不会失效，因为g++采用的是模拟实现，它做不到识别失效问题，pj版能够识别，是因为它不是一个原生指针。但不管怎么样，一般来说统一认为它会失效！
而解决失效问题，可以将代码改成如下：
iteratorerase(iteratorpos) { //pos的位置要合理assert(pos>=_start); assert(pos<_finish); iteratorbegin=pos+ ; while (begin<_finish) { *(begin-1) =*begin; ++begin; } --_finish; returnpos; }
删除后，更新pos位置即可。
8.find导致的迭代器失效问题
my_vector::vector<int>::iteratorit=find(arr.begin(), arr.end(), 3); if (it!=arr.end()) { arr.insert(it, 30); } //可能发生迭代器失效 (*it)++;
如上代码，在insert之和，it会发生迭代器失效。其原因是：即使我们在insert后，pos位置更新，使得pos没有失效，但是对于reserve接口，传参是传值传参，pos的改变不会影响it，而it作为参数传到insert接口后，由于原本指向的空间已经释放了，it就变成了野指针，也就是迭代器失效了。当然了，如果没有发生扩容，就可能不会发生失效。
在C++官方库里面，insert也没有引用作参数，也是传值传参的。简单地解释一下就就是，有时候传进去的是一些具有常性的临时变量，不可传，比如insert(arr.begin(),1);，其中的arr.begin()就是临时变量。
9.赋值操作
vector<T>&operator=(vector<T>v) { swap(v); return*this; }
