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

💕9.完结