-
C++------vector【STL】
vector的介绍及使用
vector的介绍
1、vector是表示可变大小数组的序列容器。
2、就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
3、本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
4、vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
5、因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
6、与其他动态序列容器相比，vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其他不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好。vector的使用
需要重点掌握的接口
vector的构造函数
// vector的构造 int TestVector1() { // constructors used in the same order as described above: vector<int> first; //空 vector<int> second(4, 100); //4个100初始化 vector<int> third(second.begin(), second.end()); //迭代器区间 vector<int> fourth(third); //拷贝构造 // 下面涉及迭代器初始化的部分，我们学习完迭代器再来看这部分 int myints[] = { 16,2,77,29 }; vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int)); cout << "The contents of fifth are:"; for (vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it) cout << ' ' << *it; cout << '\n'; 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
迭代器的使用，这里是左闭右开的区间
void PrintVector(const vector<int>& v) { // const对象使用const迭代器进行遍历打印 vector<int>::const_iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; } void TestVector2() { // 使用push_back插入4个数据 vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); // 使用迭代器进行遍历打印 vector<int>::iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; // 使用迭代器进行修改 it = v.begin(); while (it != v.end()) { *it *= 2; ++it; } // 使用反向迭代器进行遍历再打印 // vector::reverse_iterator rit = v.rbegin(); auto rit = v.rbegin(); while (rit != v.rend()) { cout << *rit << " "; ++rit; } cout << endl; PrintVector(v); }- 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
vector的扩容
- capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
- reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
- resize在开空间的同时还会进行初始化，影响size。
// reisze(size_t n, const T& data = T()) // 将有效元素个数设置为n个，如果时增多时，增多的元素使用data进行填充 // 注意：resize在增多元素个数时可能会扩容 void TestVector3() { vector<int> v; // set some initial content: for (int i = 1; i < 10; i++) v.push_back(i); v.resize(5); v.resize(8, 100); v.resize(12); cout << "v contains:"; for (size_t i = 0; i < v.size(); i++) cout << ' ' << v[i]; cout << '\n'; } // 测试vector的默认扩容机制 // vs：按照1.5倍方式扩容 // linux：按照2倍方式扩容 void TestVectorExpand() { size_t sz; vector<int> v; sz = v.capacity(); cout << "making v grow:\n"; for (int i = 0; i < 100; ++i) { v.push_back(i); if (sz != v.capacity()) { sz = v.capacity(); cout << "capacity changed: " << sz << '\n'; } } } // 往vecotr中插入元素时，如果大概已经知道要存放多少个元素 // 可以通过reserve方法提前将容量设置好，避免边插入边扩容效率低 void TestVectorExpandOP() { vector<int> v; size_t sz = v.capacity(); v.reserve(100); // 提前将容量设置好，可以避免一遍插入一遍扩容 cout << "making bar grow:\n"; for (int i = 0; i < 100; ++i) { v.push_back(i); if (sz != v.capacity()) { sz = v.capacity(); cout << "capacity changed: " << sz << '\n'; } } }- 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
vector的增删查改
// 尾插和尾删：push_back/pop_back void TestVector4() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); auto it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; v.pop_back(); v.pop_back(); it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; } // 任意位置插入：insert和erase，以及查找find // 注意find不是vector自身提供的方法，是STL提供的算法 void TestVector5() { // 使用列表方式初始化，C++11新语法 vector<int> v{ 1, 2, 3, 4 }; // 在指定位置前插入值为val的元素，比如：3之前插入30,如果没有则不插入 // 1. 先使用find查找3所在位置 // 注意：vector没有提供find方法，如果要查找只能使用STL提供的全局find auto pos = find(v.begin(), v.end(), 3); if (pos != v.end()) { // 2. 在pos位置之前插入30 v.insert(pos, 30); } vector<int>::iterator it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; pos = find(v.begin(), v.end(), 3); // 删除pos位置的数据 v.erase(pos); it = v.begin(); while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; } // operator[]+index 和 C++11中vector的新式for+auto的遍历 // vector使用这两种遍历方式是比较便捷的。 void TestVector6() { vector<int> v{ 1, 2, 3, 4 }; // 通过[]读写第0个位置。 v[0] = 10; cout << v[0] << endl; // 1. 使用for+[]小标方式遍历 for (size_t i = 0; i < v.size(); ++i) cout << v[i] << " "; cout << endl; vector<int> swapv; swapv.swap(v); cout << "v data:"; for (size_t i = 0; i < v.size(); ++i) cout << v[i] << " "; cout << endl; // 2. 使用迭代器遍历 cout << "swapv data:"; auto it = swapv.begin(); while (it != swapv.end()) { cout << *it << " "; ++it; } // 3. 使用范围for遍历 for (auto x : v) cout << x << " "; 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
- 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
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
vector迭代器失效问题
迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。
迭代器失效的情况：扩容后迭代器失效，删除时迭代器失效。
解决方法：
迭代器失效解决办法：在使用前，对迭代器重新赋值即可。vector的模拟实现
#pragma once #include#include namespace vec { template<class T> class vector { typedef T* iterator; typedef const T* const_iterator; public: vector() {} //内置类型也可以有构造函数，我们下一次再说 vector(size_t n, const T& it = T()) { resize(n, it); } vector(int n, const T& val = T()) { resize(n, val); } template<class InputIterator> vector(InputIterator first, InputIterator last) { while (first != last) { push_back(*first); first++; } } size_t capacity() const { return _endofstorage - _start; } size_t size() const { return _finish - _start; } iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } void reserve(size_t n) { if (n > capacity()) { size_t sz = size(); T* tmp = new T[n]; //拷贝原有的数据 if (_start) { for (size_t i = 0; i < sz; i++) { tmp[i] = _start[i]; } delete[] _start; } _start = tmp; _finish = _start + sz; _endofstorage = _start + n; } } void push_back(const T& x) { //考虑增容的情况 if (_finish == _endofstorage) { size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); } //*_finish = x; //_finish++; insert(end(), x); } iterator erase(iterator pos) { //考虑pos位置的合法性 assert(pos >= _start && pos < _finish); //移动数据 iterator p = pos + 1; while (p != _finish) { *(p - 1) = *p; p++; } _finish--; return pos; } void resize(size_t n, const T& x = T()) { if (n < size()) { _finish = _start + n; } else { reserve(n); while (_finish != _start + n) { *_finish = x; _finish++; } } } iterator insert(iterator pos, const T& x) { //判断pos位置的合法性 assert(pos >= _start && pos <= _finish); //考虑扩容 if (_finish == _endofstorage) { //解决迭代器失效问题 size_t len = _finish - _start; size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); pos = _start + len; } //开始插入数据 //移动数据 iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; end--; } //插入数据 *pos = x; _finish++; return pos; } void pop_back() { erase(--end()); } T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos) const { assert(pos < size()); return _start[pos]; } //拷贝构造 vector(const vector<T>& v) { //深度拷贝 _start = new T[v.capacity()]; for (size_t i = 0; i <v.size(); i++) { _start[i] = v._start[i]; } _finish = _start + v.size(); _endofstorage = _start + v.capacity(); } void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endofstorage, v._endofstorage); } //赋值运算符重载 vector<T>& operator=(vector<T> v) { swap(v); return *this; } ~vector() { if (_start) { delete[] _start; _start = _finish = _endofstorage = nullptr; } } void print(const vector<T>& v) { for (auto e : v) { std::cout << e << " "; } std::cout << std::endl; } private: iterator _start; iterator _finish; iterator _endofstorage; }; } - 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
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
好的，我们下一篇再见！
-
相关阅读:
2023年第十六届山东省职业院校技能大赛中职组“网络安全”赛项规程
elasticsearch报错“reason“: “Invalid index name [mieShop], must be lowercase
路由器安全性怎么提高
Linux逻辑方式合并物理磁盘
JDK8新特性：Stream流
负担过重何以轻装前行
基于三维Voronoi图划分的加权混合回归定位算法
好看又炫酷的网页特效例子收集
Windows 10 资源管理器使用深色主题
Android 高版本采集系统、进程CPU使用率的方式
- 原文地址：https://blog.csdn.net/m0_67635008/article/details/132652282
