【C++】vector类常用接口及模拟实现

一、vector简介

vector在STL中表示顺序表，使用vector要包含vector头文件。
vector是一个模板，使用时要指定其中存储的数据类型（类模板只能显式实例化）。
vector不支持流插入和流提取，所以不能直接用cin、cout输入输出
vector文档介绍

二、vector的使用（常用接口）

1.vector的定义（构造方法）

#include<iostream>#include<vector>usingnamespace std;intmain(){// 默认构造 vector<int> v1;// 使用10个1初始化 vector<int>v2(10,1);// 使用v2的迭代器区间初始化 vector<int>v3(v2.begin(), v2.end());// 拷贝构造 vector<int>v4(v3);return0;}

2.vector的遍历

vector的遍历有三种方法：下标+[]、迭代器、范围for

（1）下标+[]

#include<iostream>#include<vector>usingnamespace std;intmain(){ vector<int>v(10,1);for(size_t i =0; i < v.size(); i++){ cout << v[i]<<" ";} cout << endl;return0;}

（2）迭代器

#include<iostream>#include<vector>usingnamespace std;intmain(){ vector<int>v(10,1); vector<int>::iterator it = v.begin();while(it != v.end()){ cout <<*it <<" ";++it;} cout << endl;return0;}

（3）范围for

范围for的底层是迭代器

#include<iostream>#include<vector>usingnamespace std;intmain(){ vector<int>v(10,1);for(auto e:v){ cout << e <<" ";} cout << endl;return0;}

3.vector类对象的容量操作

（1）resize

改变vector的size，同时对新增数据初始化（未指定就调用默认构造）。resize一般不会缩容，但会改变size：小于size时删除数据，大于size时插入数据，空间不够时会扩容

#include<iostream>#include<vector>usingnamespace std;intmain(){ vector<int>v(10,1);for(auto i : v){ cout << i <<" ";} cout << endl; cout << v.size()<< endl; cout << v.capacity()<< endl; v.reserve(20);for(auto i : v){ cout << i <<" ";} cout << endl; cout << v.size()<< endl; cout << v.capacity()<< endl; v.resize(15,2);for(auto i : v){ cout << i <<" ";} cout << endl; cout << v.size()<< endl; cout << v.capacity()<< endl; v.resize(5);for(auto i : v){ cout << i <<" ";} cout << endl; cout << v.size()<< endl; cout << v.capacity()<< endl;return0;}

（2）capacity

#include<iostream>#include<vector>usingnamespace std;intmain(){ vector<int>v(10,1); cout << v.size()<< endl; cout << v.capacity()<< endl; v.reserve(20); cout << v.size()<< endl; cout << v.capacity()<< endl; v.reserve(15); cout << v.size()<< endl; cout << v.capacity()<< endl; v.reserve(5); cout << v.size()<< endl; cout << v.capacity()<< endl;return0;}

从运行结果可以看出，把capacity改成20后，再使用reserve不会减小vector的capacity

4.vector增删查改

（1）push_back和insert

#include<iostream>#include<vector>usingnamespace std;intmain(){ vector<int>v(10,1);// 使用push_back尾插元素 v.push_back(2);for(auto i : v){ cout << i <<" ";} cout << endl;// 在起始位置插入元素 v.insert(v.begin(),3);for(auto i : v){ cout << i <<" ";} cout << endl;// 在下标为3的位置插入元素 v.insert(v.begin()+3,4);for(auto i : v){ cout << i <<" ";} cout << endl;return0;}

（2）erase

erase可以删除一个位置，也可以删除一段迭代器区间

#include<iostream>#include<vector>usingnamespace std;intmain(){ vector<int>v(10,1);// 删除起始位置 v.erase(v.begin());for(auto i : v){ cout << i <<" ";} cout << endl;// 删除下标为3的位置 v.erase(v.begin()+3);for(auto i : v){ cout << i <<" ";} cout << endl;return0;}

5.vector的使用

vector不仅可以存储内置类型，还可以存储自定义类型甚至存储vector

使用vector存储vector

使用vector存储vector可以看作二维数组，也可以像访问二维数组一样使用[][]访问（实际上是两次函数调用）。

#include<iostream>#include<vector>usingnamespace std;intmain(){ vector<int>v(10,0);// 使用vector存储vector，相当于5行10列的二维数组 vector<vector<int>>vv(5, v);// 使用下标+[]访问vectorfor(int i =0; i < vv.size(); i++){for(int j =0; j < vv[i].size(); j++){ cout << vv[i][j]<<" ";} cout << endl;} cout << endl;return0;}

三、vector迭代器失效问题

迭代器的主要作用是让算法能够不用关心底层数据结构，其底层就是一个指针，或者对指针进行了封装，比如vector的迭代器其实就是原生指针T*。因此迭代器失效实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间（类似野指针），造成的后果就是程序崩溃（即如果继续使用已经失效的迭代器，程序可能会崩溃）
对于vector可能会导致其迭代器失效的操作有：

1. 会引起其底层空间改变的操作，都有可能使迭代器失效，比如：resize、reserve、insert、assign、push_back等

#include<iostream>usingnamespace std;#include<vector>intmain(){ vector<int> v{1,2,3,4,5};auto it = v.begin();// 将有效元素个数加到100个，多出的位置用8填充，操作期间底层会扩容//v.resize(100,8)// reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变//v.reservr(100)// 插入元素期间，可能会引起扩容，导致原空间被释放//v.insert(v.begin(), 0);//v.push_back(8)// 给vector重新赋值，可能会引起底层容量改变//v.assign(100, 8);/* 出错原因：以上操作都有可能导致vector扩容，也就是说vector底层原来的旧空间被释放掉，而在打印时，it还使用的释放之前的旧空间，在对it迭代器操作时，实际操作的是一块被释放掉的空间，而引起代码运行时崩溃 解决方式：在以上操作完成后，如果想要继续通过迭代器操作vector中的元素，只需给it重新赋值即可 */while(it != v.end()){ cout <<*it <<" ";++it;} cout << endl;return0;}

2. 指定位置元素的删除操作

#include<iostream>usingnamespace std;#include<vector>intmain(){int a[]={1,2,3,4}; vector<int>v(a, a +sizeof(a)/sizeof(a[0]));// 使用find查找3所在位置的iterator vector<int>::iterator pos =find(v.begin(), v.end(),3);// 删除pos位置的数据，导致pos迭代器失效 v.erase(pos); cout <<*pos << endl;// 此处会导致非法访问return0;}

erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上迭代器不会失效，但是如果pos刚好是最后一个元素，删除之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。

3. 注意：在Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs极端。在Linux下迭代器失效后，代码不一定会崩溃，但运行结果肯定不对，如果it不再begin到end范围内，程序一定会崩溃
4. 与vector类似，string在插入+扩容操作+erase之后，迭代器也会失效

#include<iostream>usingnamespace std;#include<string>intmain(){ string s("hello");auto it = s.begin();// 放开之后程序会崩溃，因为resize到20string会进行扩容// 扩容之后，it指向之前的旧空间已经被释放了，该迭代器就会失效// 后序打印时，再访问it指向的空间，程序就会崩溃//s.resize(20, '!');while(it != s.end()){ cout <<*it;++it;} cout << endl; it = s.begin();while(it != s.end()){ it = s.erase(it);// 按照下面方式写，运行时程序会崩溃，因为在erase(it)之后，it位置的迭代器就失效了//s.erase(it);++it;}return0;}

迭代器失效的解决办法：在使用前对迭代器重新赋值即可。

四、Victor模拟实现

#pragmaonce#include<iostream>#include<assert.h>usingnamespace std;namespace zsy {template<classT>classvector{public:typedef T* iterator;typedefconst T * const_iterator;// 默认构造//vector() {}// c++11:强制生成默认构造vector()=default;// 拷贝构造vector(const vector<T>& v){reserve(v.size());for(auto& e : v){push_back(e);}}// 类模板的成员函数可以是函数模板// 迭代器区间构造（可以使用任意容器的迭代器初始化vector，但要求类型是匹配的）template<classInputIterator>vector(InputIterator first, InputIterator last){while(first != last){push_back(*first);++first;}}vector(size_t n,const T& val =T()){reserve(n);for(size_t i =0; i < n; i++){push_back(val);}}voidclear(){ _finish = _start;}// v1 = v3// 赋值重载// 传统写法//const vector<T>& operator=(const vector<T>& v) {// if (this != &v) {// clear();// reserve(v.size());// for (auto e : v) {// push_back(e);// }// }// return *this;//}voidswap(vector<T>& v){ std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage);}// 现代写法const vector<T>&operator=(vector<T> v){swap(v);return*this;}~vector(){if(_start){delete[] _start; _start = _finish = _end_of_storage =nullptr;}}// 迭代器 iterator begin(){return _start;} iterator end(){return _finish;} const_iterator begin()const{return _start;} const_iterator end()const{return _finish;}// 扩容voidreserve(size_t n){if(n >capacity()){ size_t old_size =size(); T* tmp =new T[n];// 使用memcpy会产生深拷贝问题//memcpy(tmp, _start, old_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 = _start + n;}}voidresize(size_t n,const T& val =T()){if(n <size()){ _finish = _start + n;}else{reserve(n);while(_finish <= _start + n){ _finish = val;++_finish;}}} size_t size()const{return _finish - _start;} size_t capacity()const{return _end_of_storage - _start;}boolempty(){return _start == _finish;}// 尾插voidpush_back(const T& x){// 如果满了就先扩容if(_finish == _end_of_storage){reserve(capacity()==0?4:capacity()*2);}*_finish = x;++_finish;}// 尾删voidpop_back(){assert(!empty());--_finish;}// 这种比较长的函数可以在类里面声明、类外面定义，但不能分成两个文件，否则会链接错误 iterator 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 = _start + len;} iterator end = _finish -1;while(end >= pos){*(end +1)=*end;--end;}*pos = x; _finish++;// insert之后迭代器会失效，要访问就要更新这个失效的迭代器// 返回新插入元素，可以解决迭代器失效问题return pos;} iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish); iterator it = pos +1;while(it !=end()){*(it -1)=*it;++it;}--_finish;return pos;} T&operator[](size_t i){assert(i <size());return _start[i];}const T&operator[](size_t i)const{assert(i <size());return _start[i];}private: iterator _start =nullptr; iterator _finish =nullptr; iterator _end_of_storage =nullptr;};template<classT>voidprint_vector(const vector<T>& v){// 规定：从未实例化的类模板中取东西，编译器不能区分这里的const_iterator是类型还是静态成员变量，需要加上typename//typename vector<T>::const_iterator it = v.begin();// 也可以直接将类型名写成autoauto it = v.begin();while(it != v.end()){ cout <<*it <<" ";++it;}}}