【C++】STL——vector底层实现
目录
💕 1.vector三个核心
💕2.begin函数，end函数的实现（简单略讲）
💕3.size函数，capacity函数的实现 （简单略讲）
💕4.reserve函数实现 （细节详见）
💕5.resize函数实现（简单略讲，纯小计算）
💕6.其他功能函数实现（略讲，都是顺序表那一套没有改变）
💕7.整体代码实现
💕8.底层模拟测试 .cpp
💕9.完结
一个人的坚持到底有多难
声明:此文内容基于此文章->:【C++】STL——vector的使用
💕 1.vector三个核心
在vector中，核心成员并不是我们在数据结构实现的顺序表，如size，capacity,data,而是下面三个->:
#pragma once #include<iostream> #include<assert.h> using namespace std; namespace yz { template<class T> class vector { typedef T* iterator; typedef const T* const_iterator; public: private: iterator _start = nullptr; iterator _finish = nullptr; iterator _end_of_storage = nullptr; }; }我们把元素的地址T*,命名为迭代器类型，iterator
接下来分别是顺序表起始位置的地址，顺序表的 size 用 _finish 来表示，顺序表的capacity用_end_of_storage来表示
💕2.begin函数，end函数的实现（简单略讲）
我们知道vector库中的begin函数与end函数返回的虽然是迭代器，但是可以像指针一样使用，因此我们可以很好的实现，如下->:
iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin()const { return _start; } const_iterator end()const { return _finish; }
💕3.size函数，capacity函数的实现 （简单略讲）
size函数与capacity函数的实现更是简单，直接用指针相减即可
size_t size() { return _finish - _start; } size_t capacity() { return _end_of_storage - _start; }
💕4.reserve函数实现 （细节详见）
代码看不懂的请往下看图片讲解
//reserve预留空间 T* reserve(size_t n) { size_t old_size = size(); if (n > capacity()) { T* tep = new T[n+1];//开辟n个空间，+1是为了单独考虑string //将内容复制过去 for (int i = 0; i < size(); i++) { tep[i] = _start[i]; } delete[] _start; _start = tep; _finish = _start + old_size; _end_of_storage = _start + n; tep = nullptr; } return _start; }我们知道，capacity函数开辟的新空间只会增大，不会缩小，而开辟新空间我们需要做的第一件事就是转移数据
这里需要先思考下如何转移，如果用strcpy只可以转移string类，那怎么办?用memmove吗?
不，memmove的复制时一个字节一个字节复制过去的，虽然复制int，double时没有问题，但如果复制的是stirng类型，我们知道，string类的成员变量是字符串首地址，在使用memmove复制时字符串的首地址原封不动的复制了过去，这就会造成我们在释放旧空间后，白进行了memmove的复制，这是不可取的，所以我们要用到for循环转移数据，下面有图->:
转移数据思考完了，我们接着思考为什么要old_size,我们拷贝完数据后，需要转移的就是三大核心，start,finish,和end_of_storage,那么我们将数据转移后，释放掉原来的旧空间，就会导致finish和end_of_storage指向的是野指针，所以我们需要保留原来的old_size,这样才能让finish指向正确的位置
💕5.resize函数实现（简单略讲，纯小计算）
//resize预留空间 T* resize(size_t n,const T& val) { if (n > size()) { reserve(n);//先开辟出足够的空间 size_t newsize = n - size(); while (newsize > 0) { *(_finish++) = val; newsize--; } } return _start; }
💕6.其他功能函数实现（略讲，都是顺序表那一套没有改变）
//判断空 bool empty() { if (size() == 0) { return true; } } //尾插 void push_back(const T& x) { if (size() == capacity()) { size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); reverse(newcapacity); } *_finish = x; _finish++; } //尾删 void pop_back() { empty(); *_finish = 0; _finish--; } //指定位置插入 void insert(iterator pos, const T& val) { assert(pos >= _start && pos <= _finish); if (size() == capacity()) { size_t count = pos - _start; size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); reverse(newcapacity); pos = _start + count; } T* tep = _finish; while (tep >= pos) { *(tep) = *(tep - 1); tep--; } *(pos) = val; _finish++; } void erase(iterator pos) { assert(pos >= _start && pos < _finish); empty(); _finish--; while (pos < _finish) { *(pos) = *(pos + 1); pos++; } }
💕7.整体代码实现
#pragma once #include<iostream> #include<assert.h> using namespace std; namespace yz { template<class T> class vector { public: 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; } size_t size() { return _finish - _start; } size_t capacity() { return _end_of_storage - _start; } //reserve预留空间 T* reserve(size_t n) { size_t old_size = size(); if (n > capacity()) { T* tep = new T[n+1];//开辟n个空间，+1是为了单独考虑string //将内容复制过去 for (int i = 0; i < size(); i++) { tep[i] = _start[i]; } delete[] _start; _start = tep; _finish = _start + old_size; _end_of_storage = _start + n; tep = nullptr; } return _start; } //resize预留空间 T* resize(size_t n,const T& val) { if (n > size()) { reserve(n);//先开辟出足够的空间 size_t newsize = n - size(); while (newsize > 0) { *(_finish++) = val; newsize--; } } return _start; } //判断空 bool empty() { if (size() == 0) { return true; } } //尾插 void push_back(const T& x) { if (size() == capacity()) { size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); reverse(newcapacity); } *_finish = x; _finish++; } //尾删 void pop_back() { empty(); *_finish = 0; _finish--; } //指定位置插入 void insert(iterator pos, const T& val) { assert(pos >= _start && pos <= _finish); if (size() == capacity()) { size_t count = pos - _start; size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); reverse(newcapacity); pos = _start + count; } T* tep = _finish; while (tep >= pos) { *(tep) = *(tep - 1); tep--; } *(pos) = val; _finish++; } void erase(iterator pos) { assert(pos >= _start && pos < _finish); empty(); _finish--; while (pos < _finish) { *(pos) = *(pos + 1); pos++; } } private: iterator _start = nullptr; iterator _finish = nullptr; iterator _end_of_storage = nullptr; }; }
💕8.底层模拟测试 .cpp
#define _CRT_SECURE_NO_WARNINGS #include"vector.h" int main() { yz::vector<int> a1; /*a1.resize(200,3); cout<<a1.size()<<' '<<a1.capacity(); a1.empty();*/ a1.insert(a1.begin(), 99); a1.insert(a1.begin(), 88); a1.push_back(0); a1.push_back(20); a1.push_back(28); a1.pop_back(); a1.erase(a1.begin()); a1.erase(a1.end()-1); a1.resize(200, 5); a1.reserve(300); yz::vector<int> a2; if (a2.empty()) { cout << "空" << endl; } for (auto e : a1) { cout << e << ' '; } }
