C++-vector模拟实现

###vector底层相当于是数组，查看源码可以发现，这个类的私有成员变量是三个迭代器；在实现时迭代器就可以当作是vector里面的元素的指针类型；

###vector是一个类模板，实现时也应当按照这样的写法用一个模板去实现，类模板vector中数据类型是T；

	private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;

_start指向vector的开始地址，_finish指向vector的有效元素的结束地址，_end_of_storage指向vector最大存储数据的地址； 

一、迭代器

typedef T* iterator;
typedef const T* const_iterator;//迭代器
iterator begin()
{return _start;
}
const_iterator begin()const
{return _start;
}
iterator end()
{return _finish;
}
const_iterator end()const
{return _finish;
}

二、容量

		size_t size()const{return _finish - _start;}size_t capacity()const{return _end_of_storage - _start;}bool empty()const{return size() == 0;}void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];//memcpy(tmp, _start, size() * sizeof(T));//浅拷贝for (size_t i = 0; i < old_size; i++)//深拷贝{tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}}void resize(size_t n, const T& val = T())//匿名对象作为缺省值{if (n < capacity()){_finish = _start + n;}else{reserve(n);for (iterator i = _finish ; i < _start + n; i++){Insert(i,val);}}}

1、reserve

基本思路：开辟一个临时的数组存放T类型的数据，让这个数组的大小为指定的n，将vector对象中的数据全部放到这个临时数组中，再清空vector中的数据，最后让vector对象存放数据的地址就是这个临时数组的地址；

两个关键点：

1. old_size：若是不先记录下size的话，后面给_finish重新赋值时使用到size()，size（）函数中_size不再是原来的_size,而是tmp，此时用_size去减_finish会出错;
2. 深、浅拷贝问题：若是使用memcpy就是浅拷贝，对于vector中是内置类型的数据可以，但是若是vector对象中涉及到自定义类型，例如string为数据的情况，浅拷贝拷贝的是地址，那么tmp中的数据的地址就是vector对象中的数据地址，之后再delete掉_start，就相当于把要存放数据的tmp中的数据给释放了，这样会让数据丢失；所以一个一个赋值，对于内置类型无影响，对于自定义类型，例如string的类型，就是赋值重载，string实现时是深拷贝，这样就解决了。

2、resize

基本思路：若是比原来的size小，那么就让_finish等于_start+n，这样就访问不到n之后的数据了；若是比原来的size大，没有给值就用匿名对象T()，对于内置类型给初始值（0、空指针、0.0一类），对于自定义类型，调用默认构造函数，实现部分：先扩容，再插入数据。

三、元素获取

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

重载运算符[]，在内部通过数组的方式返回对应下标的位置。

四、修改

		void push_back(const T& val){if (_end_of_storage == _finish){reserve(size() == 0 ? 4 : 2 * capacity());}*_finish = val;_finish++;}void pop_back(){assert(size() > 0);_finish--;}iterator Insert(iterator pos, const T& val){assert(pos >= _start);assert(pos <= _finish);if (_end_of_storage == _finish){size_t len = pos - _start;reserve(size() == 0 ? 4 : 2 * capacity());pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *(end);end--;}*pos = val;_finish++;return pos;}iterator Erase(iterator pos){assert(pos >= _start && pos < _finish);iterator tmp = pos + 1;while (tmp < _finish){*(tmp - 1) = *tmp;tmp++;}--_finish;return pos;}

1、insert和erase调用时迭代器失效的问题

insert：实现时若是涉及到空间不够要扩容，扩容时要先记录下pos和_start之间的距离，扩容之后_start不是之前的了，那么pos也要跟着更新;此时在调用insert时若是插入之后还要访问pos就要更新pos（因为pos已经改变了，若是不更新就使用原来的pos会找不到原来的数据）

就算没有扩容，空间够，insert之后使用到pos还是要先更新，因为此时的pos指向的是新插入进来的数据，而不是我们想要访问的原来的数据。

erase：erase的迭代器失效举一个例子：

	vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);container_print(v);cout << "size:" << v.size() << endl;cout << "capacity:" << v.capacity() << endl;vector<int>::iterator p = v.begin();while(p < v.end()){if (*p % 2 == 0){v.Erase(p);}p++;}container_print(v);

运行结果似乎很正确，那再看：

	vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(4);v.push_back(5);container_print(v);cout << "size:" << v.size() << endl;cout << "capacity:" << v.capacity() << endl;vector<int>::iterator p = v.begin();while(p < v.end()){if (*p % 2 == 0){v.Erase(p);}p++;}container_print(v);

此时会发现有偶数没有删除完全，这是因为迭代器失效了

原因：erase的实现中删除了pos指向的数据之后返回pos，此时的pos指向的是原来要删除的数据的下一个数据，在这个删除偶数的例子中，{1，2，3，4，5}pos指向2.删除之后pos指向3，再加加就是指向4，刚好到了下一个偶数，删除之后，pos指向5，再加加，循环结束，这里只是一个巧合；数据是{1，2，3，4，4，5}删除完2，pos指向第一个4，删除之后，pos指向第二个4，再加加那么pos指向是5了，就跳过了这个4，此时就是迭代器失效了；

为了解决，erase要使用到pos就要更新迭代器；

	while(p < v.end()){if (*p % 2 == 0){p=v.Erase(p);}else{p++;}}

这样写，每次删除完之后，pos指向就是原来要删除数据的下一个数据，若是这个数是偶数那就继续删，是奇数就加加跳过，这样就能够不错过数据了。

五、构造

1、强制的默认构造写法

	vector() = default;//强制的默认构造

2、拷贝构造

		//拷贝构造vector(const vector<T>& v){reserve(v.capacity());for (auto it : v){push_back(it);}}

 3、赋值重载

		void clear(){_finish = _start;}void swap(const vector<T>& tmp){std::swap(_start, tmp._start);std::swap(_finish, tmp._finish);std::swap(_end_of_storage, tmp._end_of_storage);}//赋值重载（传统写法）vector<T>& operator=(const vector<T>& v){if (_start)//说明被赋值的对象不是空，要先清除{clear();}reserve(v.capacity());for (auto it : v){push_back(it);}}//赋值重载（现代写法）vector<T>& operator=(vector<T> tmp){swap(tmp);return *this;}

a、传统写法：

若是原vector不为空，先置为空，之后再扩容，扩到和v一样的大小，再使用拷贝构造那一套，将v的数据一个一个尾插进入要被赋值的vector

b、现代写法：

传参时用tmp接收赋值等式右边的vector，进行拷贝构造，之后再和赋值等式左边的vector进行交换；（现代写法一般要在拷贝构造写好的情况下进行）；

4、迭代器初始化

		//迭代器初始化template <class InputIterator>//可以接收不同的迭代器，但是迭代器里面的数据的类型要相同vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}

这里使用到模板是为了接收各种类型的迭代器，但是值得注意的是这些迭代器的各自的容器里面的数据类型应该和此时的待构造的vector里面的数据保持一致，再不济也可以强制类型转换；

5、n个val去初始化

		//n个 val 去初始化vector(size_t n, const T& val = T())//不给值就用匿名对象,这个对象是 vector 里面的值{reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}

6、析构

		~vector(){if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}}

六、容器打印函数模板中的注意事项：

	template <class T>void vector_print(const vector<T>& v){//要写 typename,否则没有实例化的 vector<T> 不知道const_iterator是类型还是静态成员变量typename vector<T>:: const_iterator it = v.begin();//auto it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;}

这个函数模板定义在我们自己实现的vector类外面，用来打印vector，使用到迭代器，但是在写时注意这一行：

typename vector<T>:: const_iterator it = v.begin();

 要加上typename，否则编译器分不清这是类里面的静态成员变量还是类型，当然若是写成静态成员变量去使用，那就一定是静态成员变量，但是这里不能直接写，要在前面加上tyepname；第二种方法可以直接用auto自动生成类型去使用。