文章目录 各位小伙伴们，大家好！我是bug。今天我们来谈谈vector的相关内容：
（代码可能会有一点问题，请各位老铁指正 ）
- 一、vector的概念
- 二、vector的用法
- （1）vector对象的创建
- （2）vector的遍历
- （3）vector的reserve和resize
- （4）迭代器失效问题****
- 三、vector的模拟实现
二、vector的用法 Vector： vector是C++标准模板库中的部分内容。它是动态增长的对象数组，它是一个多功能的，能够操作多种数据结构和算法的模板类和函数库。
vector的常用接口：
| construct（构造函数） | 用法 |
|---|---|
| vector() | 无参构造函数 |
| vector（size_type n, const value_type& val = value_type()） | 构造初始化n个val |
| vector (const vector& x); | 拷贝构造 |
| vector (InputIterator first, InputIterator last); | 迭代器初始化构造 |
| 遍历操作 | 用法 |
|---|---|
| operator[] | 数组 |
| begin | 获取第一个数据位置的iterator/const_iterator |
| end | 获取最后一个数据的下一个位置的iterator/const_iterator |
| rbegin | 获取最后一个数据位置的reverse_iterator |
| rend | 获取第一个数据前一个位置的reverse_iterator |
| 操作空间/容量 | 用法 |
|---|---|
| size | 获取数据个数 |
| capacity | 获取容量大小 |
| empty | 判断是否为空 |
| resize | 改变vector的size |
| reserve | 改变vector的capacity |
| 修改操作 | 用法 |
|---|---|
| push_back | 尾插 |
| pop_back | 尾删 |
| insert | 在position之前插入数据 |
| erase | 删除position位置的数据 |
| swap | 交换两个vector的数据空间 |
vector创建对象的方式有很多，比如：
使用默认构造函数
使用带参构造函数
使用拷贝构造函数
使用赋值运算符重载
使用迭代器区间进行构造
创建匿名对象
代码⬇️ ⬇️：
//有参数构造 vector（2）vector的遍历v1(5, 4); //无参数构造 vector v2; //拷贝构造 vector v3(v1); //迭代器区间进行构造 vector v4(v1.begin(), v1.end()); //赋值运算符重载 vector v5 = v1; //匿名对象 vector ();
string有三种遍历的方式：
通过[]的重载像数组一样遍历。
通过迭代器进行遍历。
通过范围for进行的遍历
代码⬇️ ⬇️：
//遍历,和string类似，这里就不详细演示了 vectorv(4, 5); //[]重载 for (size_t i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << endl; //迭代器 vector ::iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; it++; } cout << endl; //范围for for (auto e : v) { cout << e << " "; } cout << endl;
注意❗️ ❗️
（3）vector的reserve和resize （1）[]的重载有const和非const版本的。
（2）迭代器有const和非const版本的，C98中直接将begin、end进行重载。在C11中为了区别const和非const迭代器，引入了cbegin和cend。（和begin、end的const版本就名字不同）
（3）范围for的本质是迭代器，程序运行过程中，编译器会把范围for替换成迭代器进行操作。同时范围for是通过赋值的方式进行遍历（将数据赋给变量），如果要修改，就要使用引用。
测试代码⬇️ ⬇️：
vector（4）迭代器失效问题****v(4, 5); //打印容量 cout << v.capacity() << endl; v.reserve(3); cout << v.capacity() << endl; v.reserve(8); cout << v.capacity() << endl; //只能扩容，和string一样 v.resize(2); //打印容量 cout << v.capacity() << endl; //遍历 auto it = v.begin(); while (it != v.end()) { cout << *it << " "; it++; } cout << endl; v.resize(12, 0); //要重新对it赋值，因为扩容之后迭代器begin发生了改变 //这里的begin是原生指针 it = v.begin(); //打印容量 cout << v.capacity() << endl; while (it != v.end()) { cout << *it << " "; it++; } cout << endl;
迭代器失效有两种情况：
1.、会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等。
2、erase删除数据
解决方法：对it重新赋值。
这里我们来仔细谈谈迭代器失效：
在vector的类中，我们并没有实现find函数，我们使用的是算法里面的查找函数，当我们使用insert进行插入、或者使用erase删除等操作时，都需要找到数据的位置然后进行相应的操作。
但是会有这几种情况发生：
（1）使用insert等接口时，底层空间发生了改变。
从底层的角度我们不难发现，以扩容为例，过程大致分为这么几个步骤：
这个时候我们之前使用的find函数返回的指针仍然指向之前的那片空间(被释放掉了)，即这个指针就是野指针了。
在vector中，为了解决这个问题，采取了返回iterator的方式。即通过insert返回新的指针，指向之前查找的那个数字。
（2）使用erase时，我们要进行连续删除。
举个栗子：删除vector对象中所存储的奇数：
这个代码有什么问题吗？⬇️ ⬇️（vs上编不过）
#include#include using std::cin; using std::cout; using std::endl; using std::vector; int main() { vector v(4, 5); auto it = std::find(v.begin(), v.end(), 5); while (it != v.end()) { v.erase(it); it++; } cout << endl; return 0; }
如图分析：
在上图这情况下，结果看起来是没有什么问题，但是如果是下面这种呢？
即每次删除一个奇数数据后，会跳过一个数据同时判断下一个数据是否是奇数。当发生极端情况，即最后一个数据是奇数,被删除后，it发生了自增操作，就会直接越过end，然后不断的循环越界。（迭代器就失效了）
所以为了避免这种情况，我们同样采用了返回iterator的形式，通过返回一个修正值来避免迭代器失效。
代码⬇️ ⬇️：
#include#include using std::cin; using std::cout; using std::endl; using std::vector; int main() { vector v(4, 5); auto it = std::find(v.begin(), v.end(), 5); while (it != v.end()) { //通过接收erase返回后的修正值防止迭代器失效 it = v.erase(it); it++; } cout << endl; return 0; }
三、vector的模拟实现总结：解决迭代器失效的方法就是重新对it进行赋值操作。
这里我们来实现一个简易的vector⬇️ ⬇️：
typedef _Tp* iterator; typedef const _Tp* const_iterator; //构造函数 vector() vector(size_t n, const _Tp& val = _Tp()) vector(const vector& v1) vector(InputIterator start, InputIterator finish) void swap(vector& v) vector& operator=(const vector& v1) //遍历操作 _Tp& operator[](size_t i) const _Tp& operator[](size_t i)const iterator begin() const iterator end() const const_iterator cbegin()const const_iterator cend()const //扩容操作 void reserve(size_t n) void resize(size_t n, _Tp val = _Tp()) //增删操作 void push_back(const _Tp& t) void pop_back(size_t n) iterator insert(iterator pos, const _Tp& val) iterator insert(iterator pos, size_t n, const _Tp& val) iterator erase(iterator pos) iterator erase(iterator start, iterator finish) //其他 void clear() bool empty()
完整代码⬇️ ⬇️：
#include#include #include using std::cin; using std::cout; using std::endl; using std::istream; using std::ostream; namespace lz { template class vector { public: //迭代器 typedef _Tp* iterator; typedef const _Tp* const_iterator; iterator begin() const { return _start; } iterator end() const { return _finish; } const_iterator cbegin()const { return _start; } const_iterator cend()const { return _finish; } typedef _Tp* InputIterator; size_t size()const { return _finish - _start; } size_t capacity()const { return _end_of_storage - _start; } // 构造函数 vector(InputIterator start, InputIterator finish) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { while (start != finish) { push_back(*start); start++; } } vector(size_t n, const _Tp& val = _Tp()) :_start(new _Tp[n]) , _finish(_start + n) , _end_of_storage(_finish) { auto it = begin(); while (it != _finish) { *it = val; it++; } } vector() : _start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) {} // 析构函数 ~vector() { delete[]_start; _start = _finish = nullptr; _end_of_storage = nullptr; } // 拷贝构造函数 vector(const vector& v1) { reserve(v1.capacity()); for (size_t i = 0; i < v1.size(); i++) { *(_start + i) = *(v1._start + i); } _finish = _start + v1.size(); } // 赋值运算符重载 vector& operator=(const vector& v1) { vector<_Tp> tmp(v1); swap(tmp); return *this; } // []重载 _Tp& operator[](size_t i) { return _start[i]; } const _Tp& operator[](size_t i)const { return _start[i]; } // 交换函数swap void swap(vector& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); } // 扩容 reserve void reserve(size_t n) { size_t sz = size(); if (n > capacity()) { _Tp* tmp = new _Tp[n]; if (!empty())//判断是否为空 { for (size_t i = 0; i < sz; i++) { tmp[i] = _start[i]; } } delete[]_start; _start = tmp; _finish = _start + sz; _end_of_storage = _start + n; } } // 扩容+初始化 resize void resize(size_t n, _Tp val = _Tp()) { if (n < size()) { _finish = _start + n; } else if (n > size()) { if (n > capacity()) { reserve(n); } for (size_t i = size(); i < n; i++) { *(_start + i) = val; } _finish = _start + n; } } // 尾插 push_back单个数据 void push_back(const _Tp& t) { if (_end_of_storage == _finish) { size_t new_capacity = (capacity() == 0 ? 4 : capacity() * 2); reserve(new_capacity); } *_finish = t; _finish++; } // 插入 insert单个数据 iterator insert(iterator pos, const _Tp& val) { assert(pos >= _start && pos <= _finish); size_t sz = _finish - pos; if (_finish == _end_of_storage) { size_t new_capacity = (capacity() == 0 ? 4 : capacity() * 2); reserve(new_capacity); pos = _finish - sz; } for (iterator it = _finish; it >= pos; it--) { *it = *(it - 1); } _finish++; *pos = val; return pos + 1; } //插入insert多个数据 iterator insert(iterator pos, size_t n, const _Tp& val) { assert(pos >= _start && pos <= _finish); size_t sz = _finish - pos; if (_end_of_storage <= pos + n) { size_t new_capacity = n + _end_of_storage - pos; reserve(new_capacity); pos = _finish - sz; } iterator it = pos; for (iterator i = pos; i < n + pos; i++) { it = insert(it, val); } return pos + n; } // 尾删 pop_back单个数据 void pop_back(size_t n) { if (!empty()) { if (n > size()) { n = size(); } _finish -= n; } } // 删除 erase(单个数据) iterator erase(iterator pos) { assert(pos >= _start && pos < _finish); iterator it = pos; while (it != _finish) { it++; *(it - 1) = *it; } //防止为空时，_finish跑到_start前面了 if (!empty()) _finish--; return pos - 1; } //删除一个迭代器区间数据 iterator erase(iterator start, iterator finish) { assert(start >= _start && _finish >= finish); size_t sz = finish - start; size_t it = sz; while (it) { start = erase(start); it--; } return finish - sz; } //清理 void clear() { _finish = _start; } // 判空 empty bool empty() { return _start == _finish; } private: iterator _start; iterator _finish; iterator _end_of_storage; }; } void Test1()//构造函数 { lz::vector v1(4, 5); lz::vector v2; lz::vector v3(v1); lz::vector v4 = v3; lz::vector v5(v4.begin(), v4.end()); //lz::vector (); for (auto e : v5) { cout << e << " "; } cout << endl; } void Test2()//erase { lz::vector v(3, 5); auto it1 = std::find(v.begin(), v.end(), 5); while (it1 != v.end()) { it1 = v.erase(it1); it1++; } auto it2 = v.begin(); while (it2 != v.end()) { cout << *it2 << " "; it2++; } cout << endl; } void Test3()//push_back+insert { lz::vector v1; lz::vector v2(3, 1); v1.push_back(4); v1.push_back(5); v1.push_back(6); v1.push_back(7); //打印容量 cout << "capacity = " << v1.capacity() << endl; auto it = v1.begin(); while (it != v1.end()) { cout << *it << " "; it++; } cout << endl; auto tmp1 = std::find(v1.begin(), v1.end(), 4); tmp1 = v1.insert(tmp1, 1); //打印容量 cout << "capacity = "<< v1.capacity() << endl; v1.insert(tmp1, 2); it = v1.begin(); while (it != v1.end()) { cout << *it << " "; it++; } cout << endl; } void Test4()//reserve+resize { lz::vector v1(3, 5); v1.reserve(3); cout << "capacity = " << v1.capacity() << endl; v1.reserve(8); cout << "capacity = " << v1.capacity() << endl; v1.resize(4);//默认初始值 cout << "capacity = " << v1.capacity() << endl;//容量不变 auto it = v1.begin(); while (it != v1.end()) { cout << *it << " "; it++; } cout << endl; v1.resize(20, 9); cout << "capacity = " << v1.capacity() << endl; it = v1.begin();//对it进行重新赋值 while (it != v1.end()) { cout << *it << " "; it++; } cout << endl; } void Test5()//clear+empty { lz::vector v; //判空 cout << v.empty() << endl; //插入数据 v.push_back(4); v.push_back(4); v.push_back(4); v.push_back(4); for (auto e : v) { cout << e << " "; } cout << endl; v.clear(); //容量不变 cout << "capacity = " << v.capacity() << endl; //清除数据后，不打印 for (auto e : v) { cout << e << " "; } cout << endl; } int main() { Test5(); return 0; }
今天的内容到这里就结束了，希望各位小伙伴能够从中有所收获，我们下期再见！
