vector的介绍及使用vector的介绍https://cplusplus.com/reference/vector/vector/使用STL的三个境界能用明理能扩展 那么下面学习vector我们也是按照这个方法去学习vector的使用vector学习时一定要学会查看文档vector的文档介绍vector在实际中非常的重要在实际中我们熟悉常见的接口就可以下面列出了哪些接口是要重点掌握的vector的定义构造函数声明接口说明vector()(重要)无参构造vectorsize_type n, const value_type val value_type()构造并初始化n个valvector (const vector x); 重点拷贝构造vector (InputIterator first, InputIterator last)使用迭代器进行初始化构造vector 迭代器的使用迭代器的使用接口说明beginend重要获取第一个数据位置的iterator/const_iterator 获取最后一个数据的下 一个位置的iterator/const_iteratorrbeginrend重要获取最后一个数据位置的reverse_iterator获取第一个数据前一个位置 的reverse_iteratorvector 空间增长问题容量空间接口说明size获取数据个数capacity获取容量大小empty判断是否为空resize重点改变vector的sizereserve 重点改变vector的capacitycapacity的代码在vs和g下分别运行会发现vs下capacity是按1.5倍增长的g是按2 倍增长的。这个问题经常会考察不要固化的认为vector增容都是2倍具体增长多少是根据具体的需求定义的。vs是PJ版本STLg是SGI版本STLreserve只负责开辟空间如果确定知道需要用多少空间reserve可以缓解vector增容的代价缺陷问题resize在开空间的同时还会进行初始化影响sizevector 增删查改vector增删查改接口说明push_back重点尾插pop_back 重点尾删find查找。注意这个是算法模块实现不是vector的成员接口insert在指定位置之前插入数字erase删除指定位置的数据swap交换两个vector的数据空间operator[] 重点像数组一样访问vector 迭代器失效问题重要迭代器的主要作用就是让算法能够不用关心底层数据结构其底层实际就是一个指针或者是对 指针进行了封装比如vector的迭代器就是原生态指针T* 。因此迭代器失效实际就是迭代器 底层对应指针所指向的空间被销毁了而使用一块已经被释放的空间造成的后果是程序崩溃(即 如果继续使用已经失效的迭代器程序可能会崩溃)对于vector可能会导致其迭代器失效的操作有1.会引起其底层空间改变的操作都有可能是迭代器失效比如resize、reserve、insert、 assign、push_back等先使用resize进行测试#includeiostream #includevector using namespace std; int main() { vectorint v{ 1,2,3,4,5,6 }; auto it v.begin(); v.resize(100, 8); //将有效元素个数加到100剩下的空间使用8来填充操作期间底层会扩容 while (it ! v.end()) { cout *it ; it; } cout endl; return 0; }运行结果reserve#includeiostream #includevector using namespace std; int main() { vectorint v{ 1,2,3,4,5,6 }; auto it v.begin(); v.reserve(100);//reserve的作用是改变大小但不改变元素个数操作期间也会引起底层容量改变 while (it ! v.end()) { cout *it ; it; } cout endl; return 0; }运行结果insert:#includeiostream #includevector using namespace std; int main() { vectorint v{ 1,2,3,4,5,6 }; auto it v.begin(); v.insert(v.begin(), 0);//插入元素期间可能会引起容量改变导致空间被释放 while (it ! v.end()) { cout *it ; it; } cout endl; return 0; }运行结果push_back#includeiostream #includevector using namespace std; int main() { vectorint v{ 1,2,3,4,5,6 }; auto it v.begin(); v.push_back(5);//插入元素期间可能会引起扩容导致空间被释放 while (it ! v.end()) { cout *it ; it; } cout endl; return 0; }运行结果assgin:#includeiostream #includevector using namespace std; int main() { vectorint v{ 1,2,3,4,5,6 }; auto it v.begin(); v.assign(100, 8);//给vector赋值会引起底层容量改变 while (it ! v.end()) { cout *it ; it; } cout endl; return 0; }运行结果2.指定位置元素的删除操作--erase代码void test_vector2() { int a[] { 1,2,3,4 }; vectorint v(a, a sizeof(a) / sizeof(int)); vectorint::iterator pos find(v.begin(), v.end(), 3); v.erase(pos); cout *pos endl; }运行结果erase删除pos位置元素后pos位置之后的元素会往前搬移没有导致底层空间的改变理论上讲迭代器不应该会失效但是如果pos刚好是最后一个元素删完之后pos刚好是end的位置而end位置是没有元素的那么pos就失效了。因此删除vector中任意位置上元素时vs就认为该位置迭代器失效了3.与vector类似string在插入扩容操作erase之后迭代器也会失效resize(扩容):void test_string1() { string s(hello); auto it s.begin(); //放开之后会崩溃因为resize到20的时候就会扩容 //扩容后it指向的空间已经被释放了因此迭代器会失效 //后续在访问it指向的空间程序就会崩溃 s.resize(20, !); while (it ! s.end()) { cout *it; it; } cout endl; }erase:void test_string1() { string s(hello); auto it s.begin(); it s.begin(); while (it ! s.end()) { it s.erase(it); s.erase(it); //按下面的方式写程序运行时崩溃因为eraseit之后it的迭代器就失效了 it; } }运行结果运行结果迭代器失效解决办法在使用前对迭代器重新赋值即可vector深度剖析及模拟实现平常在写模拟实现的代码时声明与定义会进行分离可是在写模板的时候声明和定义不能进行分离否则会出现链接错误我们现在开始进行模拟实现基础架构templateclass T class vector { public: typedef T* iterator; private: iterator _start; iterator _finish; iterator _end_of_storage; };初始化这里使用nullptr作为初始值vector() :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) {}push_back(尾插)在写尾插代码前我们要先写上reserve、size和capacity函数代码先写上size和capacity的代码sizesize是用于取得一个空间中数据的长度从start到finish的长度就是一个size的大小代码size_t size() const { return _finish - _start; }capacity(整体空间长度)capacity用于取得这个空间大小从end_of_stroage到_start的长度就是这个空间的大小代码size_t capacity() const { return _end_of_storage - _start; }reserve(预开辟空间)用于预先开辟新空间防止存储空间进行扩容的次数过多影响效率代码void reserve(size_t n) { if (n capacity()) { T* tmp new T[n]; if (_start) { memcpy(tmp, _start, sizeof(T) * size()); delete[] _start; } _start tmp; _finish _start size(); _end_of_storage _start n; } }接下来就可以开始写尾插了尾插是将一个个的数据插入空间中代码void reserve(size_t n) { if (n capacity()) { T* tmp new T[n]; if (_start) { memcpy(tmp, _start, sizeof(T) * size()); delete[] _start; } _start tmp; _finish _start size(); _end_of_storage _start n; } }这里会有个坑先来进行调试先进入函数再次走到断点处再次进入函数首先会返回全部的空间大小如果相等就会进行扩容此时的capacity为0因此会进行扩容进入后会先检查n是否大于capacity检查完之就会开始扩容接着往下走代码突然报错这是为啥我们回去检查reserve可是这里的ncapacity没问题if部分也没啥问题memcpy也没啥问题delete[]也没啥问题问题就只会出现在下面的赋值了我们先看向监视我们看到start变了、end_of_stroange也变了可是finish没有变这是为啥因为size函数里的finish值为0可是start已经有变动了因此变成了0-start因此size中变成负值所以会出错那么要怎么解决呢我们把旧的size存储起来代码void reserve(size_t n) { if (n capacity()) { size_t old_size size(); T* tmp new T[n]; if (_start) { memcpy(tmp, _start, sizeof(T) * old_size); delete[] _start; } _start tmp; _finish _start old_size; _end_of_storage _start n; } }之后调试就没有问题了我们来运行下测试文档void test_vector() { Vector::vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); for (size_t i 0; i v.size();i) { cout v[i] ; } cout endl; } int main() { test_vector(); return 0; }运行结果下标符号重载将数组中下标符号进行重载代码T operator[](size_t i) { assert(i size()); return _start[i]; }迭代器在写迭代器前自定义类中无法使用库中的begin和end函数所以要自己写beginvoid begin() { return _start; }end:void end() { return _finish; }我们写上迭代器void test_vector() { Vector::vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); for (auto e : v) //迭代器 { cout e ; } cout endl; }运行结果我们可以把它写成一个函数void Print(Vector::vectorint v) { for (auto e : v) { cout e ; } cout endl; }运行结果可是这里有一个问题如果我们在函数参数中加上const呢void Print(const Vector::vectorint v) { for (auto e : v) { cout e ; } cout endl; }我们发现它报错了我们来看报错原因报错说不能将“this”指针从“const Vector::vectorint”转换为“Vector::vectorint ”说明这里涉及了权限放大那么要怎么解决呢我们使用const_iterator类型就可以解决此问题const_iterator begin() const { return _start; } const_iterator end() const { return _finish; }这样就不报错了我们再来运行下测试文档void test_vector() { Vector::vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); Print(v); }运行结果pop_back(尾删)pop_back比起push_back逻辑简单些我们先来写代码void pop_back() { --_finish; }我们来运行下测试文档void test_vector2() { Vector::vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); Print(v); v.pop_back(); v.pop_back(); Print(v); v.pop_back(); v.pop_back(); Print(v); }运行结果这里有个问题这里有插入五个数字如果我们删六次会发生什么事呢void test_vector2() { Vector::vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); Print(v); v.pop_back(); v.pop_back(); Print(v); v.pop_back(); v.pop_back(); Print(v); v.pop_back(); v.pop_back(); Print(v); }运行结果我们发现他崩溃了这是为啥呢因为我删除了六次可是数字只有五个当数字删除完之后就没有东西可以删因此会出现乱码因此我们需要加上assert断言void pop_back() { assert(_finish _start); --_finish; }我们再运行一次这样就会出现断言报错了我们还可以使用这个方法这个办法我们需要写一个empty函数bool empty() { return _finish _start; }在pop_back上使用emptyvoid pop_back() { assert(!empty()); --_finish; }运行结果insert(指定位置插入pos)我们需要在pos插入数据void insert(iterator pos, const T x) { assert(pos _start); assert(pos _finish); if (_finish _end_of_storage) { reserve(capacity() 0 ? 4 : capacity() * 2); } iterator end _finish - 1; while (end pos) { *(end 1) *end; --end; } *pos x; _finish; }这里有个坑我们来看看怎么回事先用这两个实例进行测试测试文档void test_vector3() { Vector::vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); Print(v); v.insert(v.begin(),0); Print(v); v.insert(v.begin()2, 0); Print(v); }我们再写上一个实例void test_vector3() { Vector::vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); Print(v); int x; cin x; auto it find(v.begin(), v.end(), x); if (it ! v.end()) { v.insert(it,x * 10); } Print(v); }运行结果如果我们把第五个push_back删掉会出现什么事呢void test_vector3() { Vector::vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); //v.push_back(5); Print(v); v.insert(v.begin(),0); Print(v); v.insert(v.begin()2, 0); Print(v); int x; cin x; auto it find(v.begin(), v.end(), x); if (it ! v.end()) { v.insert(it,x * 10); //it失效这里it是否还能使用不能 //扩容会导致it失效但是C标准没有规定vector扩容规则 //所以我们这里认为insert后it就失效了it无法使用 *it 1000; } Print(v); }运行结果我们发现我们一运行就报错这是为啥这里涉及一种情况叫迭代器失效当我插入五个数字时reverse会先扩容到8个因此在插入其他数字时不会有问题。可是当我只插入四个数字时只会开四个空间当我插入新的数字时reverse会开辟一块更大的新内存空间开完空间后就空间就会失效可是指针指向的还是旧空间因此会出现野指针那要怎么解决呢先将pos之前的数据返回之后再将pos更新void insert(iterator pos, const T x) { assert(pos _start); assert(pos _finish); if (_finish _end_of_storage) { size_t len pos - _start; reserve(capacity() 0 ? 4 : capacity() * 2); //如果触发扩容就需要更新pos pos _start len; } iterator end _finish - 1; while (end pos) { *(end 1) *end; --end; } *pos x; _finish; }再来运行一次erase(指定pos删除)我们需要将pos的数据删除代码void erase(iterator pos) { assert(pos _start); assert(pos _finish); iterator it pos 1; while (it ! _finish) { *(it - 1) *it; it; } --_finish; }测试文档void test_vector4() { Vector::vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); Print(v); v.erase(v.begin()); Print(v); }运行结果再添加一个用例void test_vector4() { Vector::vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); Print(v); int x; cin x; auto it find(v.begin(), v.end(), x); if (it ! v.end()) { v.erase(it); } Print(v); }运行结果resize(更改size的大小可以往size里加入数据代码void resize(size_t n, T val T()) { if (n size()) { reserve(n); while (_finish ! _start n) { *_finish val; _finish; } } else { _finish _start n; } }测试文档void test_vector6() { Vector::vectorint v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); Print(v); v.resize(7); Print(v); v.resize(20,1); Print(v); }运行结果拷贝构造函数代码vector(const vectorT v) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { reserve(v.capacity()); for (auto e : v) { push_back(e); } }测试文档void test_vector7() { Vector::vectorint v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); Print(v1); Vector::vectorint v2(v1); Print(v2); }运行结果我们还可以拷贝数组不过我们还需要写上另一个参数的代码vector(initializer_listT il) { reserve(il.size()); for (auto e : il) { push_back(e); } }测试文档void test_vector7() { Vector::vectorint v1; v1.push_back(1); v1.push_back(2); v1.push_back(3); v1.push_back(4); v1.push_back(5); Print(v1); Vector::vectorint v3 { 1,2,3,4,5,0 }; Vector::vectorint v4 { 1,2,3,4,5,51,1,1,1,1,1,1 }; Print(v3); Print(v4); }运行结果也可以只拷贝一部分的数字代码vector(iterator first, iterator last) { while (first ! last) { push_back(*first); first; } }测试文档void test_vector7() { Vector::vectorint v3 { 1,2,3,4,5,0 }; Vector::vectorint v4 { 1,2,3,4,5,51,1,1,1,1,1,1 }; Vector::vectorint v5(v3.begin()1, v3.end()-1); Print(v5); }运行结果再来看下标准库是怎么解决的我们看到他使用的是函数模板那么为啥会这样弄呢如果我要使用的类型是string类呢string s1(hello world); Vector::vectorint v6(s1.begin(), s1.end());代码就会出现报错如果我们时候函数模板就可以避免这个问题template class InputIterator vector(InputIterator first, InputIterator last) { while (first ! last) { push_back(*first); first; } }先来运行下测试文档string s1(hello world); Vector::vectorint v6(s1.begin(), s1.end()); Print(v6);运行结果赋值符号重载我们现在测试用例写上这段代码v1 v7; Print(v1);我们先来运行下它崩溃了可是为啥会崩溃呢因为在自定义类型中什么符号都要自己重载我们先写上重载代码在写这个代码前要先写上swap的代码swap代码void swap(vectorT v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); }再写上赋值符号重载的代码vectorT operator(vectorT v) { swap(v); return *this; }我们再来运行一次运行结果附录拷贝构造函数还有一个“坑”会是什么坑呢我们先写上一个代码void test_vector8() { Vector::vectorstring v1; v1.push_back(111111111111111111111); v1.push_back(111111111111111111111); v1.push_back(111111111111111111111); v1.push_back(111111111111111111111); v1.push_back(111111111111111111111); Print(v1); }我们来运行一次我们看到出现乱码了这是为啥呢先调试看看首先现在监视窗口输入this接下来走到函数里首先数据要进行插入动作插入之前要检查空间是否足够得出的结果是需要扩容进入reserve函数进入函数后首先会检查ncapacity检查过后回到继续往下走之后会检查start是否为空不为空则不进入循环我们看到并没有进入if条件接着走下去此时看到_start改变了地址_finish也改变了地址接着往下走我们看到了end_of_storage也发生了改变此时回到了push_back的位置再往下走后_start和_finish都读入了数据往下走后_finish往后走一步这样就回到了测试文档我们接着走下去看是哪里出了问题我们发现走到第五个的时候就开始无法读取数据了因此我们可以发现是扩容出现了问题可是为啥扩容会出现问题呢当我将数据memcpy到新空间的时候只进行了浅拷贝拷贝完后_start就会被删除可是tmp还是指向旧空间因此会出现野指针那么要怎么解决呢我们可以改用深拷贝把memcpy改用循环调用赋值运算符void reserve(size_t n) { if (n capacity()) { size_t old_size size(); T* tmp new T[n]; if (_start) { for (size_t i 0; i old_size; i) { tmp[i] _start[i]; } delete[] _start; } _start tmp; _finish _start old_size; _end_of_storage _start n; } }运行结果