-
【初阶与进阶C++详解】第九篇：vector
🏆个人主页：企鹅不叫的博客
🌈专栏
⭐️ 博主码云gitee链接：代码仓库地址
⚡若有帮助可以【关注+点赞+收藏】，大家一起进步！
💙系列文章💙
【初阶与进阶C++详解】第二篇：C&&C++互相调用（创建静态库）并保护加密源文件
【初阶与进阶C++详解】第三篇：类和对象上（类和this指针）
【初阶与进阶C++详解】第四篇：类和对象中（类的六个默认成员函数）
【初阶与进阶C++详解】第五篇：类和对象下（构造+static+友元+内部类
【初阶与进阶C++详解】第六篇：C&C++内存管理（动态内存分布+内存管理+new&delete）
【初阶与进阶C++详解】第七篇：模板初阶（泛型编程+函数模板+类模板+模板特化+模板分离编译）
【初阶与进阶C++详解】第八篇：string类（标准库string类+string类模拟实现）
💎一、vector使用
🏆1.vector定义
vector()（重点） 无参构造 vector（size_type n, const value_type& val = value_type()） 构造并初始化n个val vector (const vector& x); （重点） 拷贝构造 vector (InputIterator first, InputIterator last); 使用迭代器进行初始化构造 int main () { vector<int> first; //构造一个int类型容器 vector<int> second(4, 100); // 初始化4个100 vector<int> third(second.begin(), second.end()); // 区间初始化，将second从begin开始初始化到end vector<int> fourth(third);//拷贝构造 //迭代器使用注意 //注意迭代器解引用之后对用的string还是char vector<string>v1; v1.push_back("你好！"); string s = "hello!"; vector<char>v6(s.begin(), s.end()); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
🏆2.vector iterator 的使用
函数名称 功能说明 operator[] （重点） 返回pos位置的字符，const string类对象调用 begin+ end begin获取一个字符的迭代器 + end获取最后一个字符下一个位置的迭代器 rbegin + rend rbegin获取最后一个字符的迭代器 + rend获取第一个字符位置的迭代器 范围for C++11支持更简洁的范围for的新遍历方式 int main () { //1.下标+[] for (size_t i = 0; i < v.size(); ++i) { v[i] += 1; } //2.迭代器 vector<int>::iterator it = v.begin(); while (it != v.end()) { *it -= 1; cout << *it << " "; ++it; } //3.范围for for (auto e : v) { cout << e << " "; } return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
🏆3.迭代器失效问题
迭代器底层是一个指针，迭代器失效本质是迭代器底层对应指针所指向的空间被销毁了，有以下情况
1.扩容，增容，导致原有的空间被释放（但是迭代器指针依旧指向原空间变成野指针），比如：resize、reserve、insert、assign、
push_back等 。void TestVector1() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); vector<int>::iterator it = v.begin(); while (it != v.end()) { if (*it % 2 == 0)//在偶数之前插入内容 { //程序内出现了扩容，it原先指向的空间已经被释放 //v.insert(it, 99);是错误写法 //需要去insert中更新迭代器，具体看insert实现 //下面是正确写法 it = v.insert(it, 99); it++; } it++; } for (auto ch : v) { cout << ch << " "; } cout << endl;- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
2.erase导致数据删除，迭代器指向的位置意义变了
void TestVector1() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); vector<int>::iterator it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) // 迭代器失效，因为删除会导致后面的数据往前挪动，迭代器还指向原来的位置，但是原来的位置上数据变了 //错误写法：v.erase(it); it = v.erase(it);// 正确写法，给迭代器重新赋值 ++it; } for (auto e : v) { cout << e << " "; } cout << endl; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
总结： 使用迭代器前记得对迭代器赋值，可以避免迭代器失效的问题产生。
💎二、vector模拟实现
🏆1.vector无参构造函数/析构函数/用n个val进行构造（注意重载）
template<class T> class vector { public: //定义迭代器，在vector中，迭代器其实就是一个原生指针T* typedef T* iterator; typedef const T* iterator; //无参初始化 vector() :_start(nullptr) , _finish(nullptr) , _endofstoage(nullptr) {} ~vector() { if (_start) { delete[]_start; _start = _finish = _endofstoage = nullptr; } } vector(size_t n, const T& val = T()) :_start(nullptr) , _finish(nullptr) , _endofstoage(nullptr) { //1.写法一 //resize(n, val); //2.写法二 reserve(n); for (size_t i = 0; i < n; ++i) { push_back(val); } } vector(int n, const T& val = T()) :_start(nullptr) , _finish(nullptr) , _endofstoage(nullptr) { resize(n, val); } private: iterator _start;//指向开头 iterator _finish;//指向结尾数据的下一个位置 iterator _endofstoage;//指向空间尾部 };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
如果我们只实现==vector(size_t n, const T& val = T())==这个版本不可以，如果出现以下情况
vector<char> v1(10,'x')//(int, char)可以成功调用 vector<int> v2(10,11) //(int, int)不能成功调用- 1
- 2
第一个会去匹配vector(size_t n, const T& val = T())，因为类型符合
第二个回去匹配vector(InputIterator frist, InputIterator last)，因为他们类型最相似，一个是(int, int)，另一个是模板参数，然而匹配之后，由于传过去是int类型解引用就会报错，解决办法是，函数重载一个
🏆2.vector空间增长
size 获取数据个数 capacity 获取容量大小 empty 判断是否为空 resize（重点） 改变vector的size reserve （重点） 改变vector放入capacity -
capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的，单次增容多，浪费就会多
-
resize开空间会初始化
-
reserve只负责开辟空间,会修改原有空间
template<class T> class vector { public: //定义迭代器，在vector中，迭代器其实就是一个原生指针T* typedef T* iterator; typedef const T* iterator; size_t size() const { return _finish - _start; } size_t capacity() const { return _endofstoage - _finish; } iterator begin() { return _start; } iterator end() { return _finish; } iterator begin() const { return _start; } iterator end() const { return _finish; } void reserve(size_t n) { //提前更新sz防止后面_start被更新,计算出原有的长度 size_t sz = size(); if (n > capacity()) { T* tmp = new T[n]; if(_start)//只有_start不为空才能进行拷贝操作 { //memcpy(tmp, _start, size()*sizeof(T)); //使用memcpy会存在浅拷贝问题 //当遇到自定义类型比如string类，vector，所以我们要一个一个拷贝数据 for (size_t i = 0; i < size(); ++i) { tmp[i] = _start[i];//手动赋值，当成员是自定义类型的时候，会调用重载 } delete[] _start; } _start = tmp; } _finish = _start + sz; _endofstoage = _start + n; } //T()的含义是用模板参数的构造函数作为缺省值 void resize(size_t n, T val = T()) { if (n > capacity()) { reserve(n); } if (n > size()) { while (_finish < _start + n) { *_finish = val; ++_finish; } } else { _finish = _start + n; } } private: //指针 iterator _start;//指向开头 iterator _finish;//指向结尾数据的下一个位置 iterator _endofstoage;//指向空间尾部 };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
🏆3.vector增删查改
push_back（重点） 尾插 pop_back （重点） 尾删 find 查找。（注意这个是算法模块实现，包含< algorithm >头文件） insert 在position之前插入val erase 删除position位置的数据 swap 交换两个vector的数据空间 operator[] （重点） 像数组一样访问 template<class T> class vector { public: //定义迭代器，在vector中，迭代器其实就是一个原生指针T* typedef T* iterator; typedef const T* iterator; iterator insert(size_t pos, const T& x) { //检查合法性 assert(pos >= _start && pos <= _finish); //扩容 //扩容之后pos失效(野指针)了，需要更新pos if (_finish == _endofstoage) { size_t n = pos - _start; size_t newcapacity = capacit y() == 0 ? 4 : capacity() * 2; reserve(newcapacity); pos = _start + n; } //挪动数据 iterator end = _finish-1; while (end >= pos) { *(end + 1) = *end; --end; } *pos = x; ++_finish; return pos; } iterator erase(size_t pos) { assert(pos >= _start && pos <= _finish); iterator it = pos + 1; while (it != _finish) { *(it - 1) = *it; ++it; } --_finish; return pos; } //使用引用传参防止深拷贝 void push_back(const T& x) { //如果满了 if (_finish == _endofstoage) { size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); } *_finish = x; _finish++; } void pop_back() { if (_finish > _start) { _finish--; } } T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos) const { assert(pos < size()); return _start[pos]; } void clear() { _finish = _start; } bool empty() { return size() == 0; } private: //指针 iterator _start;//指向开头 iterator _finish;//指向结尾数据的下一个位置 iterator _endofstoage;//指向空间尾部 };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
🏆4.vector的迭代器区间构造/拷贝构造/赋值
template<class T> class vector { public: //定义迭代器，在vector中，迭代器其实就是一个原生指针T* typedef T* iterator; typedef const T* iterator; //迭代区间构造，利用指针解引用尾插内容，（如果没有空间会reserve扩容） template <class InputIterator> vector(InputIterator frist, InputIterator last) :_start(nullptr) , _finish(nullptr) , _endofstoage(nullptr) { while (frist != last) { push_back(*frist); ++frist; } } //使用库函数swap交换thsi和tmp成员变量，构造完成之后，tmp生命周期结束 void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstoage, v._endofstoage); } //拷贝构造 //利用迭代器构造一个tmp对象，再与this交换 vector(const vector<T>& v) :_start(nullptr) , _finish(nullptr) , _endofstoage(nullptr) { vector<T>tmp(v.begin(), v.end()); swap(tmp); } //直接传值，将传过来的值与this交换 vector<T>& operator=(vector<T> v) { swap(v); return *this; } private: iterator _start;//指向开头 iterator _finish;//指向结尾数据的下一个位置 iterator _endofstoage;//指向空间尾部 };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
🏆5.自定义类型的拷贝问题
为什么在的reserve实现中，使用赋值重载，而没有使用memcpy？
class Solution { public: vector<vector<int>> generate(int numRows) { //定义一个二维数组vv vector<vector<int>> vv; //初始化行数 vv.resize(numRows); for(size_t i = 0; i < vv.size(); ++i) { //每一行递增 vv[i].resize(i+1, 0); //每一行的第一个和最后一个初始化为1 vv[i][0] = 1; vv[i][vv[i].size()-1] = 1; } //相加 for(size_t i = 0; i < vv.size(); ++i) { for(size_t j = 0; j < vv[i].size(); ++j) { if(vv[i][j] == 0) { vv[i][j] = vv[i-1][j-1]+vv[i-1][j]; } } } return vv; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
-
目前两层vector进行嵌套]使用，外层的vector存放的是内层vector的对象。
-
如果拷贝的是自定义类型的元素，memcpy即高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝
-
如果只用
memcpy进行浅拷贝，相当于新的空间里面存放的是的确是新的vector对象，但这些vector对象存放的却是原有数据的指针，而原本的数据已经被我们delete掉了，出现了野指针问题。
-
相关阅读:
快捷键记录
java 时间类型和 mysql 时间类型对应关系
spring @value @configurationProperties比较
win11更新后任务栏空白怎么办？ win11更新后任务栏空白卡死的解决方法
Zongmu AVM车载环视 Android SDK 简介
荣23转债上市价格预测
『吴秋霖赠书活动 ｜ 第二期』《ChatGPT原理与实战》
基于PHP+MySQL珠宝销售网站的设计与开发
线程池源码解析 1.前导_FutureTask源码解析
SpringMVC框架学习
- 原文地址：https://blog.csdn.net/YQ20210216/article/details/126829243
