-
vector类模拟实现（c++）（学习笔记）
基本框架：
namespace xty { template<class T> class vector { public: typedef T* iterator; /// //... /// private: iterator _strat; //起始位置 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
vector的大致形状如下：黄色代表每天满的地方。
构造函数
使用初始化列表实现一个简单的无参构造函数。
//无参构造函数 vector() :_finish(nullptr), _start(nullptr), _end_of_storage(nullptr) {}- 1
- 2
- 3
- 4
- 5
- 6
析构函数
记住要带[]即可。
~vector() { delete[] _start; //用带括号的 _start = nullptr; _finish = nullptr; _end_of_storage = nullptr; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
[]
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
- 11
push_back
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
reserve()
因为push_back涉及到扩容函数，需要实现reserve()。
如下示例：
void reserve(size_t n) { if (n > capacity()) { T* tem = new T[n]; if (_start) { memcpy(tem, _start, sizeof(T)*size()); //拷贝过去 delete[] _start; } _start = tem; _finish = _start + size(); //error _end_of_storage = _start + n; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
问题1：_finish赋值出错，出bug了，是因为size()函数，调用了空指针，导致报错。
改正：
因为delete之后，原数据就被清空了，所以可以提前保存一下size()的大小。void reserve(size_t n) { if (n > capacity()) { T* tem = new T[n]; const size_t sz = size(); //提前保存sz if (_start) { memcpy(tem, _start, sizeof(T)*size()); //拷贝过去 delete[] _start; } _start = tem; _finish = _start + sz; //使用sz赋值 _end_of_storage = _start + n; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
push_back()
逻辑比较简单，在vector的尾部添加一个val，就需要一些前置函数。
//尾插 void push_back(const T& val) { //满了扩容 if (_finish == _end_of_storage) { reserve(capacity() == 0 ? 4 : capacity() * 2); } //插入数据 *_finish = val; _finish++; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
迭代器实现
该逻辑也比较简单，注意实现const的版本。
非const和const版本
typedef T* iterator; typedef const T* const_iterator; iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
pop_back()
尾删。
bool empty() { return _start == _finish; } //尾删 void pop_back() { assert(!empty()); _finish--; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
resize()
和string逻辑差不多。
void resize(size_t n, const T& val = T()) { //一样大，直接返回 if (n == size()) { return; } if (n<size()) //小于直接修改_finish { while (n != size()) { --_finish; } } else { if (n > capacity()) //大于容量先扩容 { reserve(n); } while (n != size()) { push_back(val); } } }- 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
优化：该函数多次调用push_back()使用while，效率低。
void resize(size_t n, const T& val = T()) { if (n == size()) { return; } if (n < size()) { _finish = _start + n; //直接移动_finish } else { if (n > capacity()) { reserve(n); } while (_finish != _start + n) //使用指针操作，减少调用 { *_finish = val; _finish++; } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
insert()***重点
传入迭代器的位置，插入一个元素。
void insert(iterator pos ,const T& val) { //检测pos位置是否合法 assert(pos >= _start); assert(pos <= _finish); // 满了需要扩容 if (_finish == _end_of_storage) { reserve(capacity() == 0 ? 4 : capacity() * 2); } //从后往前移动 iterator end = _finish; while (end > pos) { *end = *(end - 1); end--; } *pos = val; //在该位置赋值 _finish++; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
算法问题1：会造成迭代器失效，迭代器失效，实际就是迭代器底层对应指针所指[空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器程序可能会崩溃)。
该程序正常来说没有问题，当出现扩容的时候，reserve（）会删除原来的空间，去申请新的空间，因此会导致pos指向的那段空间被释放掉，pos变成野指针。改正：记录插入的相对位置，扩容后根据相对位置更新pos的值。
void insert(iterator pos, const T& val) { //检测pos位置是否合法 assert(pos >= _start); assert(pos <= _finish); // 满了需要扩容 if (_finish == _end_of_storage) { size_t len = pos - _start;//扩容前记住相对位置 reserve(capacity() == 0 ? 4 : capacity() * 2); pos = _start + len; //扩容后重新给pos值 } //从后往前移动 iterator end = _finish; while (end > pos) { *end = *(end - 1); end--; } *pos = val; //在该位置赋值 _finish++; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
算法问题2：执行insert后，如果扩容，pos位置已经改变了，而函数外面的pos因为是值传递，并没有修改，同样导致了野指针的问题。（迭代器再一次失效！）
解决办法：- pos传引用可以吗？
不可以。如下图：如果传入v.begin()，会报错。因为begin()是传值返回，传值返回有一个临时变量，而临时变量具有常性，不能被修改，insert里面就不能修改了！
- 通过返回值解决可以吗？
可以，我们可以利用insert返回值的特性，来更新pos防止失效！
如下图：这样就解决问题了。
最终版本：
iterator insert(iterator pos, const T& val) { //检测pos位置是否合法 assert(pos >= _start); assert(pos <= _finish); // 满了需要扩容 if (_finish == _end_of_storage) { size_t len = pos - _start;//扩容前记住相对位置 reserve(capacity() == 0 ? 4 : capacity() * 2); pos = _start + len; //扩容后重新给pos值 } //从后往前移动 iterator end = _finish; while (end > pos) { *end = *(end - 1); end--; } *pos = val; //在该位置赋值 _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
总结：使用insert后，我们默认迭代器失效！因为我们不知道何时执行扩容操作，因此需要重新对pos赋值，防止这类情况发生！
erase()***重点
指定位置执行删除操作。
void erase(iterator pos) { assert(pos >= _start); assert(pos < _finish); auto end = pos + 1; while (end < _finish) { //后给前，从前往后 *(end - 1) = *end; end++; } _finish--; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
问题1：erase会导致迭代器失效？
==会导致！==如果删除最后一个位置，最后一个位置就变成了空位置，导致pos也指向了不该指向的位置。因此，erase()执行过后，应该重新给pos赋值再使用！最终版本：添加返回值。
iterator erase(iterator pos) { assert(pos >= _start); assert(pos < _finish); auto end = pos + 1; while (end < _finish) { //后给前，从前往后 *(end - 1) = *end; end++; } _finish--; return pos; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
最后给大家一个例子自己感受：
该例子在VS2019会报错#includeusing namespace std; #include int main() { vector<int> v{ 1, 2, 3, 4 }; auto it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) v.erase(it); ++it; } return 0; } int main() { vector<int> v{ 1, 2, 3, 4 }; auto it = v.begin(); while (it != v.end()) { if (*it % 2 == 0) it = v.erase(it); else ++it; } 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
再谈构造函数！
这次实现一个可以规定数量和内容的构造函数。
//正常实现 vector(size_t n, const T& val = T()) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { reserve(n); size_t len = n; while (n--) { push_back(val); } } //构造函数由迭代器实现 template<class InputIterator> vector(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
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
当我们满心欢喜的实现好这两个构造函数后，想要测试一下。结果报错了。
输入： vector vx(10,5);
这是为什么呢？因为10，5都被编译器认为是int类型，而编译器在函数重载时，会自动调用最合适的，而它认为第二个函数更适合自己()，因此解引用的时候产生非法间接寻址！因此我们需要再次实现一个int型的函数重载！
vector(int n, const T& val = T()) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { reserve(n); size_t len = n; while (len--) { push_back(val); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
迭代器构造还支持以下方法：
int a[] = { 1, 2, 3 }; vector<int> v4(a, a + 3); for (auto e : v4) { std::cout << e << " "; } std::cout << std::endl; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
拷贝构造函数****（重点）
如果我们不自己实现拷贝构造函数，编译器就会默认生成一个，但是编译器默认生成的是浅拷贝，不可以。
//拷贝构造 vector(const vector<T>& v) { //扩容 reserve(v.capacity()); memcpy(_start, v._start, sizeof(T) * v.size()); _finish = _start + v.size(); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
现在我们写完这个函数的拷贝构造之后，看看是否有问题：
提前告诉大家，这个程序会崩溃，因为memcpy()实现的是浅拷贝，他仅仅会拷贝v3的首尾指针，并不会开一个新的空间去存储相应的字符串。所以，程序结束时，调用析构函数，会连续析构两次！**解决办法：**不适用memcpy()自己实现深拷贝，使用‘=’即可实现，因为string赋值操作就是深拷贝，string的赋值，就会先开空间，再拷贝！
//拷贝构造 vector(const vector<T>& v) { //扩容 reserve(v.capacity()); //memcpy(_start, v._start, sizeof(T) * v.size()); for (size_t i = 0; i <v.size(); i++) { _start[i] = v._start[i]; //变成string对象的拷贝 } _finish = _start + v.size(); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
但是reverse()也会产生这个浅拷贝的问题，因此将reserve也应该改成深拷贝。
void reserve(size_t n) { if (n > capacity()) { T* tem = new T[n]; const size_t sz = size(); //提前保存sz if (_start) { //memcpy(tem, _start, sizeof(T)*size()); //拷贝过去 for (size_t i = 0; i < size(); i++) { tem[i] = _start[i]; } delete[] _start; } _start = tem; _finish = _start + sz; //使用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
这样vector的问题就解决了。但是vector
=运算符重载***（重点）
这里暴露了一个问题，就是虽然外面的vector是深拷贝，但是里面的vector是浅拷贝，是由于没有写vector的赋值重载，再补充一个赋值重载即可！
vector<T>& operator=(vector<T> v) { swap(v); return *this; } void swap(vector<T>& 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
- 8
- 9
- 10
- 11
- 12
运算符重载和拷贝构造这里写的不太详细，后续还会补充！
-
相关阅读:
概率论与数理统计
华为云云耀云服务器L实例评测｜华为云耀云服务器L实例评测用例(五)
【python与数据分析】Tushare库详解（1）
es 官方诊断工具
【Verilog】时序逻辑电路 -- 程序设计与应用
“童”趣迎国庆 安全“童”行-柿铺梁坡社区开展迎国庆活动
水墨屏超高频电子标签|RFID电子纸之可视化标签组态软件操作流程
基于pgrouting的路径规划处理
go 线程限制数量v1 --chatGPT
英语六级-day7
- 原文地址：https://blog.csdn.net/weixin_45153969/article/details/134168648
