-
STL容器——vector
前言： vector是STL的容器之一，学习vector我们不仅要会用，还得了解一下它的基本原理，甚至可以模拟实现vector。
1.vector的使用
1.1 构造函数
（1）不需要参数//vectorarr; vector<int> arr;- 1
- 2
- 3
（2）构造n个val//vectorarr1(n,val); //比如构造100个5 vector<int> arr1(100,5);- 1
- 2
- 3
- 4
（3）利用迭代器构造//vectorarr2(迭代器1，迭代器2) //拷贝arr1的所有内容 vector<int> arr2(arr1.begin(),arr1.end()); //也可以反着拷贝arr1的内容，利用反向迭代器 vector<int> arr2(arr1.rbegin(),arr1.rend());- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
（4）拷贝构造//vector(const vector& x) //拷贝arr1的内容 vector<int> arr3(arr1);- 1
- 2
- 3
- 4
1.2 迭代器的使用
只讲前四个，用的比较多。vector中的迭代器也可以看作指针，begin()返回的是头部的指针，end()返回的是尾部的下一个的指针,所以不能够对end()解引用，它不在末尾，而是末尾的下一个。rbeing()和rend()则反之。
使用迭代器前必须要声明：vector<T> ::iterator it;- 1
例如：用迭代器来遍历vector，当然也可以反向遍历，而且还支持修改数据
//构造 vector<int> arr(6, 6); //迭起器使用 vector<int> ::iterator it = arr.begin(); vector<int> ::reverse_iterator is = arr.rbegin(); //正向遍历 while (it != arr.end()) { cout << *it << " "; it++; } cout << endl; //反向遍历，并且使得每个数都+1 while (is != arr.rend()) { *is+=1; cout << *is << " "; is++; } 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
运行结果：
1.3 修改空间大小
主要掌握resize()和reserve();size()返回的是有效空间的大小，capacity()返回的是总空间的大小；max_size(),返回能创建的最大的空间；empty()判断是否为空；
(1) reserve(),修改总空间的大小，如果传的参数小于原有总空间大小，那么不做任何操作；简单说就只能变大，不能变小；
用以下例子来验证：vector<int> arr; arr.reserve(10); arr.reserve(1);- 1
- 2
- 3
通过调试，可以看到，capacity最终是10，验证了reserve()只能扩容。
(2)resize修改的是有效空间的大小(size)，如果是扩容:保留原有数据，可以初始化增加的有效数据。
验证一下：//初始化arr1 vector<int> arr1(10, 5); //resize() int a = 2; arr1.resize(12,a); arr1.resize(1);- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
初始化后的arr1：
有效空间变成12，并且初始化增加的数据为2：
将有效空间减为1：
1.4 增删查改
以下的例子，全用arr这一个对象：vector<int> arr;- 1
(1)增加
push_back()，尾插一个数据arr.push_back(1); arr.push_back(2); arr.push_back(3); arr.push_back(4);- 1
- 2
- 3
- 4
insert(),在某个位置插入一个数据/或者多个。
vector<int> myvector(3, 100); vector<int>::iterator it; it = myvector.begin(); it = myvector.insert(it, 200); myvector.insert(it, 2, 300); // "it" no longer valid, get a new one: it = myvector.begin(); vector<int> anothervector(2, 400); myvector.insert(it + 2, anothervector.begin(), anothervector.end()); int myarray[] = { 501,502,503 }; myvector.insert(myvector.begin(), myarray, myarray + 3); cout << "myvector contains:"; for (it = myvector.begin(); it < myvector.end(); it++) cout << ' ' << *it; cout << '\n';- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
测试的时候，自己写的时候，可能会有迭代器失效问题，这个后面我会好好的讲一件。
（2）删除
erase()，删除某个位置的数据；或者莫一段数据，用的是迭代器。
vector<int> myvector; // 输入数据1~10 for (int i=1; i<=10; i++) myvector.push_back(i); // erase 第六个位置的数 myvector.erase (myvector.begin()+5); // erase 前三个数据 myvector.erase (myvector.begin(),myvector.begin()+3);- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
clear()，会清空数据，但是总空间不变。
（3）查找
find在vector里，并没有实现。用的是STL中算法的find。
template <class InputIterator, class T> InputIterator find (InputIterator first, InputIterator last, const T& val)- 1
- 2
在一段迭代器区间中，查找一个val，找到返回它的位置(迭代器表示)，如果找不到会返回 last(这一段迭代器的末尾)。
（4）改数据
- 可以对迭代器解引用来改
- []，支持随机访问，这也可以改
1.5 测试用的代码
大家可以使用以下的代码，去自行调试，和上面的内容是完全对应的。
#include#include using namespace std; int main() { //构造函数测试 /*vector arr; vector //迭代器使用 /*vectorarr1(100, 5); vector arr2(arr1.begin(), arr1.end()); vector arr3(arr1);*/ arr(6, 6); vector //修改空间大小 /*vector::iterator it = arr.begin(); vector ::reverse_iterator is = arr.rbegin(); while (it != arr.end()) { cout << *it << " "; it++; } cout << endl; while (is != arr.rend()) { *is += 1; cout << *is << " "; is++; } cout << endl;*/ arr; arr.reserve(10); arr.reserve(1); vector //增删查改 //增加 //vectorarr1(10, 5); int a = 2; arr1.resize(12,a); arr1.resize(1);*/ myvector(3, 100); //vector::iterator it; //it = myvector.begin(); //it = myvector.insert(it, 200); //myvector.insert(it, 2, 300); "it" no longer valid, get a new one: //it = myvector.begin(); //vectoranothervector(2, 400); //myvector.insert(it + 2, anothervector.begin(), anothervector.end()); //int myarray[] = { 501,502,503 }; //myvector.insert(myvector.begin(), myarray, myarray + 3); //cout << "myvector contains:"; //for (it = myvector.begin(); it < myvector.end(); it++) // cout << ' ' << *it; // cout << '\n'; //删除 //vectormyvector; 输入数据1~10 //for (int i = 1; i <= 10; i++) myvector.push_back(i); erase 第六个位置的数 //myvector.erase(myvector.begin() + 5); erase 前三个数据 //myvector.erase(myvector.begin(), myvector.begin() + 3); 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
- 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
2. vector的模拟实现
vector的框架是用三个迭代器维护的，非常银杏。
start指向开头，finish指向有效空间末尾，end_of_storage指向总空间的末尾。
private: iterator _start; // 指向数据块的开始 iterator _finish; // 指向有效数据的尾 iterator _endOfStorage; // 指向存储容量的尾- 1
- 2
- 3
- 4
- 5
- 6
- 7
2.1 实现一个简单的vector(面试写)
namespace ly { template<class T> class vector { //构造函数 vector() :_start(nullptr), _finish(nullptr), _endOfStorage(nullptr) {} //得到size和capacity size_t size() const { return _finish - _start; } size_t capacity() const { return _endOfStorage - _start; } //调整空间大小 void reserve(size_t n) { size_t size = _finish - _start; if (n > capacity()) { iterator tmp = new T[n]; memcpy(tmp, _start, size * sizeof(T)); _start = tmp; _finish = _start + size; _endOfStorage = _start + n; } } //插入数据 void push_back(const T& x) { //扩容 if (size() == capacity()) { reserve(capacity() == 0 ? 4 : 2 * size()); } *_finish = x; _finish++; } //删除数据 void pop_back() { _finish--; } 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
以上的vector，就可以简易的插入数据，删除数据了，但只支持尾插尾删。
2.2 模拟实现vector
#include#include namespace ly { template<class T> class vector { public: // Vector的迭代器是一个原生指针 typedef T* iterator; typedef const T* const_iterator; iterator begin() { return _start; } iterator end() { return _finish; } const_iterator cbegin() const { return _start; } const_iterator cend() const { return _finish; } // construct and destroy vector() :_start(nullptr), _finish(nullptr), _endOfStorage(nullptr) {} vector(int n, const T& value = T()) { reserve(n); while (n--) { push_back(value); } } template<class InputIterator> vector(InputIterator first, InputIterator last) :_start(nullptr), _finish(nullptr), _endOfStorage(nullptr) { reserve(last - first); while (first != last) { push_back(*first); first++; } } vector(const vector<T>& v) :_start(nullptr), _finish(nullptr), _endOfStorage(nullptr) { vector<int> tmp(v.cbegin(), v.cend()); swap(tmp); } vector<T>& operator= (vector<T> v) { swap(v); return *this; } ~vector() { if (_start) { delete[] _start; _start = _finish = _endOfStorage = nullptr; } } // capacity size_t size() const { return _finish - _start; } size_t capacity() const { return _endOfStorage - _start; } void reserve(size_t n) { size_t size = _finish - _start; if (n > capacity()) { iterator tmp = new T[n]; memcpy(tmp, _start, size * sizeof(T)); _start = tmp; _finish = _start + size; _endOfStorage = _start + n; } } void resize(size_t n, const T& value = T()) { if (n > capacity()) { reserve(n); while (_finish != _start + n) { *_finish = value; _finish++; } } else if (n > size()) { while (_finish != _start + n) { *_finish = value; _finish++; } } else { _finish = _start + n; } } ///access/// T& operator[](size_t pos) { return _start[pos]; } const T& operator[](size_t pos)const { return *(_start + pos); } ///modify/ void push_back(const T& x) { if (size() == capacity()) { reserve(capacity() == 0 ? 4 : 2 * size()); } *_finish = x; _finish++; } void pop_back() { _finish--; } void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_endOfStorage, v._endOfStorage); } iterator insert(iterator pos, const T& x) { assert(pos >= _start); assert(pos <= _finish); if (_finish == _endOfStorage) { // 扩容会导致pos失效，扩容需要更新一下pos 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++; return pos; } iterator erase(iterator pos) { assert(pos >= _start); assert(pos <_finish); iterator end = pos; while (end<_finish) { *(end) = *(end + 1); end++; } _finish--; return pos; } // void Print() { T* it = begin(); while (it != end()) { std::cout << *it << " "; it++; } 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
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
3. 迭代器失效
迭代器为什么会失效？迭代器在底层封装的是指针，指针指向的空间被释放，指针就失效了，此时的指针为野指针。迭代器也同理，比如：在pos位置插入一个数据，但如果需要扩容，扩容会新开辟一个新空间，那么pos就失效了。
因为，旧的空间被释放
所以但凡涉及到底层空间改变的操作，都有可能会遇到迭代器失效的问题。
比如：：resize、reserve、insert、assign、push_back等。iterator insert(iterator pos, const T& x) { assert(pos >= _start); assert(pos <= _finish); if (_finish == _endOfStorage) { // 扩容会导致pos失效，扩容需要更新一下pos 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++; return pos; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
这是上文，insert的模拟实现，可以看到，我是更新了pos的位置的。
再讲一种迭代器失效的问题，erase()会碰到
iterator erase(iterator pos) { assert(pos >= _start); assert(pos <_finish); iterator end = pos; while (end<_finish) { *(end) = *(end + 1); end++; } _finish--; return pos; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
假如：需要删除数组中的偶数。
vector<int>arr1; arr1.push_back(1); arr1.push_back(2); arr1.push_back(3); arr1.push_back(4); arr1.push_back(5); vector<int>::iterator it = arr1.begin(); while (it != arr1.end()) { if (*it % 2 == 0) { arr1.erase(it); } it++; } arr1.Print();- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
数组的内容是{1，2，3，4，5}，删除偶数后应该是{1，3，5}。上面的代码可以大家一眼看上去，非常正确。我们来运行看看结果，结果显示也正确。
那么修改一下数组的内容为{1，2，4，5}.vector<int>arr1; arr1.push_back(1); arr1.push_back(2); arr1.push_back(4); arr1.push_back(5); vector<int>::iterator it = arr1.begin(); while (it != arr1.end()) { if (*it % 2 == 0) { arr1.erase(it); } it++; } arr1.Print();- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
运行结果：
怎么是1，4，5。4为啥没有被删除呢?这就设计到了迭代器失效问题。
画图：
（1）1是奇数，所以it++。
（2）2是偶数，所以删除掉，删除用的是，从后往前覆盖。
（3）it++,此时并没有判断覆盖过来的数据：4。
综上：因为erase()后，迭代器位置失效，不更新导致，数据4没有被判断。
那么是erase的问题吗？不是，是我们人为使用时，没考虑到迭代器失效导致的。我们只需要更新一下迭代的位置即可。vector<int>::iterator it = arr1.begin(); while (it != arr1.end()) { if (*it % 2 == 0) { //更新迭代器位置 it=arr1.erase(it); } else { it++; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
it 新接收的位置，刚好是pos位置，这个pos位置被后面的数据覆盖，这时候我们不应该继续 it++,而是去检验这个刚被覆盖的pos位置。
4.模拟实现谨慎使用memcpy
上文中reserve()的实现用的是memcpy()，大家都知道memcpy()是浅拷贝，这就会导致：vector < T>,T为自定义类型：string等，它们拷贝不可以是浅拷贝。继续用memcpy(),会出错的，同一个空间释放两次的问题。
结论：- 对于内置类型，比如int，char，float等浅拷贝对象，memcpy()是够用的
- 对于自定义类型，比如string，list等深拷贝对象，需要自己写深拷贝，来完成copy
memcpy版：
void reserve(size_t n) { size_t size = _finish - _start; if (n > capacity()) { iterator tmp = new T[n]; memcpy(tmp, _start, size * sizeof(T)); _start = tmp; _finish = _start + size; _endOfStorage = _start + n; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
深拷贝版：
void reserve(size_t n) { size_t size = _finish - _start; if (n > capacity()) { iterator tmp = new T[n]; for (size_t i = 0; i < this->size(); i++) { //会调用自定义类型的拷贝构造 tmp[i] = _start[i]; } //记得delete旧空间 delete[] _start; _start = tmp; _finish = _start + size; _endOfStorage = _start + n; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
结尾语： vector模拟实现，到此结束。
-
相关阅读:
20天深度复习JavaSE的详细笔记(二十)——XML、解析、设计模式等
51建模网3D编辑器：一键为3D模型设置特殊材质
使用Flink处理Kafka中的数据_题库子任务_Java语言实现
Journal of statistical software:追踪前沿的统计学软件
使用单调栈解决 “下一个更大元素” 问题
《科学之路》读书笔记
【树状数组该回炉重造了】Codeforces Round #813 (Div. 2) E2. LCM Sum (hard version)
维控PLC——LX1S ：编程口通讯协议
【C语言】结构体、共用体兄弟俩
ansible
- 原文地址：https://blog.csdn.net/lyzzs222/article/details/126588210
