【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 << ' ';}}
