【STL源码剖析】vector类模拟实现了解底层-走进底层-掌握底层【超详细的注释和解释】

今天博主继续带来STL源码剖析专栏的第二篇博客了！
今天带来vector的模拟实现！
其实在很多人学习C++过程中，都是只学习一些STL的使用方式，并不了解底层的实现。博主本人认为，这样的学习这样的技术是不深的。如果我们想要熟悉的掌握一门语言，我认为，底层的实现必不能少！
但是，想从0开始模拟实现STL的容器，需要我们熟悉C++的语法，特别是类和对象部分的知识！
博主学习C++到现在，我认为C++类和对象基本语法的学习比任何部分都要重要，而我花在这上面的时间也是最多的！只要搞清楚C++面向对象编程的基本规则，我们才能在STL的世界里游刃有余！
所以我希望大家在学习STL之前，先将数据结构与算法，C++的类和对象部分内容掌握熟悉！

前言

那么这里博主先安利一下一些干货满满的专栏啦！

手撕数据结构https://blog.csdn.net/yu_cblog/category_11490888.html?spm=1001.2014.3001.5482这里包含了博主很多的数据结构学习上的总结，每一篇都是超级用心编写的，有兴趣的伙伴们都支持一下吧！算法专栏https://blog.csdn.net/yu_cblog/category_11464817.html这里是STL源码剖析专栏，这个专栏将会持续更新STL各种容器的模拟实现。

STL源码剖析https://blog.csdn.net/yu_cblog/category_11983210.html?spm=1001.2014.3001.5482

实现过程中要注意的一些点

vector类其实是我们非常常用的一个容器，其底层其实就是一个顺序表。

博主在带大家实现的过程中，并不会把STL里面每一个成员函数都去模拟实现一次，我们模拟实现容器底层的目的其实是去学习里面实现的思路。

因此，博主只会将一些重要、常用的成员函数模拟实现给大家。

另外，除了博主实现的源代码之外，博主还提供一份测试代码，它可以帮助我们检查自己写的代码是否准确。

在测试代码中遇到的问题和解决思路以及一些细节的处理，博主都在.h和.cpp代码里用注释的形式给大家说明白(注释满满干货不要错过噢)。

希望大家可以从中学到知识。

MyVector.h完整源代码

#pragma once
#include<cassert>
#include<string.h>
#include<algorithm>
#include<functional>
namespace yufc {template<class T>class vector {public:typedef T* iterator;//这个要放成共有，不然迭代器外面访问不了 -- 定义迭代器类型是指针类型typedef const T* const_iterator;//vector的迭代器就是原生指针iterator begin() {return _start;}iterator end() {return _finish;}//如果不提供const迭代器 -- 如果传了const的vector是遍历不了的，因为权限不能放大const_iterator begin()const { //不能返回普通迭代器，要返回const迭代器return _start;}const_iterator end()const {return _finish;}vector() :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {}~vector() {delete[] _start;_start = _finish = _end_of_storage = nullptr;}//stl的vector还支持使用迭代器区间去构造//为什么需要一个其它类型的迭代器？//因为他要支持用其它容器的迭代器的区间构造template<class InputIterator>vector(InputIterator first, InputIterator last) :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){while (first != last) {//不能直接push_back()，直接push_back()会崩溃 -- 因为没有初始化 -- 野指针push_back(*first);++first;}}vector(size_t n, const T& val = T()) :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){//用n个值去构造reserve(n);for (size_t i = 0; i < n; i++) {push_back(val);}}//传统拷贝构造
#if 0vector(const vector<T>& v) {_start = new T[v.size()];//这里是给size还是capacity呢？STL没有要求//memcpy(_start, v._start, sizeof(T) * v.size());//解决vector<vector<int>>深拷贝的情况,memcpy不能帮助内层的自定义类型完成深拷贝，赋值可以（我们写好了自定义类型的赋值）for (size_t i = 0; i < v.size(); i++) {_start[i] = v._start[i];}_finish = _start + v.size();_end_of_storage = _start + v.size();//因为T[]里面给了size(),所以这里也应该是v.size()}
#endif//写法2
#if 0vector(const vector<T>& v) :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(v.size());for (const auto& e : v) { //注意：这里拷贝过去一定要引用，不然又要拷贝了//写深拷贝自己还要调深拷贝 -- 肯定是会出问题的push_back(e);}//不需要去调整_finish,因为push_back()已经搞定了}
#endif//现代写法拷贝构造 -- 复用迭代器区间构造函数void swap(vector<T>& v) {std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}
#if 1vector(const vector<T>& v) :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){vector<T>tmp(v.begin(), v.end());swap(tmp);//当然自定义类型自己写的swap更高效 -- 我们自己实现一个}
#endifvector<T>& operator=(vector<T> v) { //v1=v2//v是v2的拷贝，而且是局部的，swap完之后给到v1，v还会自动析构（因为是局部对象）swap(v);return *this;}size_t capacity()const {return _end_of_storage - _start;}size_t size()const {return _finish - _start;}void reserve(size_t n) {if (n > capacity()) {T* tmp = new T[n];size_t sz = size();if (_start) {//memcpy(tmp, _start, sizeof(T) * sz);//拷贝size()个字节过去，先放到tmp里面//同样，解决//vector<自定义类型>的问题for (size_t i = 0; i < sz; i++) {tmp[i] = _start[i];//当T是自定义类型时，调用T类型的operator=}delete[] _start;}_start = tmp;//_finish = _start + size();//这里不要现场去算size()//因为size()是用start减出来的，上面那一行start已经变了//所以在前面我们最好保留一下size先_finish = _start + sz;_end_of_storage = _start + n;}}void resize(size_t n, const T& val = T()) {//1.扩容+初始化//2.初始化//3.删除数据if (n > capacity()) {reserve(n);}if (n > size()) {//初始化填值while (_finish < _start+n) {*_finish = val;++_finish;}}else {_finish = _start + n;}}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 push_back(const T& x) {//加了const保证传什么类型都行，因为隐式类型转换临时变量具有常性if (_finish == _end_of_storage) {reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}void pop_back() {assert(_finish > _start);//为空是不能删的--_finish;}void insert(iterator pos, const T& x) {assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage) {//扩容//记住pos和start的相对位置size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;//更新pos的位置 -- 解决迭代器失效}//挪动数据iterator end = _finish - 1;while (end >= pos) { // insert要扩容的时候，这个循环就失效了，停不下来了，为什么？*(end + 1) = *end;end--;}//扩容之后，旧空间的数据拷贝到新空间//旧空间已经被释放了 -- pos是指向旧空间的一个数字的位置的//pos成了野指针！ -- 迭代器失效//所以我们要把pos更新一下// -- 修改了内部的pos之后，其实问题还没有根本的解决*pos = x;++_finish;}iterator erase(iterator pos) {assert(pos >= _start);assert(pos < _finish);//挪动覆盖删除iterator begin = pos + 1;while (begin < _finish) {*(begin - 1) = *begin;++begin;}--_finish;//删除了位置的下一个位置 -- 还是posreturn pos;}T& front() {assert(size() > 0);return *_start;}T& back() {assert(size() > 0);return *(_finish - 1);}private:iterator _start;//start相当于整个数组的开始位置iterator _finish;//[_start,_finish)iterator _end_of_storage;};
}

test.cpp测试源文件完整代码

#define _CRT_SECURE_NO_WARNINGS 1#include"MyVector.h"
#include<iostream>
#include<vector>
using namespace std;void PrintVector(yufc::vector<int>& v) {//在没有写拷贝构造的时候，这里一定要引用的，不然浅拷贝，释放两次会出问题yufc::vector<int>::iterator it = v.begin();while (it != v.end()) {cout << *it << " ";it++;}cout << endl;
}
void PrintVector(const yufc::vector<int>& v) {yufc::vector<int>::const_iterator it = v.begin();while (it != v.end()) {cout << *it << " ";it++;}cout << endl;
}
void test_vector1() {yufc::vector<int>v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);for (int i = 0; i < v.size(); i++) {++v[i];cout << v[i] << " ";}cout << endl;
}
void test_vector2() {yufc::vector<int>v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);yufc::vector<int>::iterator it = v.begin();while (it != v.end()) {(*it)--;cout << *it << " ";it++;}cout << endl;for (auto& e : v) {e++;cout << e << " ";}cout << endl;it = v.begin();while (it != v.end()) {cout << *it << " ";it++;}cout << endl;PrintVector(v);
}
void test_vector3() {const yufc::vector<int>v;
#if 0 //改不了的v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);
#endifPrintVector(v);//范围for虽然是傻瓜式的替换 -- 但是它也是会调用const迭代器的
}
//迭代器失效问题
void test_vector4() {yufc::vector<int>v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);//v.push_back(5); // 我们发现  -- 原来4个数据，insert之后要扩容的时候，就出现问题了！//v.push_back(6);yufc::vector<int>::iterator it = v.begin();while (it != v.end()) {cout << *it << " ";it++;}cout << endl;//auto p = find(v.begin(), v.end(), 3);if (p != v.end()) {v.insert(p, 30);//在内部初步解决迭代器失效之后，其实问题还是没有根本解决！//因为内部的pos更新不会影响p//所以我们在使用的时候//在p位置插入数据以后，不要访问p，因为p可能失效了//因为我们使用STL的时候，不了解底层的扩容机制，所以以后我们insert之后，不要去访问p位置！ -- 可能会有问题//那能否把insert第一个参数改成&行吗？ -- 尽量不要这样做 -- 和库保持一致好//虽然我们看似解决了问题 -- 但是改了可能会引出其它问题 -- 比如，头插，我们想传v.begin();v.insert(v.begin(), 0);//编不过，因为类型不匹配
#if 0cout << *p << endl;v.insert(p, 40);
#endif}PrintVector(v);
}
//erase迭代器会失效吗？
//库里面的erase会失效吗？ -- 不知道
//STL并没有规定什么机制
//有没有一种可能，当size()<capacity()/2的时候，缩一下容（缩容：以时间换空间）
//反正用完那个别访问，别动那个p就行了！
void test_vector5() {yufc::vector<int>v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);auto p = find(v.begin(), v.end(), 3);if (p != v.end()) {v.erase(p);}PrintVector(v);
}
void test_vector6() {yufc::vector<int>v;
#if 0v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);
#endif//情况1和2//我们发现此时有这个5 -- 程序正常，没有 -- 崩溃
#if 1//情况3v.push_back(1);v.push_back(2);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);
#endif//要求删除所有的偶数auto it = v.begin();//情况3的时候，it会跳过end()，直接继续往后了 -- 崩溃//所以下面这段算法是不正确的！//其实我们看源代码可以发现 -- erase是有返回值的 -- 会更新一下迭代器//STL规定erase返回删除位置下一个位置的迭代器！//vs这个编译器是查的很严格的 -- erase之后不允许去访问！ -- 访问就报错//Linux下就不同while (it != v.end()) {if (*it % 2 == 0) {it = v.erase(it);//我们要返回一个it才行}else {++it;}}PrintVector(v);
}
//总结
//其实迭代器失效，我们在自己做OJ的时候也能体会的，插入或者删除之后，迭代器指向了它不该指向的地方
//在使用vector的迭代器的时候，要多调试！void test_vector7() {//系统默认的拷贝//1.自定义类型 -- 调拷贝构造 -- 默认生成的 -- 浅拷贝//2.内置类型 -- 值拷贝 -- 浅拷贝yufc::vector<int>arr;arr.push_back(1);arr.push_back(2);arr.push_back(3);for (auto i : arr) {cout << i << " ";}cout << endl;yufc::vector<int>arr2 = arr;//调用系统默认的话就是浅拷贝，这样程序肯定会崩溃的 -- 析构了两次//而且如果是浅拷贝，改一边的值另一边也会被改变arr2[0] = 100; //两边都会被改变的 -- 所以我们需要深拷贝！for (auto i : arr) {cout << i << " ";}cout << endl;for (auto i : arr2) {cout << i << " ";}
}
void test_vector8() {string s("hell");yufc::vector<int>vs(s.begin(), s.end());for (auto i : vs) {cout << i << " ";}cout << endl;//赋值yufc::vector<int>v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vs = v;//要实现一个深拷贝//当然，如果f11 -- 这里是先进去拷贝的，因为传参要拷贝//走完拷贝就进去赋值了for (auto i : vs) {cout << i << " ";}
}
//其实内置类型也有构造
void test_type() {int i = 0;int j = int();int k = int(10);
}
void test_vector9() {//vector<int>v = { 1,2,3,4,5 };vector<int>v(10);yufc::vector<int>v(10, 1);//这样就报错了,如果传了两个参数都是int//这里出问题就是匹配问题，它匹配到不该去的地方去了//为什么 -- 因为迭代器区间构造那个函数，更适合这样传参 -- 所以进到那里去了//解决：//1.传参的时候写(10u,1)表示这个是个usigned int类型//2.把vector(size_t n,const T&val=T())里面的size_t改成int，也可以解决 -- 但是stl官方给的是size_t//3.复制一份，改成int，弄个重载就行 -- stl_3.0是这样解决的for (auto i : v) {cout << i << " ";}cout << endl;
}
void test_vector10() {yufc::vector<int>v;v.resize(10, 1);for (auto e : v) {cout << e << " ";}cout << endl;yufc::vector<int>v1;v1.reserve(10);v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.resize(8, 8);for (auto e : v1) {cout << e << " ";}cout << endl;v1.resize(20, 20);for (auto e : v1) {cout << e << " ";}cout << endl;v1.resize(3);for (auto e : v1) {cout << e << " ";}cout << endl;
}//vector到目前为止还有最后一个坑还没有解决
//我们用自己的vector测试一下杨辉三角
class Solution {
public:yufc::vector<yufc::vector<int>> generate(int numRows) {yufc::vector<yufc::vector<int>> ret(numRows);for (int i = 0; i < numRows; ++i) {ret[i].resize(i + 1);ret[i][0] = ret[i][i] = 1;for (int j = 1; j < i; ++j) {ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];}}return ret;}
};
void test_vector11() {Solution().generate(10);//报错 -- 在函数结束的时候崩溃了//修改一下 -- 把函数改成void类型，不return -- 没事了//为什么？//拷贝有问题了 -- 普通的vector深拷贝没问题 -- 这里的深拷贝有问题//里面是浅拷贝，外面是深拷贝// //            //即：我们的vector是深拷贝了 -- 但是里面的自定义类型没有深拷贝！！！！！！！！！！//我们拷贝的时候，外面的空间是深拷贝，但是里面的东西，还是指向以前的地方//传统写法是因为memcpy导致的 -- 我们将memcpy改成一个一个赋值就行了（这样的话自定义类型也可以完成深拷贝（调用自己的deepcopy））//现代写法是因为因为要调用push_back()，而push_back()里面调用reserve(),是reserve()里面的memcpy出问题
}
int main() {//test_vector1();//test_vector2();//test_vector3();//test_vector4();//test_vector5();//test_vector6();//test_vector7();//test_vector8();//test_type();//test_vector9();//test_vector10();test_vector11();return 0;
}//我们一定要清晰一个点：
//STL只是一个规范
//这个规范怎么去实现，是没有规定的！
//VS-PJ版   g++ SGI版