vector是向量的意思，看了vector的底层实现之后，能够很明确的认识到它其实就是我们经常使用的顺序表。在我们的认知中，顺序表会有一个数组、数据的size以及容量的大小。vector作为一个向量容器，它可以存放任意类型的数据。所以在实现时一定是一个类模板。再来谈它的成员属性，我在这里仿照库函数的实现，定义了三个迭代器：_start、_finish、_end_of_sotrage;

1、基本框架

namespace ltq
{template<class T>class vector{public:typedef T* iterator;vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}~vector(){delete[] _start;//涉及到后续的空间申请，所以需要释放。_start = nullptr;_finish = nullptr;_end_of_storage = nullptr;}private:iterator _start;//数据起点iterator _finish;//有效数据后一位置iterator _end_of_storage;//容量};
}

2、void push_back(const T& x)

        尾插的数据类型为T类型，有可能是自定义类型。自定义类型传值传参会进行深度拷贝影响代码效率，所以在函数参数部分直接加上引用来提高代码效率。由于vector在初始化部分没有预先开辟空间，所以在尾插之前需要进行开辟空间，即使提前有开好的空间也要进行容量的检查。

        这里直接略过capacity()和size()的说明，这两个函数比较简单。

		void push_back(const T& x){if (_start == _finish){size_t new_capacity = capacity() == 0 ? 4 : 2 * capacity();reserve(new_capacity);}*_finish = x;++_finish;}size_t capacity()const{return _end_of_storage - _start;}size_t size()const{return _finish - _start;}

        使用reserve(size_t n)进行空间的开辟。在最开始时容量为0时，默认开辟4个T类型大小的空间。如果该容器之前存在容量，那么就按二倍当前容量进行扩容。

3、void reserve(size n) 

        这里需要明确n是n个T类型的意思。也就是说要开辟的空间是sizeof(T)*n的大小。但是一般开辟空间直接使用new关键字就行。

		void reserve(size_t n){if (n > capacity()){//开空间T* tmp = new T[n];if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}size_t old_size = size();_start = tmp;_finish = _start + old_size;_end_of_storage = _start + n;}}

        如果vector中有历史数据就要进行数据的拷贝，这里使用memcpy()库函数来进行实现，需要注意拷贝的字节大小为sizeof(T) * size()。创建old_size变量是为了修复直接给_finish = _start + size()引发的_finish恒等于nullptr的bug.

        假设这里_finish = _start + size()，那么

        在计算_finish时，size() = _finish - _start,此时_start已经指向tmp开辟出来的空间,但是_finish还是nullptr，相减之后size() = 负的_start。所以执行_finish  = _start + 负的_start 就恒为nullptr。在插入数据*_finish = x就会发生错误。解决办法是在_start指向新开辟的空间之前就记录老的size()，再进行后续的计算。 这里也能说明为什么要在析构函数里对_start进行释放。

 4、迭代器

        迭代器iterator就是T*，因为顺序结构的原因直接解引用就能访问到T类型的数据。

		iterator begin(){return _start;}iterator end(){return _finish; }

5、T& operator[](size_t pos)

        方括号要实现的功能就是对容器内数据的访问，对于顺序结构来说，对迭代器本身进行解引用就是数据本身。所以，代码实现就可以写成下面的形式：需要包括只读和读写两个版本：

		T& operator[](size_t pos){assert(pos < size());return *(_start + pos);}const T& operator[](size_t pos)const{assert(pos < size());return *(_start + pos);}

6、iterator insert(iterator pos,const T& x)

        在pos位置插入一个新的数据x，类似于string的插入，但是这里使用迭代器解决了string在sisze_t pos 位置插入数据时挪动数据引发的整型提升导致的错误。但是又带了一个新的问题（迭代器失效）,我们先按照正常思路进行代码的实现。

		void insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish);//扩容逻辑if (_finish == _end_of_storage){size_t new_capacity = capacity() == 0 ? 4 : capacity() * 2;reserve(new_capacity);}//挪动数据iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;}

        按照正常的逻辑，首先要判断pos位置的合法性。其次要检查容器的容量是否充足，容量不够时要进行扩容操作。然后需要对pos位置到_finish之前的数据往后挪动1个位置。最后在pos位置插入新的数据x。

        这样的逻辑看似没有任何问题，但是在测试中不难发现每当容器的容量不够时，再进行扩容操作之后就是发生迭代器失效。

        此时我们看到程序没有在容器的头部插入数字5，到底是怎一回事呢？下面我来画图说明问题：

        扩容前容器的容量为4，在头插数据对容器进行扩容之后，依据前面代码的逻辑会开辟新的空间，并进行数据的复制，再释放旧的空间。也就是说，开辟新的空间之后所有的成员属性都指向了新的空间，但是pos仍在指向已经被释放的空间，此时pos就是一个野指针。在对数据进行挪动时

    //挪动数据iterator end = _finish - 1;while (end >= pos)//pos指向原来的旧空间{*(end + 1) = *end;--end;}

         为了解决这一问题，我们应该在扩容开始之前记录pos与_start的相对位置，再扩容结束之后更新pos的位置，从而解决问题。修改后的代码如下：

		iterator insert(iterator pos, const T& x){assert(pos >= _start && pos <= _finish);//扩容逻辑if (_finish == _end_of_storage){size_t len = pos - _start;size_t new_capacity = capacity() == 0 ? 4 : capacity() * 2;reserve(new_capacity);pos = _start + len;}//挪动数据iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;}

        经过上述的修改，实际上已经解决了迭代器的内部失效问题，但是在外部调用insert函数之后也有可能引发外部的迭代器失效。这里我们需要注意，在insert()之后谨慎使用迭代器。

7、iterator erase(iterator pos)

        删除pos位置的数据，首先还是要对pos位置的合法性进行检查。pos合法之后挪动数据进行覆盖即可。删除数据之后的迭代器也会失效，因为删除操作会将所有的数据往前挪动，之前的迭代器将不再指向挪动之后的数据。所以，为了删除数据之后正常使用迭代器访问容器中的数据，一般需要返回删除位置的下一个位置的迭代器，也就是pos位置。

		iterator erase(iterator pos){assert(pos >= _start && pos < _finish);//挪动数据iterator it = pos - 1;while (it != _finish){*(it - 1) = *it;++it;}--_finish;return pos;}

8、void resize(size_t n,const T& x = T())  

        resize()函数可以更改容器数据的尺寸大小，大逻辑主要是原尺寸大于n，那么就直接截断数据。如果n大于原始数据尺寸那么在进一步判断是否需要扩容，在不满尺寸的位置插入指定数据。这里需要说明的是，如果没有给定数据，也应当插入默认值也就是在函数实现时要给定缺省值。T为自定义类型时需要调用构造函数创建匿名对象，将创建的对象插入容器中。

		void resize(size_t n, const T& x = T()){if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish != _start + n){*_finish = x;++_finish;}}}

9、拷贝构造函数 

        拷贝构造函数可以自己开空间并进行深拷贝，以实现拷贝构造的功能。这里如何来进行深拷贝，可以采用下面的实现方法：将目标容器中的每一个对象赋值给新的对象,而每一个特定对象就会调用自己本身的赋值运算重载函数进行深拷贝。

		vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){_start = new T[v.size()];//浅拷贝//memcpy(_start, v._start, sizeof(T) * v.size());for (size_t i = 0; i < v.size(); ++i){//使用赋值 进行深拷贝_start[i] = v._start[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();}

10、赋值运算符重载 

        采用新式写法，使用传值传参，自动调用拷贝构造tmp对象，再与*this进行交换j即可。

		void swap(vector<T>& v){std::swap(_start,v._start);std::swap(_finish,v._finish);std::swap(_end_of_storage,v._end_of_storage);}vector<T>& operator=(vector<T> tmp){swap(tmp);return *this;}

11、存放自定义类型的深拷贝问题 

        在前面的扩容、构造中我们使用的数据拷贝均为memcpy，这就存在一个问题，当存放的数据类型为自定义类型数据时memcpy仅仅进行的是浅拷贝。

        假设vector中存放的数据类型为string，当容器容量需要扩容时，mencpy仅仅拷贝的是string对象的各个成员变量，并没有开辟新的空间，这就意味着当扩容过程中，开辟了新的空间，而新的空间中存放的依旧是就空间中的string对象，当_str指向新的空间之后,就空间就会调用析构函数，此时delete[] 也就会将就空间中的string对象进行释放。即使新的空间中存放的是就空间的地址，但是这时就空间内的string对象早已不复存在。 

解决方案：

    for (size_t i = 0; i < v.size(); ++i){//使用赋值 进行深拷贝_start[i] = v._start[i];}

        将每一个对象逐个赋值给新的容器，对象间的赋值就会调用自身的赋值运算符重载，从而进行深拷贝。

12、迭代器区间初始化

        vector支持各种迭代器初始化，不仅仅局限于自身类型的迭代器，那么迭代器区间构造函数就需要增加新的模板参数。

		template<class InputIterator>vector(InputIterator first, InputIterator last): _start(nullptr), _finish(nullptr), _end_of_storage(nullptr){while (first != last){push_back(*first);++first;}}