?个人主页：奋斗的小羊 ?所属专栏：C++ 很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~ 
目录
?1、vector的主要函数接口?2、vector的模拟实现?2.1 构造和析构?2.2 vector属性相关函数?2.3 运算符重载?2.3.1 赋值重载?2.3.2 [ ] 重载 ?2.4 vector的打印?2.5 扩容?2.5.1 深拷贝中的浅拷贝问题 ?2.6 迭代器失效的问题?2.6.1 插入和删除?扩容形成野指针?挪动数据位置意义改变 ?2.7 调整大小 ?3、vector模拟实现完整代码
?1、vector的主要函数接口
namespace yjz{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//默认构造vector(){}//拷贝构造vector(const vector<T>& v){}//迭代器区间构造template<class InputIterator>vector(InputIterator first, InputIterator last){}//指定n个值构造vector(size_t n, const T& val = T()){}vector(int n, const T& val = T()){}//析构~vector(){}//交换数据void swap(vector<T>& tmp){}//清理数据void clear(){}传统写法//vector<T>& operator=(const vector<T>& v)//{}//现代写法vector<T>& operator=(vector<T> tmp){}size_t size() const{}size_t capacity() const{}//迭代器iterator begin(){}iterator end(){}const_iterator begin() const{}const_iterator end() const{}//【】重载T& operator[](size_t i){}const T& operator[](size_t i) const{}//判空bool empty(){}//尾删void pop_back(){}//扩容void reserve(size_t n){}//尾插void push_back(const T& n)//可能插入类等{}//插入iterator insert(iterator pos, const T& n){}//删除iterator erase(iterator pos){}//调整大小void resize(size_t n, T val = T()){}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};template<class T>void print_vector(const vector<T>& v){}}?2、vector的模拟实现
?2.1 构造和析构
虽然vector使用编译器生成的默认构造就行，但是我们还需要写拷贝构造，有了构造函数编译器就不会生成默认构造了，所以可以在形式上写个默认构造类模版的成员函数，还可以继续是函数模版 //默认构造vector(){}//拷贝构造vector(const vector<T>& v){reserve(v.size());for (auto& e : v){push_back(e);}}//迭代器区间构造template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}//指定n个值构造vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}vector(int n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}?2.2 vector属性相关函数
size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}//迭代器iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}?2.3 运算符重载
?2.3.1 赋值重载
赋值重载可以借助swap函数，需要注意的是形参必须传值 void swap(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=(vector<T> tmp){swap(tmp);return *this;}?2.3.2 [ ] 重载
T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}at() 和 operator[] 都是根据下标获取任意位置元素的，在debug模式下两者都会去做边界检查。当发生越界行为时，at 是抛异常，operator[] 内部的assert会触发 ?2.4 vector的打印
为了方便打印vector中不同类型的数据，可以将迭代器遍历和范围for遍历封装成一个模版函数，有几点需要注意：
const引用传参，避免拷贝，迭代器也要保持一致使用const_iterator没有实例化的类模版里面取东西，编译器不能区分这里的const_iterator是类型还是静态成员变量，从属名称的使用必须以typename为前缀当然最省事的还是auto template<class T>void print_vector(const vector<T>& v){//typename vector<T>::const_iterator it = v.begin();auto it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;for (auto e : v){cout << e << " ";}cout << endl;}?2.5 扩容
?2.5.1 深拷贝中的浅拷贝问题
void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];memcpy(tmp, _start, sizeof(T) * size());delete[] _start;_start = tmp;//_finish = _start + size();_finish = _start + old_size;//_finish也要更新_end_of_storage = _start + n;}}上面是以前扩容的常规操作，但是在这里有些潜在的问题：
void test_vector7(){vector<string> v1;v1.push_back("11111111111111");v1.push_back("11111111111111");v1.push_back("11111111111111");v1.push_back("11111111111111");print_vector(v1);}
当我们在不扩容的情况下在vector中插入string类，不会出现什么问题，但如果扩容的话，就会出现问题：
这里的问题在扩容的过程中memcpy是按字节拷贝的（浅拷贝），而string类中还有_str指向一块空间，memcpy将string类中的所有数据都浅拷贝到tmp指向的空间中，tmp中的_str指向的还是原来的空间，释放旧空间时其中的string类会自动调用析构函数，释放掉_str指向的空间，最后tmp空间中的_str指向的就是非法空间。
要想解决这个问题也简单，用深拷贝来代替memcpy的浅拷贝，可以考虑赋值重载，因为 string类的赋值重载是深拷贝：
void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];//memcpy(tmp, _start, sizeof(T) * size());for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;//_finish = _start + size();_finish = _start + old_size;//_finish也要更新_end_of_storage = _start + n;}}?2.6 迭代器失效的问题
?2.6.1 插入和删除
?扩容形成野指针
在指定位置插入一个数据，首先要判断vector是否满了，如果满了调用reserve扩容。插入前还需要挪动指定位置之后的数据，最后插入数据，++_finish。
void insert(iterator pos, const T& n){ assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : 2 * capacity());}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = n;++_finish;}这是常规的插入方法，和string类插入一个字符一样。
但是当我们插入一个数据需要扩容时，编译运行就会陷入死循环。
原因是虽然扩容后_start、_finish、_end_of_storage都更新了，但是pos指向的还是原来的位置。
所以我们需要在扩容后将pos的指向也更新一下：
void insert(iterator pos, const T& n){assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = n;++_finish;}?挪动数据位置意义改变
假如我们想在某个数据前面插入但是不知道具体位置，则需要先查找到这个数据的地址：
int n;cin >> n;auto pos = find(v.begin(), v.end(), n);if (pos != v.end()){v.insert(pos, 40);*pos += 100;}print_vector(v);
如果没有扩容，pos原本指向的数据是我们要查找的3，但是在我们往3的前面插入一个40后，pos指向的数据就变了，这也被认为是迭代器失效；如果扩容，则就是上面讲的pos变成野指针。
vector类似，string在插入+扩容操作+erase后，迭代器也会失效所以不管扩不扩容， insert后pos就失效，不要直接访问，要访问就要更新迭代器的值。 可以在insert函数最后返回pos的值：
iterator insert(iterator pos, const T& n){assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = n;++_finish;return pos;}int n;cin >> n;auto pos = find(v.begin(), v.end(), n);if (pos != v.end()){ pos = v.insert(pos, 40);*(p + 1) += 100;}print_vector(v);同样的删除也会使迭代器失效：
iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;++it;}--_finish;return pos;}vector中任意位置的数据，VS都认为该位置迭代器失效 ?2.7 调整大小
为了兼容类类型给缺省值的情况，内置类型也有了构造函数的概念。
void resize(size_t n, T val = T()){if (n < size()){_finish = _start + n;}else{reserve(n);//大了才扩容while (_finish < _start + n){*_finish = val;++_finish;}}}?3、vector模拟实现完整代码
vector.h:
#pragma once#include <iostream>#include <assert.h>#include <string>using namespace std;namespace yjz{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//默认构造vector(){}//拷贝构造vector(const vector<T>& v){reserve(v.size());for (auto& e : v){push_back(e);}}//迭代器区间构造template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}//指定n个值构造vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}vector(int n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}void swap(vector<T>& tmp){std::swap(_start, tmp._start);std::swap(_finish, tmp._finish);std::swap(_end_of_storage, tmp._end_of_storage);}void clear(){_finish = _start;}传统写法//vector<T>& operator=(const vector<T>& v)//{//if (this != &v)//{//clear();//reserve(v.size());//for (auto e : v)//{//push_back(e);//}//}//}//现代写法vector<T>& operator=(vector<T> tmp){swap(tmp);return *this;}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}//迭代器iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}bool empty() const{return _start == _finish;}void pop_back(){assert(!empty());_finish--;}void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];//memcpy(tmp, _start, sizeof(T) * size());for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;//_finish = _start + size();_finish = _start + old_size;//_finish也要更新_end_of_storage = _start + n;}}void push_back(const T& n)//可能插入类等{if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : 2 * capacity());}*_finish = n;++_finish;}iterator insert(iterator pos, const T& n){assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = n;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;++it;}--_finish;return pos;}void resize(size_t n, T val = T()){if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish < _start + n){*_finish = val;++_finish;}}}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};template<class T>void print_vector(const vector<T>& v){//typename vector<T>::const_iterator it = v.begin();auto it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;//for (auto e : v)//{//cout << e << " ";//}//cout << endl;}}_finish和_end_of_storage，因为reserve中更新了_end_of_storage和_start指向的空间reserve中不能使用memcpy拷贝原始数据，memcpy是浅拷贝，而vector中也可以存类类型；可以考虑赋值重载reserve中更新_finish的时候不能用_finish = _start + size()，因为size()是通过_finish - _start得到的，而扩容过后_start和_finish指向的已经不是同一空间了，所以size()是错误的，应该在扩容前保存下旧的size的值，扩容后再用这个值更新_finish在insert中同样也有类似的问题，当空间不够时就要扩容，而pos是指向原来空间的迭代器，所以在扩容前也要提前保存下pos相较于_start的位置，在扩容后及时地更新pos的指向还需要特别注意的是insert和erase中迭代器失效的问题 test.cpp:
#define _CRT_SECURE_NO_WARNINGS#include "vector.h"namespace yjz{void test_vector1(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);print_vector(v);}void test_vector2(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);//v.push_back(5);print_vector(v);v.insert(v.begin() + 2, 10);print_vector(v);}void test_vector3(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);int n;cin >> n;auto pos = find(v.begin(), v.end(), n);if (pos != v.end()){pos = v.insert(pos, 40);*(pos + 1) += 100;}print_vector(v);}void test_vector4(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(4);print_vector(v);//删除所有的偶数auto it = v.begin();while (it != v.end()){if (*it % 2 == 0){it = v.erase(it);}else{++it;}}print_vector(v);}void test_vector5(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);print_vector(v);v.resize(3);print_vector(v);v.resize(8, 1);print_vector(v);}void test_vector6(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);vector<int> v2(10, 1);print_vector(v2);vector<int> v3(v2.begin() + 1, v2.begin() + 5);print_vector(v3);}void test_vector7(){vector<string> v1;v1.push_back("11111111111111");v1.push_back("11111111111111");v1.push_back("11111111111111");v1.push_back("11111111111111");v1.push_back("11111111111111");v1.push_back("11111111111111");v1.push_back("11111111111111");v1.push_back("11111111111111");v1.push_back("11111111111111");v1.push_back("11111111111111");print_vector(v1);}}int main(){//yjz::test_vector1();//yjz::test_vector2();//yjz::test_vector3();//yjz::test_vector4();//yjz::test_vector5();//yjz::test_vector6();yjz::test_vector7();return 0;}