vector模拟实现
成员变量定义默认成员函数构造函数 迭代器范围for、对象类型匹配原则 容量操作sizeemptycapacityreserve成员变量未更新memcpy值拷贝 resize内置类型的构造函数 数据访问frontbackoperator[ ] 数据修改操作push_backpop_backswapclearinsertpos位置未更新无返回值 erase无返回值 迭代器失效定义insert导致的迭代器失效erase导致的迭代器失效删除vector中的奇数 非法的间接寻址铁汁们，今天给大家分享一篇vector模拟实现 + 迭代器失效，来吧，开造⛳️
成员变量定义
指向最后一个空间的下一个位置? iterator _endofstorage
指向存储第一个有效数据空间的位置? iterator _start
指向存储最后一个有效数据空间的下一个位置? iterator _finish
#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>#include<string>#include<assert.h>using namespace std;template<class T>class vector {private:iterator _start = nullptr; //起始位置iterator _finish = nullptr; //有效数据的结束位置iterator _endofstorage = nullptr; //容量的结束位置};默认成员函数
构造函数
?vector( ) { } ;
功能：构造无参的对象vector() {}; //无参构造?vector(size_t n, const T& val = T( ) ) ;
功能：构造含n个val值的对象vector(size_t n, const T& val = T()) //用n个val值构造{resize(n, val);}?vector( InputIterator first, InputIterator last ) ;
功能：构造与[first, last)范围一样多元素的对象template<class InputIterator> // 注意： 模板内可以在嵌套模板vector(InputIterator first, InputIterator last) //用迭代区间进行构造{ //泛型编程，函数模板，不是只适用于某个容器的的迭代器，适用于所有容器的的迭代器while (first != last){push_back(*first);first++;}}?Tips：模板内可以嵌套其他模板。
迭代器
template<class T>class vector {public:typedef T* iterator;typedef const T* const_iterator;}? Tips：指向连续物理空间的指针是天然的迭代器。
?iterator begin( ) ;
功能：返回指向第一个元素的位置。iterator begin() //迭代器所指向的空间内的值 “既可读又可写”{ //只适用于const对象（权限可以平移）、不适用于非const对象（权限不可以放大）return _start; //vector第一个元素所在的位置（指针）}?Tips : const_iterator 修饰的是迭代器所指向的元素不能被修改，而迭代器本身可以被修改。const修饰this指针，表示在该成员函数中成员变量不允许被修改，此处const的用法只能用于类中的成员函数。
?iterator end( ) ;
功能：返回指向最后一个元素的下一个位置。iterator end(){return _finish; //vector最后一个元素后面所在的位置（指针）}?const_iterator begin( )const ;
const_iterator begin()const //迭代器所指向的空间内的值 “只可不可写”{return _start; //既适用于const对象（权限可以平移）、又适用于非const对象（权限可以缩小）}?const_iterator end( )const ;
const_iterator end()const{return _finish;}范围for、对象类型匹配原则
const vector<int> v(5, 2);for (auto& e : v){cout << e << ' ';}cout << endl;只要容器支持迭代器，就支持用范围for来访问, 原因：范围for的底层实现为迭代器。
用范围for访问对象中的元素，对象类型不同，范围for底层调用的迭代器接口不同。
容量操作
size
?size_t size( )const ;
功能：计算元素的总个数size_t size()const //有效元素总个数{return _finish - _start;}empty
?bool empty( )const ;
功能：判断vector是否为空，为空，则返回true,不为空，则返回false。bool empty()const //判断是否为空， 为空，则返回true,不为空，则返回false{return size() == 0;}vector<string> v1;v1.push_back("zhangsan");cout << v1.empty() << endl;vector<int> v2;cout << v2.empty() << endl;capacity
?size_t capacity( )const ;
功能：获得当前分配给vector存储空间的大小。size_t capacity()const //容量的大小{return _endofstorage - _start;}reserve
?void reserve(size_t n) ;
功能：使得vector容器存储空间的大小为n。void reserve(size_t n) //开空间（扩容）{if (n > capacity()) //此处在判断:1.自己直接调用reserve,2.其他接口间接调用reserve{T* tmp = new T[n]; //扩容 new:开空间+构造函数，完成初始化size_t old = size(); // 注意 ：因为new[]会开辟新的空间if (_start) //拷贝旧空间中的值{for (int i = 0; i < old; i++) //vector底层物理空间连续tmp[i] = _start[i] ; // 若为string,则调用string的赋值重载函数(深拷贝）delete[] _start; //delete:析构函数+释放空间}//更新成员变量_start = tmp; _finish = _start + old; //_endofstorage = _start + n; //}}
成员变量未更新
void reserve(size_t n) //开空间（扩容）{if (n > capacity()) //此处在判断:1.自己直接调用reserve,2.其他接口间接调用reserve{T* tmp = new T[n]; //扩容 new:开空间+构造函数，完成初始化if (_start) //拷贝旧空间中的值{memcpy(tmp, _start, sizeof(T) * size()); delete[] _start; //delete:析构函数+释放空间}//更新成员变量_start = tmp; _finish = _start + size(); _endofstorage = _start + capacity();}}
memcpy值拷贝
void reserve(size_t n) //开空间（扩容）{if (n > capacity()) //此处在判断:1.自己直接调用reserve,2.其他接口间接调用reserve{T* tmp = new T[n]; //扩容 new:开空间+构造函数，完成初始化size_t old = size(); // 注意 ：因为new[]会开辟新的空间if (_start) //拷贝旧空间中的值{memcpy(tmp, _start, sizeof(T) * old); delete[] _start; //delete:析构函数+释放空间}//更新成员变量_start = tmp; _finish = _start + old; //_endofstorage = _start + n; //}}
resize
?void resize(size_t n, const typename& val = typename( ) ) ;
功能：调整vector容器的大小，使其内元素个数变为n。void resize(size_t n, const T& val = T()) //开空间+初始化{if (n > size()) //插入数据 -》 n > capacity:扩容+插入 size < n <capacity:插入{reserve(n); // n > capacityfor(int i = size(); i < n; i++) //从size位置处向后插入push_back(val); }else //n < size:尾删{_finish = _start + n;}}vector<int> v2;v2.push_back(2);v2.push_back(2);v2.push_back(2);v2.push_back(2);v2.push_back(2);for (auto& e : v2){cout << e << ' ';}cout << endl;v2.resize(7, 1);for (auto& e : v2){cout << e << ' ';}cout << endl;v2.resize(12);for (auto& e : v2){cout << e << ' ';}cout << endl;v2.resize(3);for (auto& e : v2){cout << e << ' ';}cout << endl;
内置类型的构造函数
int a = int();cout << a << endl;int b = int(5);cout << b << endl;
?Tips ：初始化处默认给缺省值，缺省值为无参构造函数，自定义类型会去调它自己的默认构造函数，c++11为了兼容模板，使得内置类型也有构造函数，内置类型得无参构造函数初始化为0,eg:int val = int(), val = 0、double val = double(),val = 0.0,int* val = int*() , val = nullptr、char val = char(), val = ‘\0’。
数据访问
front
?T& front( ) ;
功能：获取第一个有效元素T& front() //获取第一个有效元素{assert(size() > 0); //断言，确保是否有数据return *_start;}back
?T& back( ) ;
功能：获取最后一个有效元素T& back() //获取最后一个有效元素{ assert(size() > 0); //断言，确保是否有数据 return *(_finish - 1);}vector<int> v4;v4.push_back(1);v4.push_back(2);v4.push_back(3);cout << v4.front() << endl;cout << v4.back() << endl;
operator[ ]
?T& operator[](size_t n) ;
功能：访问下标为n处的值，返回值既可读又可写(非const对象)。T& operator[](size_t n) //既可读又可写{return _start[n];}?const T& operator[](size_t n)const ;
功能：访问下标为n处的值，返回值只可读不可写(const对象)。const T& operator[](size_t n)const //只可读不可写{return _start[n];}vector<int> v2(5, 2);v2[2] = 3; cout << v2[2] << endl;const vector<int> v3(5, 4); cout << v3[3] << endl;
数据修改操作
push_back
?void push_back(const T& val) ;
功能：在末尾插入一个元素。void push_back(const T& val) //在末尾插入一个数据{if (_finish == _endofstorage) //空间满了，扩容{size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}*_finish = val; //插入数据_finish++; }pop_back
?void pop_back( ) ；
功能：删除最后一个元素。void pop_back() //删除最后一个元素{ assert(size() > 0); //断言，无任何数据，不能在进行删除操作 _finish--;}vector<int> v4;v4.push_back(1);v4.push_back(2);v4.push_back(3);for (auto& e : v4){cout << e << ' ';}cout << endl;v4.pop_back();for (auto& e : v4){cout << e << ' ';}cout << endl;
swap
?void swap(vector& v) ;
功能：交换。void swap(vector<T>& v) //交换{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}vector<int> v2(5, 2);vector<int> v4;v4.push_back(1);v4.push_back(2);v4.push_back(3);v4.pop_back();for (auto& e : v2){cout << e << ' ';}cout << endl;for (auto& e : v4){cout << e << ' ';}cout << endl;v2.swap(v4);for (auto& e : v2){cout << e << ' ';}cout << endl;for (auto& e : v4){cout << e << ' ';}cout << endl;
clear
?void clear( ) ;
功能：使vector中元素的总个数size变为0，但容量capacity不变。void clear() //清空 size改变，capacity不变{_finish = _start;}insert
?void insert ( iterator position , const typename& x) ；
功能：在指定的位置(迭代器）前插入元素x。iterator insert(iterator pos, const T& val) //在pos位置前插入元素{assert(pos >= _start && pos <= _finish); //断言，确保在[_start,_finish]范围内插入数据if (_finish == _endofstorage) //空间满了，扩容{size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);pos = _start + len; //扩容会导致pos位置失效，更新pos位置}//此处数据往后挪动，既可以用memmove，又可以用迭代器//memmove(pos + 1, pos, sizeof(T) *( _finish - pos)); //memmove为值拷贝iterator tmp = _finish - 1;while (tmp >= pos) {*(tmp + 1) = *tmp;tmp--;}*pos = val; //插入数据_finish++;return pos; //返回值为了，发生扩容,pos位置更新后的值仍能被继续使用}pos位置未更新
void insert(iterator pos, const T& val) //在pos位置前插入元素{assert(pos >= _start && pos <= _finish); //断言，确保在[_start,_finish]范围内插入数据if (_finish == _endofstorage) //空间满了，扩容{size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);}//此处数据往后挪动，既可以用memmove，又可以用迭代器//memmove(pos + 1, pos, sizeof(T) *( _finish - pos)); //memmove为值拷贝iterator tmp = _finish - 1;while (tmp >= pos) {*(tmp + 1) = *tmp;tmp--;}*pos = val; //插入数据_finish++;}vector<string> v1;v1.push_back("zhangsan");v1.push_back("lisi");v1.push_back("wangwu");v1.push_back("zhaoqan");v1.insert(v1.begin(), "lala");for (auto& e : v1){cout << e << ' ';}
无返回值
void insert(iterator pos, const T& val) //在pos位置前插入元素{assert(pos >= _start && pos <= _finish); //断言，确保在[_start,_finish]范围内插入数据if (_finish == _endofstorage) //空间满了，扩容{size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newcapacity);pos = _start + len; //扩容会导致pos位置失效，更新pos位置}//此处数据往后挪动，既可以用memmove，又可以用迭代器//memmove(pos + 1, pos, sizeof(T) *( _finish - pos)); //memmove为值拷贝iterator tmp = _finish - 1;while (tmp >= pos) {*(tmp + 1) = *tmp;tmp--;}*pos = val; //插入数据_finish++;}vector<string> v1;v1.push_back("zhangsan");v1.push_back("lisi");v1.push_back("wangwu");v1.push_back("zhaoqan");vector<string>::iterator pos = std::find(v1.begin(), v1.end(), "zhangsan");v1.insert(pos, "zzx");v1.insert(pos, "lala"); //出错处for (auto& e : v1){cout << e << ' ';}
erase
iterator erase(iterator pos){assert(pos >= _start && pos < _finish); //断言，确保在[_start,_finish)范围内删除数据assert(size() > 0); //断言，无任何数据，不能在进行删除操作//此处数据往前覆盖pos位置，既可以用memmove，又可以用迭代器//memmove(pos, pos + 1, sizeof(T) * (_finish - pos - 1)); memmove为值拷贝iterator tmp = pos;while (tmp < _finish - 1){*tmp = *(tmp + 1);tmp++;}_finish--;return pos;}无返回值
void erase(iterator pos){assert(pos >= _start && pos < _finish); //断言，确保在[_start,_finish)范围内删除数据assert(size() > 0); //断言，无任何数据，不能在进行删除操作memmove(pos, pos + 1, sizeof(T) * (_finish - pos - 1));_finish--;}vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//删除v中的奇数auto it = v.begin();while (it != v.end()){if (*it % 2 != 0)v.erase(it);it++;}for (auto& e : v){cout << e << ' ';}cout << endl;
vectorv{1,2,3},it=v.begin(),erase(it)后,it中数据为2,在直接it++,此时it中数据为3，erase(it)后，it=v.end(),而end位置是没有元素的，那么pos就失效了。在it++, 就越界了assert条件为假，导致程序崩溃。此时只需要给it重新赋值，即：添加返回值。
vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//删除v中的奇数auto it = v.begin();while (it != v.end()){if (*it % 2 != 0)it = v.erase(it);elseit++;}for (auto& e : v){cout << e << ' ';}cout << endl;
迭代器失效
定义
在c++中，容器的insert、erase等操作可能会引起迭代器失效，如果在迭代器已经失效的情况下，继续使用失效的迭代器来访问容器内的数据，会引起运行时程序崩溃或者产生不可预期的结果，这种情况就称为迭代器失效。insert导致的迭代器失效
vector<string> v1;v1.push_back("zhangsan");v1.push_back("lisi");v1.push_back("wangwu");v1.push_back("zhaoqan");v1.insert(v1.begin(), "lala");for (auto& e : v1){cout << e << ' ';}
erase导致的迭代器失效
删除vector中的奇数
void erase(iterator pos){assert(pos >= _start && pos < _finish); //断言，确保在[_start,_finish)范围内删除数据assert(size() > 0); //断言，无任何数据，不能在进行删除操作memmove(pos, pos + 1, sizeof(T) * (_finish - pos - 1));_finish--;}vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//删除v中的奇数auto it = v.begin();while (it != v.end()){if (*it % 2 != 0)v.erase(it);it++;}for (auto& e : v){cout << e << ' ';}cout << endl;erase删除pos位置元素后，pos位置之后的元素会往前挪动，无底层空间的变化，但是如果pos刚好为最后一个元素，删完之后pos刚好为end位置，而end位置上无元素，那么pos也就失效了，此时只需要给it重新赋值，即：添加返回值。
删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。
?Tips: 迭代器失效——》不会引起底层空间发生变化，迭代器指向了错误的位置。
vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//删除v中的奇数auto it = v.begin();while (it != v.end()){if (*it % 2 != 0)it = v.erase(it);elseit++;}for (auto& e : v){cout << e << ' ';}cout << endl;
? Tips：在erase的实现中，不能保证编译器是否会进行缩容，但是缩容会导致迭代器失效。insert和erase的pos可能都会失效，所以对于insert和erase使用过的迭代器不要去使用。
非法的间接寻址
vector<string> v1(5, "zzx");for (auto& e : v1){cout << e << ' ';}cout << endl;vector<int> v2(5, 2);for (auto& e : v2){cout << e << ' ';}cout << endl;
铁铁们，vector模拟实现+迭代器失效就到此结束啦，若博主有不好的地方，请指正，欢迎铁铁们留言，请动动你们的手给作者点个?鼓励吧，你们的鼓励就是我的动力✨