一、vector的源码分析
这里我们只是简单的去了解一下原码即可，后序将会出一个专题着重剖析stl源码
1.分析思路
vector的原码有很多版本，我们采用与侯捷老师的《STL原码剖析》这本书同一个版本的原码
对于我们所看的vector原码，我们首先要关注的是成员变量。这个是最核心的部分。
如下所示，这三个就是我们的成员变量
可以注意到，vector原码采用的是三个迭代器作为成员变量，这与我们之前的string是有所差异的。既然是迭代器，那么我们就在来找找迭代器真正的类型是什么？
如下图所示
我们可以注意到在源码中，迭代器实际上就是我们的模板参数T，T就是我们vector里面每个数据的类型，这些迭代器本质就是T的指针。因为对于vector就是一个顺序表，所以它完全可以用原生的指针作为迭代器
现在我们已经知道了成员变量及其类型，可以看到是与我们原来所想的有所差异，那么我们就要进行对比，与正常的顺序表它这些成员变量究竟是什么意思？为了得知这些成员变量是什么意思，我们需要做的就是看构造函数和插入接口
2.构造函数和插入接口
如下所示，是我们找到的构造函数
对于第一个无参的构造，它的作用是将三个指针全部置空。这里我们似乎也看不出什么来
既然如此，那么我们再来关注一下这个尾插函数
既然关注到了尾插，那么肯定涉及到扩容
接下来我们就可以根据这两个函数进行猜测成员变量都是啥意思。事实上根据单词的意思，我们已经可以猜测的七七八八了，这两个函数起到的作用就是可以进行验证我们猜测的是否正确
有了上面的猜测，尾插函数其实我们大概也就能够读懂。至于reserve函数，我们也可以看出来它显示开好空间，然后释放掉原来的空间，在最后的三行中，再次验证了我们的猜测
二、手把手教你写一个简单的vector
1.基本结构
我们的基本结构如下所示
2.迭代器与私有成员变量的定义
根据前面的分析，我们很容易写出成员变量和迭代器的定义
template<class T> class vector { public: typedef T* iterator; typedef const T* const_iterator; private: iterator _start; iterator _finish; iterator _end_of_storage; };
3.构造函数
如下所示，是最基本的无参的构造函数，我们只需要将全部的置空即可
vector() :_start(nullptr) ,_finish(nullptr) ,_end_of_storage(nullptr) {}
4.size和capacity
这个两个也是很重要的接口，后序的很多测试都是需要依靠他的
size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; }
5.迭代器函数接口
迭代器接口也是比较容易写出来的。和string是类似的，这里不再赘述
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; }
6.析构函数
析构函数也是最基本必须要完成的默认成员函数之一，我们当_start不为空的时候，直接释放掉内存即可
~vector() { if (_start) { delete[] _start; _start = nullptr; _finish = nullptr; _end_of_storage = nullptr; } }
7.reserve接口
这个接口起着扩容的重大作用，当我们增加数据的时候，必须要先判断是否需要进行扩容。当我们要求的容量大于我们实际的容量时候，我们就开辟一块新的空间，然后拷贝数据，最后释放掉原来的数据。最后改变指针的指向，需要注意的是，我们最好提前算好原来的size，以便后来_finish指针的计算。
void reserve(size_t n) { if (n > capacity()) { iterator tmp = new T[n]; int sz = size(); if (_start) { memcpy(tmp, _start, sizeof(T) * sz); delete[] _start; } _start = tmp; _finish = _start + sz; _end_of_storage = _start + n; } }
8.尾插
有了前面的接口，我们现在可以去实现一下尾插的接口，这个逻辑也是很简单的，当finish和end_of_storage相等的时候，就是需要扩容了，然后我们直接插入数据即可
void push_back(const T& val) { if (_finish == _end_of_storage) { size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); } *_finish = val; _finish++; }
9.operator[]运算符重载
对于这个接口，它和string的基本实现也是类似的，需要注意要写两个函数重载，这是为了保证const对象只读和普通对象读写的特性
T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos) const { assert(pos < size()); return _start[pos]; }
10.简单的测试前面的接口
我们使用如下代码对前面接口进行测试。
void Print(const Sim::vector<int>& v) { for (auto e : v) { cout << e << " "; } cout << endl; } void testvector2() { Sim::vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(4); v.push_back(4); for (size_t i = 0; i < v.size(); i++) { v[i]++; } for (auto e : v) { cout << e << " "; } cout << endl; Print(v); cout << endl; }
经过测试后，符合我们的预期
11.insert以及迭代器失效问题
对于这个接口，我们的思路是这样的，首先我们先断言，pos在合理的范围之内，然后当容量满了以后，我们进行扩容，注意在这里扩容时候要小心，这里当我们扩容以后，pos会失效的，因为pos还是指向原来的空间，我们扩容完以后已经将原来的空间给释放了，所以pos会失效。这就是迭代器失效问题，为了防止pos失效，我们需要先记录pos的相对位置，然后当扩容以后重新加上去就可以计算出新的pos位置了。
void insert(iterator pos, const T& val) { assert(pos >= _start && pos <= _finish); if (_finish == _end_of_storage) { int sz = pos - _start; int newcapacity= capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); pos = _start + sz; } iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *(end); end--; } *pos = val; _finish++; }
最后我们就可以正常的按照我们逻辑进行挪动数据和插入数据了。
下面是我们的测试代码
void testvector3() { Sim::vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.insert(v.begin(), 10); v.insert(v.begin(), 10); v.insert(v.begin(), 10); v.insert(v.begin(), 10); v.insert(v.begin(), 10); for (auto e : v) { cout << e << " "; } cout << endl; }
其实上面的仅仅只是内部的迭代器失效问题，这个问题我们已经得到了解决，还有一类迭代器失效是外部的迭代器失效问题，如下所示的测试代码，当我们想要在某处插入多次数据的时候，可能会引发pos失效的问题，这是因为，在内部插入数据需要扩容的时候已经修改了pos的值，pos的位置已经被改变了。而在外部还在使用原来的pos自然是不行的
可见，我们的程序引发了断言错误，正是由于pos已被内部所改变了。故同一个pos不可以连续使用
那么在这里，我们可能会想，能否在传参的时候对pos使用传引用呢。其实这样也是错的，这是因为如果传引用的话，会涉及到权限放大的问题。由于pos里面的数据肯定是要被修改的，所以pos肯定不可以使用const迭代器。故参数必须使用普通的迭代器。而如果我们在传参的时候，我们实参写了一个运算表达式。运算表达式返回一个结果的时候会产生一个临时变量，临时变量具有常性。由此权限放大了。故不可以使用传引用。或者当我们直接使用迭代器begin函数作为实参的话，由于这个迭代器是传值返回，也是会产生临时变量，故仍然会权限放大。再次说明了不可以传引用。
所以insert以后迭代器可能失效
insert以后就不要使用这个形参迭代器了，因为他可能已经失效了
继续使用它就是一个高危行为
在库里面它的解决方案就是带一个返回值
库里面这个返回值返回的是新插入元素的位置
这样一来我们就可以从外部规避这个迭代器失效问题了
所以真正的代码应该是这样的：
iterator insert(iterator pos, const T& val) { assert(pos >= _start && pos <= _finish); if (_finish == _end_of_storage) { int sz = pos - _start; int newcapacity= capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); pos = _start + sz; } iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *(end); end--; } *pos = val; _finish++; return pos; }
12.erase以及迭代器失效
对于erase，我们可以很容易的写出如下代码，即依次往前挪动。这个思路看上去确实没什么毛病
void erase(iterator pos) { assert(pos >= _start && pos < _finish); if (_start) { iterator end = pos + 1; while (end != _finish) { *(end - 1) = *end; end++; } _finish--; } }
但是当我做出如下操作的时候，发生了断言错误
其实仔细一想也确实是这样的，因为我们删除了倒数第二个值以后， 原来的pos还是指向那个位置，这里的pos已经是最后一个位置了。当再次删除的时候，必然产生pos断言错误。这就意味着pos已经不是指向原来的值了，已经失效了。继续使用pos有可能会越界或者跳过了某些数据。
如果是vs的std库里面的话，直接程序报错
下图的其实不算足够严谨，因为我们已经改变了pos，相当于我们没有连续使用同一个迭代器，vs不会直接暴力报错。这里崩溃原因其实还是因为越界了。
如下图所示，还算比较严谨，因为我们连续使用同一个pos，vs直接暴力检查，直接报错。但是在linux下，并没有如此暴力的检查。但是我们还是不能这样写，因为我们不可以让一个代码可以在linux下可以跑，但是vs下不能跑，这样代码移植性太差了。
也就是说
erase以后，迭代器失效了，vs进行了强制检查，直接报错，必须要重新给pos赋值，才可以不报错
而在linux下的g++编译器，并没有做直接报错的处理，但是结果很可能不符合我们的预期，有可能会产生非常危险的现象
标准为了避免迭代器失效，所以就要给pos重新赋值，那么我们只能给函数添加返回值了
如上可知，它这个返回的是刚刚被删除的那个元素的下一个位置。
所以最终代码是这样的
iterator erase(iterator pos) { assert(pos >= _start && pos < _finish); if (_start) { iterator end = pos + 1; while (end != _finish) { *(end - 1) = *end; end++; } _finish--; } return pos; }
总结：vector在使用完erase和insert迭代器对象以后，不能在使用这个迭代器了，我们认为迭代器失效了，因为结果是未定义的
13.尾删
如下所示，我们既可以直接调用erase复用，也可以自己直接写一个都是可以的。
void pop_back() { if (_start) { _finish--; } //erase(_finish-1); }
14.resize
resize的基本逻辑我们都明白，但是有一点需要注意的是，如果处理第二个缺省参数，对于内置类型我们直接给0当然是可以的，但是倘若是构造类型的话，显然是不可以的。我们这里的策略是给一个匿名对象，这个匿名对象就是默认构造出来的，这就意味着我们每一个对象最好都写上默认构造函数，否则迟早会出问题的。但是内置类型严格来说是没有默认构造函数这一说法的。但是C++中对内置类型做了升级。让内置类型也类似于有了默认构造。
如下代码所示。
最终我们代码如下所示
void resize(size_t n, const T& val = T()) { if (n < size()) { _finish = _start + n; } else { reserve(n); while (_finish != _start + n) { *_finish = val; _finish++; } } }
如下是测试结果
15.拷贝构造
如下代码所示，这是一个典型的深拷贝问题。
vector(const vector<T>& v) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { _start = new T[v.capacity()]; memcpy(_start, v._start, sizeof(T) * v.size()); _finish = _start + v.size(); _end_of_storage = _start + v.capacity(); }
运行结果如下所示
当然拷贝构造不仅仅这一种写法，还有很多种写法。如下所示
vector(const vector<T>& v) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { reserve(v.capacity()); for (auto e : v) { push_back(e); } }
16.赋值运算符重载
这里我们可以直接使用现代写法，比较容易简洁
void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish,v._finish); std::swap(_end_of_storage,v._end_of_storage); } vector<T>& operator=(vector<T> v) { swap(v); return *this; }
测试结果如下所示：
17.再谈reserve
当我们写出这样的代码的时候，我们惊讶的发现，居然报错了
void testvector6() { Sim::vector<string> v; v.push_back("1111"); v.push_back("2222"); v.push_back("3333"); v.push_back("4444"); v.push_back("5555"); for (auto e : v) { cout << e << " "; } cout << endl; }
这个代码咋一看好像没什么大问题，而且在我们使用内置类型的连续尾插时候也没有出现问题，那么这里为什么会出现问题呢？
我们可以将内存图给画出来
如下图所示，这是我们一开始的情形
当我们再次插入数据的时候，我们发现需要进行扩容了，于是在我们扩容的时候，我们使用reserve函数，它里面有个部分是memcpy
注意，这里的memcpy就是原罪。因为我们这里对于vector来说，确实是一个深拷贝，但是对于string而言，它里面的数据是一个浅拷贝。
当我们程序结束需要delete的时候，就会出事了，程序第二次析构。
所以这里的问题就是：vector是深拷贝，但是vector空间上存的对象是string数组，使用memcpy会导致string对象的浅拷贝
解决方案也很简单，把这行代码给替换一下，下面我们所使用的看似简单，实则内藏玄机，注意看，我们看似使用了一个简单的变量，在这个遍历中，我们将原来的每一个_start所指向的数组依次使用赋值运算符重载交给新的数组中，这样一来深拷贝的问题就交给了赋值运算符重载。从而成功的规避了这个问题
void reserve(size_t n) { if (n > capacity()) { iterator tmp = new T[n]; int sz = size(); if (_start) { //memcpy(tmp, _start, sizeof(T) * sz); for (size_t i = 0; i < size(); i++) { tmp[i] = _start[i]; } delete[] _start; } _start = tmp; _finish = _start + sz; _end_of_storage = _start + n; } }
现在我们的代码就可以正常运行了
18.再谈拷贝构造
reserve存在浅拷贝的问题，那么拷贝构造是否也存在呢？因为我们的拷贝构造也是使用了memcpy，我们可以验证一下。结果发现确实也存在问题
既然如此，那么我们也进行一次修正，去处理掉这个问题
vector(const vector<T>& v) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { _start = new T[v.capacity()]; //memcpy(_start, v._start, sizeof(T) * v.size()); for (size_t i = 0; i < v.size(); i++) { _start[i] = v[i]; } _finish = _start + v.size(); _end_of_storage = _start + v.capacity(); }
这里笔者在给一段测试代码，这段代码的拷贝构造部分的分析极其复杂，有兴趣的可以去研究一下。
void testvector7() { Sim::vector<Sim::vector<int>> v; Sim::vector<int> vv; vv.push_back(1); v.push_back(vv); v.push_back(vv); v.push_back(vv); v.push_back(vv); v.push_back(vv); Sim::vector<Sim::vector<int>> v1(v); for (Sim::vector<int> e : v) { for (int c : e) { cout << c << " "; } cout << endl; } }
19.用n个val去构造
这个代码我们可以直接复用前面的resize
需要注意的是，这个初始化列表一定要写，或者给成员变量写缺省参数都是可以的。如果不写的话，那么会出现很多问题的。
vector(size_t n, const T& val = T()) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { resize(n, val); }
如下是一个简单的测试代码
void testvector8() { Sim::vector<int> v(10, 1); for (int e : v) { cout << e << " "; } cout << endl; }
20.用迭代器区间构造函数
我们可以很容易的写出以下代码
template<class InputIterator> vector(InputIterator first, InputIterator last) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { while (first != last) { push_back(*first); first++; } }
但是当我们运行的时候，发现了一个很奇怪的错误
为什么说奇怪呢？首先是我们测试用例并没有做出任何改变，我们仅仅只是加了一个迭代器区间构造函数，而且报的错误是非法的间接寻址。
事实上这是编译器的选择函数的问题
是由于以下两个函数产生冲突了
我们写的参数是10和1，编译器会认为是int类型的，但是第一个函数的第一个参数是无符号的整型，第二个的参数是可变的，理论上来说第二个是更匹配的。故编译器选择了第二个函数使用。而迭代器本应类似一个指针，这里却是一个普通的变量，当然会发生问题了。这个问题正好就是非法的间接寻址。
如果我们将代码写成10u的话，也就意味着第一个参数变为了无符号的整型。第二个参数是int是满足第一个函数的形式的，且不可能满足第二个函数的参数，因为第二个的两个参数必须是一致的，故这样下，编译器才会正确的选择函数
或者说，当我们的第二个参数确定好了，不可能与第一个是一样的，那这样编译器也不会错误的识别函数。比如说字符串类型等等
这样一来我们现在测试一下我们的迭代器区间初始化，可见符合我们的预期
这样还是不符合我们本应该的想法的，我们不可能每次都记得要多写一个u，在编译器中解决的方案就是多写了几个函数重载，改变了第一个参数的类型。这样的话编译器发现有一个是编译失败的，那么自然就会选择可以编译正确的函数。
三、vector完整代码
vector完整代码
#pragma once #include<iostream> #include<string.h> #include<assert.h> #include<algorithm> using namespace std; namespace Sim { 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; } vector() :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) {} vector(const vector<T>& v) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { _start = new T[v.capacity()]; //memcpy(_start, v._start, sizeof(T) * v.size()); for (size_t i = 0; i < v.size(); i++) { _start[i] = v[i]; } _finish = _start + v.size(); _end_of_storage = _start + v.capacity(); } //vector(const vector<T>& v) // :_start(nullptr) // , _finish(nullptr) // , _end_of_storage(nullptr) //{ // reserve(v.capacity()); // for (auto e : v) // { // push_back(e); // } //} vector(size_t n, const T& val = T()) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { resize(n, val); } vector(int n, const T& val = T()) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { resize(n, val); } template<class InputIterator> vector(InputIterator first, InputIterator last) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { while (first != last) { push_back(*first); first++; } } void swap(vector<T>& v) { std::swap(_start, v._start); std::swap(_finish,v._finish); std::swap(_end_of_storage,v._end_of_storage); } vector<T>& operator=(vector<T> v) { swap(v); return *this; } ~vector() { if (_start) { delete[] _start; _start = nullptr; _finish = nullptr; _end_of_storage = nullptr; } } size_t size() const { return _finish - _start; } size_t capacity() const { return _end_of_storage - _start; } void reserve(size_t n) { if (n > capacity()) { iterator tmp = new T[n]; int sz = size(); if (_start) { //memcpy(tmp, _start, sizeof(T) * sz); for (size_t i = 0; i < size(); i++) { tmp[i] = _start[i]; } delete[] _start; } _start = tmp; _finish = _start + sz; _end_of_storage = _start + n; } } void resize(size_t n, const T& val = T()) { if (n < size()) { _finish = _start + n; } else { reserve(n); while (_finish != _start + n) { *_finish = val; _finish++; } } } void push_back(const T& val) { if (_finish == _end_of_storage) { size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); } *_finish = val; _finish++; } void pop_back() { if (_start) { _finish--; } //erase(_finish-1); } T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const T& operator[](size_t pos) const { assert(pos < size()); return _start[pos]; } iterator insert(iterator pos, const T& val) { assert(pos >= _start && pos <= _finish); if (_finish == _end_of_storage) { int sz = pos - _start; int newcapacity= capacity() == 0 ? 4 : capacity() * 2; reserve(newcapacity); pos = _start + sz; } iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *(end); end--; } *pos = val; _finish++; return pos; } iterator erase(iterator pos) { assert(pos >= _start && pos < _finish); if (_start) { iterator end = pos + 1; while (end != _finish) { *(end - 1) = *end; end++; } _finish--; } return pos; } private: iterator _start; iterator _finish; iterator _end_of_storage; }; }
测试代码
#define _CRT_SECURE_NO_WARNINGS 1 #include<string.h> #include<string> #include<vector> #include"vector.h" void Print(const Sim::vector<int>& v) { for (auto e : v) { cout << e << " "; } cout << endl; } void testvector1() { Sim::vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(4); v.push_back(4); for (auto e : v) { cout << e << " "; } cout << endl; } void testvector2() { Sim::vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(4); v.push_back(4); for (size_t i = 0; i < v.size(); i++) { v[i]++; } for (auto e : v) { cout << e << " "; } cout << endl; Print(v); cout << endl; } void testvector3() { Sim::vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.insert(v.begin(), 10); v.insert(v.begin(), 10); v.insert(v.begin(), 10); v.insert(v.begin(), 10); v.insert(v.begin(), 10); for (auto e : v) { cout << e << " "; } cout << endl; //在第三个数据位置处进行插入多次数据 Sim::vector<int>::iterator pos = v.begin() + 2; pos = v.insert(pos, 222); pos = v.insert(pos, 333); for (auto e : v) { cout << e << " "; } cout << endl; } void testvector4() { Sim::vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.insert(v.begin(), 10); v.insert(v.begin(), 20); v.insert(v.begin(), 30); v.insert(v.begin(), 40); v.insert(v.begin(), 50); for (auto e : v) { cout << e << " "; } cout << endl; Sim::vector<int>::iterator pos = v.begin()+6; pos = v.erase(pos); pos = v.erase(pos); for (auto e : v) { cout << e << " "; } cout << endl; v.pop_back(); v.pop_back(); v.pop_back(); for (auto e : v) { cout << e << " "; } cout << endl; } void test() { int i = 0; int j = int(); int k = int(1); cout << "i=" << i << endl; cout << "j=" << j << endl; cout << "k=" << k << endl; } void testvector5() { Sim::vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.insert(v.begin(), 10); v.insert(v.begin(), 20); v.insert(v.begin(), 30); v.insert(v.begin(), 40); v.insert(v.begin(), 50); v.resize(10, 100); for (auto e : v) { cout << e << " "; } cout << endl; v.resize(5, 10); for (auto e : v) { cout << e << " "; } cout << endl; Sim::vector<int> v1(v); for (auto e : v1) { cout << e << " "; } cout << endl; auto v2 = v; for (auto e : v1) { cout << e << " "; } cout << endl; } void testvector6() { Sim::vector<string> v; v.push_back("1111"); v.push_back("2222"); v.push_back("3333"); v.push_back("4444"); v.push_back("5555"); Sim::vector<string> v1(v); for (auto e : v) { cout << e << " "; } cout << endl; } void testvector7() { Sim::vector<Sim::vector<int>> v; Sim::vector<int> vv; vv.push_back(1); v.push_back(vv); v.push_back(vv); v.push_back(vv); v.push_back(vv); v.push_back(vv); Sim::vector<Sim::vector<int>> v1(v); for (Sim::vector<int> e : v) { for (int c : e) { cout << c << " "; } cout << endl; } } void testvector8() { Sim::vector<int> v(10, 1); for (int e : v) { cout << e << " "; } cout << endl; Sim::vector<int> v1(v.begin(), v.end()); for (int e : v1) { cout << e << " "; } cout << endl; } int main() { testvector8(); return 0; }
好了，本期内容就到这里了
如果对你有帮助的话，不要忘记点赞加收藏哦！！！
