-
STL——vector与迭代器
前言：
vector与数组
vector在底层是一种类似数组的C++类模板，因此vector容器一但实例化其大小是不变的，但是容器中指向堆上的元素对象是动态变化的，支持“增删查改"，同数组一样对于插入，insert的效率是很低的
迭代器—“通用指针"
迭代器的本质
- 循环的控制方式有2种：标志控制(while),计数控制(for),而迭代器将这2种循环方式的统一为一种控制方式—迭代器控制—“通用指针"
- 为什么称迭代器为指针，因为其的行为和指针非常相似，另外不同容器的迭代器类型是不同的，因此这里的“通用"是一种概念上的通用
- 几乎所有的的泛型容器和泛型算法都使用迭代器来访问对象
迭代器的分类
迭代器 功能 Input_iterator–输入迭代器 只提高读操作 Output_iterator–输出迭代器 只提高写操作 Forward_iterator–单向迭代器 只能向前访问下一元素，不能向后访问，支持++ Bidirectional_iterator–双向迭代器 双向访问迭代器，支持++与– Random_iterator–随机迭代器 可以随机访问对象中的每一个元素，支持++，-,+,–等运算 从表中可以得出，功能更全的迭代器是支持向功能少的迭代器支持的接口进行传参的
迭代器失效
-
迭代器失效指的是：当容器底层发生变化，原来的迭代器可能由于元素存储位置的变动，成为野指针或者后续的迭代器不在指向准确的数据。
-
常见的引发操作：insert()时的扩容，erase（）的缩容，clear（），remove()等
-
解决方法：及时的更新迭代器并通过返回值得到正确的指向下一个元素的
vector功能复写
成员变量
typedef T* iterator; iterator _start; iterator _finish; iterator _end_of_storage;- 1
- 2
- 3
- 4
构造函数
默认构造函数
vector() :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {}- 1
- 2
- 3
自定义的构造函数
vector支持通过迭代器区间来初始化对象
templatevector(inputIterator first, inputIterator last) :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr) { while (first != last) { push_back(*first); ++first; } } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
拷贝构造函数
vector(const vector& v)//提前初始化成员，防止delete随机值 : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) { vector tmp(v.begin(), v.end()); std::swap(_start, tmp._start); std::swap(_finish, tmp._finish); std::swap(_end_of_storage, tmp._end_of_storage); } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
赋值运算符
//现代写法 vector& operator=(vector v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); } - 1
- 2
- 3
- 4
- 5
- 6
- 7
size()
size_t size()const { return _finish - _start; }- 1
- 2
- 3
- 4
capacity()
size_t capacity()const { return _end_of_storage - _start; }- 1
- 2
- 3
- 4
operator[]
T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos)const { assert(pos < size()); return _start[pos]; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
begin()
typedef T* iterator; iterator begin() { return _start; } typedef T* const_iterator; const_iterator begin()const { return _start; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
end()
typedef T* iterator; iterator end() { return _finish; } typedef T* const_iterator; const_iterator end()const { return _finish; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
reserve()
void reserve(size_t n) { if (n > capacity()) { T* tmp = new T[n]; int sz = size(); if (_start != nullptr) { //使用memcpy会导致浅拷贝野指针问题 //memcpy(tmp, _start, sizeof(T)*sz); //使用深拷贝赋值 // 或者定位new for (size_t i = 0; i < sz; ++i) { //调用深拷贝的赋值函数 tmp[i] = _start[i]; } delete[]_start; } _start = tmp; //注意这里要用旧的size，因为_start改变时， //finish未变，直接使用size()，可能会出现负的情况 _finish = _start + sz; _end_of_storage = _start + 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
resize()
编译器对很多类型包括内置类型都将它们进行了提升，类似一种类，因此int()=0；
void resize(size_t n, const T& value = T()) { if (n < size()) { _finish = _start + n; } else { if (n > capacity()) { reserve(n); } //初始化大于size()的空间 for (size_t i = size(); i < n; ++i) { _start[i] = value; } _finish = _start + n; _end_of_storage = _start + n; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
push_back()
void push_back(const T& value) { if (_finish == _end_of_storage) { reserve(capacity() == 0 ? 4 : 2 * capacity()); } *_finish = value; ++_finish; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
pos_back()
void pop_back() { assert(_finish > _start); --_finish; }- 1
- 2
- 3
- 4
- 5
- 6
insert()
如果inisrt中发生了扩容导致pos指向的空间被释放
又pos本身是一个指针，这就成了对野指针的操作是非法的----迭代器失效iterator insert(iterator pos,const T& value) { assert(pos >= _start); assert(pos <= _finish); //扩容会导致pos失效，需要更新pos if (_finish == _end_of_storage) { size_t len = pos - _start; reserve(capacity() == 0 ? 4 : 2 * capacity()); pos = _start + len; } iterator end = _finish; while (end > pos) { *(end) = *(end - 1); --end; } *pos = value; ++_finish; return pos; }- 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
erase()
//不同版本的erase可能会 异地 缩容，因此要返回一个 iterator erase(iterator pos) { assert(pos >= _start); assert(pos < _finish); iterator begin = pos + 1; while (begin < _finish) { *(begin - 1) = *(begin); ++begin; } --_finish; return pos; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
find(）
templateInputIterator find (InputIterator first, InputIterator last, const T& val) { while (first!=last) { if (*first==val) return first; ++first; } return last; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
全部代码
Vector.h
#pragma once #define _CRT_SECURE_NO_WARNINGS #include#include #include #include #include #include #include #include namespace My_Vet { template class vector { public: typedef T* iterator; iterator begin() { return _start; } iterator end() { return _finish; } typedef T* const_iterator; const_iterator begin()const { return _start; } const_iterator end()const { return _finish; } vector() :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {} //传统写法 /*vector(const vector & v) { T* tmp = new [v.size()*sizeof(T)]; delete[]_start; _start = tmp; _finish = tmp + v.size(); _end_of_storage = tmp + v.capacity(); //传统写法要考虑浅拷贝问题 //memcpy(_start, v._start, sizeof(T)*v.size()); for(size_t i =0;i & v)//提前初始化成员，防止delete随机值 : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) { vector tmp(v.begin(), v.end()); std::swap(_start, tmp._start); std::swap(_finish, tmp._finish); std::swap(_end_of_storage, tmp._end_of_storage); } //现代写法 vector & operator=(vector v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); } size_t size()const { return _finish - _start; } size_t capacity()const { return _end_of_storage - _start; } 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 reserve(size_t n) { if (n > capacity()) { T* tmp = new T[n]; int sz = size(); if (_start != nullptr) { //使用memcpy会导致浅拷贝野指针问题 //memcpy(tmp, _start, sizeof(T)*sz); //使用深拷贝赋值 // 或者定位new for (size_t i = 0; i < sz; ++i) { //调用深拷贝的赋值函数 tmp[i] = _start[i]; } delete[]_start; } _start = tmp; //注意这里要用旧的size，因为_start改变时， //finish未变，直接使用size()，可能会出现负的情况 _finish = _start + sz; _end_of_storage = _start + n; } } //编译器对很多类型包括内置类型都将它们进行了提升，类似一种类，因此int()=0； void resize(size_t n, const T& value = T()) { if (n < size()) { _finish = _start + n; } else { if (n > capacity()) { reserve(n); } //初始化大于size()的空间 for (size_t i = size(); i < n; ++i) { _start[i] = value; } _finish = _start + n; _end_of_storage = _start + n; } } void push_back(const T& value) { if (_finish == _end_of_storage) { reserve(capacity() == 0 ? 4 : 2 * capacity()); } *_finish = value; ++_finish; } void pop_back() { assert(_finish > _start); --_finish; } //如果inisrt中发生了扩容导致pos指向的空间被释放 //又pos本身是一个指针，这就成了对野指针的操作是非法的----迭代器失效 iterator insert(iterator pos,const T& value) { assert(pos >= _start); assert(pos <= _finish); //扩容会导致pos失效，需要更新pos if (_finish == _end_of_storage) { size_t len = pos - _start; reserve(capacity() == 0 ? 4 : 2 * capacity()); pos = _start + len; } iterator end = _finish; while (end > pos) { *(end) = *(end - 1); --end; } *pos = value; ++_finish; return pos; } //不同版本的erase可能会 异地 缩容，因此要返回一个 iterator erase(iterator pos) { assert(pos >= _start); assert(pos < _finish); iterator begin = pos + 1; while (begin < _finish) { *(begin - 1) = *(begin); ++begin; } --_finish; return pos; } ~vector() { delete[]_start; _start = _finish = _end_of_storage = nullptr; //std::cout << "~vector()" << std::endl; } //iterator find() //{ // //} private: iterator _start; iterator _finish; iterator _end_of_storage; }; } - 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
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
-
相关阅读:
【前端笔记】ant-design-vue 3.x使用modal.method()自定义content内容小记
高数---二重积分
卷麻了，00后测试用例写的比我还好，简直无地自容。。。
【C语言】Debian安装并编译内核源码
【前端面试必知】圣杯布局和双飞翼布局
2023/10/5 下午3:38:53 SCROLLINFO scrollInfo；
项目风险管理十大黄金法则！高质量项目管理必杀技！
Springboot中的多环境开发
一文教你处理SpringBoot统一返回格式
乔布斯逝世十周年 苹果官网发布纪念短片
- 原文地址：https://blog.csdn.net/qq_55439426/article/details/125698018
