C++初阶-vector的模拟实现2
目录
1.vector已经实现的代码总结
2.vector::resize的模拟实现
3.vector::vector(const vector& v)拷贝构造函数的模拟实现
4.vector::operator=(const vector& x)的模拟实现（原始写法）
5.vector::swap的模拟实现
6.vector::operator=(const vector& x)的模拟实现（现代写法）
7.问题分析
vector::vector()的最终实现
8.问题分析
vector::reserve最终实现
9.总结
1.vector已经实现的代码总结
如果不想看得话可以直接跳到第2个vector::resize的模拟实现去。
#include<iostream>
#include<vector>
#include<string>
#include<assert.h>
using namespace std;
//防止命名冲突，用一个命名空间域进行分隔
namespace td
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//无参的构造函数的实现vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}//析构函数的实现~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}//size()函数的实现size_t size() const{return _finish - _start;}//capacity()函数的实现size_t capacity() const{return _end_of_storage - _start;}//普通版本的begin()函数的实现iterator begin(){return _start;}//普通版本的end()函数的实现iterator end(){return _finish;}//empty函数的实现bool empty() const{return begin() == end();}//push_back的实现void push_back(const T& x){if (_finish == _end_of_storage){//先扩容//如果没有空间，就初始化为4//否则二倍扩容reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}//reserve函数的实现2void reserve(size_t n){if (n > capacity()){//开辟新空间T* tmp = new T[n];//拷贝数据memcpy(tmp, _start, sizeof(T) * size());//释放空间delete[] _start;_finish = tmp + size();_start = tmp;_end_of_storage = _start + n;}}//普通operator[]的实现T& operator[](size_t i){//需包含头文件：assert.hassert(i < size());return _start[i];}//const的operator[]的实现const T& operator[](size_t i) const{assert(i < size());return _start[i];}//const版本的begin的实现const_iterator begin() const{return _start;}//const版本的end的实现const_iterator end() const{return _finish;}//pop_back函数的实现void pop_back(){assert(_finish > _start);--_finish;}//erase函数的模拟实现void erase(iterator pos){assert(pos >= _start);assert(pos <= _finish);if (pos == _finish){pop_back();return;}iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;++it;}--_finish;}//insert函数的实现2void insert(iterator pos, const T& x){//判断是否合法assert(pos >= _start);assert(pos <= _finish);//判满if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator it = _finish - 1;//移动数据while (it >= pos){*(it + 1) = *it;--it;}*pos = x;++_finish;}private:iterator _start;iterator _finish;iterator _end_of_storage;};void test(){}
}2.vector::resize的模拟实现
这个函数就是把size和capaciay根据情况改变大小，并且可能删除数据。也可能添加数据，也可能扩容等等。这里简单分析一下：
（这里是用之前的capacity和size进行讲解的，而不是现在模拟实现vector的方式来进行讲解的） 若capacity开始为20，size开始为10，那么resize可能会有三种情况： 若resize（5），则删除后5个数据，保留前5个数据； 若resize（15），则插入5个数据（插入第二个参数）； 若resize（25），则插入15个数据，并扩容至25个T大小的空间。
所以我们通过了解这个函数的功能后可以写出代码：
//resize函数的实现
void resize(size_t n, const T& val = T())
{if (n < size()){//删除但不释放空间_finish = _start + n;}else {//reserve会帮我们检查是否要扩容reserve(n);//插入数据至_start+n(即一共到达n个数据)while (_finish != _start + n){*_finish = val;++_finish;}}
}而这个函数主要还是用来开辟一段空间并进行初始化的操作。
我们来测试一下这个函数有没有问题：
void test()
{vector<int> a;cout << a.size() << endl;cout << a.capacity() << endl;a.resize(10);cout << a.size() << endl;cout << a.capacity() << endl;for (const auto& e : a){cout << e << " ";}cout << endl;a.resize(5);cout << a.size() << endl;cout << a.capacity() << endl;for (const auto& e : a){cout << e << " ";}cout << endl;a.resize(15);cout << a.size() << endl;cout << a.capacity() << endl;for (const auto& e : a){cout << e << " ";}cout << endl;
}那么函数的运行结果为：
测试发现针对每个情况都没有问题！
3.vector::vector(const vector<T>& v)拷贝构造函数的模拟实现
这个函数是拷贝构造函数，要实现它我们可以通过先进行扩容至与v相同的大小（准确来说是v存储数据的大小），最后再用循环进行尾插即可：
//拷贝构造函数的模拟实现
vector(const vector<T>& v)
{reserve(v.size());for (auto& e : v){push_back(e);}
}我们来测试一下这个函数：
void test()
{vector<int> a;a.push_back(1);a.push_back(3);a.push_back(6);a.push_back(4);a.push_back(8);vector<int> b(a);for (const auto& c : a){cout << c << " ";}cout << endl;for (const auto& c : b){cout << c << " ";}cout << endl;
}那么运行结果为：
则代码没有问题。
4.vector::operator=(const vector<T>& x)的模拟实现（原始写法）
这个函数和拷贝构造函数的实现差不多，只是我们需要注意：我们需要先判断是否存在自己给自己赋值的情况，然后再进行释放旧空间，拷贝x的各个数据到对象里面去，这样就可以了，所以最终实现如下：
//vector::operator=的实现
//也可以写为如下形式：
//vector<T>& operator=(const vector& x)
vector<T>& operator=(const vector<T>& x)
{if (this != &x){delete[] _start;_start = _finish = _end_of_storage = nullptr;reserve(x.size());for (auto& e : x){push_back(e);}}return *this;
}我们来测试一下该函数：
void test()
{vector<int> a;a.push_back(3);a.push_back(5);a.push_back(4);a.push_back(9);a.push_back(0);vector<int> b;b = a;for (const auto& c : a){cout << c << " ";}cout << endl;for (const auto& c : b){cout << c << " ";}cout << endl;
}那么运行结果为：
测试结果没有问题。不过这是一个实现比较麻烦的版本，有现代版本会在swap函数实现后给出。
5.vector::swap的模拟实现
这个函数实现比较简单，只要完成三个数据的交换，我们可以直接用算法库里面的swap完成该功能：
//swap函数的模拟实现
void swap(vector<T>& v)
{//一定要指定类域，否则会从自己这个域里面找std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}我们测试一下这个函数：
void test()
{vector<int> a;a.push_back(3);a.push_back(5);a.push_back(1);a.push_back(8);a.push_back(7);cout << "a交换之前:";for (const auto& v : a){cout << v << " ";}cout << endl;vector<int> b;b.push_back(4);b.push_back(7);b.push_back(6);cout << "b交换之前:";for (const auto& v : b){cout << v << " ";}cout << endl;a.swap(b);cout << "a交换之后:";for (const auto& v : a){cout << v << " ";}cout << endl;cout << "b交换之后:";for (const auto& v : b){cout << v << " ";}cout << endl;
}那么运行结果为：
6.vector::operator=(const vector<T>& x)的模拟实现（现代写法）
我们实现了swap函数后我们可以通过swap来进行现代写法，因为我们都是拷贝，所以我们可以通过这个函数来实现：
//现代写法
//不能加const因为是要改变的
vector<T>& operator=(vector<T> x)
{//由于x是形参，x的改变不会影响实参，所以可以直接交换！swap(x);return *this;
}7.问题分析
我们如果写了以下程序，那么结果会怎么样呢（用现代写法和传统写法实现的=结果都一样）？
void test()
{vector<int> v1;vector<int> v2;v2.resize(100, 1);v1 = v2;for (const auto& e : v2){cout << e << " ";}cout << endl;
}那么运行结果为：
我们发现程序会崩溃，所以肯定是resize或者=有问题，但是我们测试了两个函数好像都没有问题啊！
这里就不将调试所有的过程演示了，原因是：
在v1=v2这个东西时会先执行拷贝构造，而拷贝构造有reserve,而这个reserve使_start、_finish、_end_of_storage置为随机值了。
可能有些人不信，那我们调试一下即可：
通过一系列调试，我们可以知道，一定是_finish在进行reserve操作后_finish不知道出了什么问题变为nullptr了，然后空指针解引用导致出现问题。
难道是reserve有问题。但是压根，没有调用reserve啊。
真实原因是：reserve使_start、_finish、_end_of_storage置为随机值了，然后访问不到数据，之后还要调用构造函数（operator=函数调用时）。
实际上我们需要在定义中改为：
private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;这样就没问题了，不过想深究的可以自行调试，因为我自己也没有调试出来什么问题。
那么这样改变后运行结果为：
vector::vector()的最终实现
不过这样无参的构造就可以直接改为：
//无参的构造函数的实现
vector()
{}8.问题分析
我们运行一下这个程序：
void test()
{vector<string> v1;//插入数据大于16个，防止它存放到buff数组里面了v1.push_back("11111111111111111111111111111111111111");v1.push_back("11111111111111111111111111111111111111");v1.push_back("11111111111111111111111111111111111111");v1.push_back("11111111111111111111111111111111111111");//再加一个就会有问题//v1.push_back("11111111111111111111111111111111111111");for (const auto& e : v1){cout << e << " ";}cout << endl;
}那么这个程序最终运行结果为：
但是如果我们再添加一个push_back会怎么样？
void test()
{vector<string> v1;//插入数据大于16个，防止它存放到buff数组里面了v1.push_back("11111111111111111111111111111111111111");v1.push_back("11111111111111111111111111111111111111");v1.push_back("11111111111111111111111111111111111111");v1.push_back("11111111111111111111111111111111111111");//再加一个就会有问题v1.push_back("11111111111111111111111111111111111111");for (const auto& e : v1){cout << e << " ";}cout << endl;
}那么运行结果会改为：
也就是说前面所存放的数据都改变了！为什么？
我们可以分析一下，这肯定是在第5次尾插时就扩容了，也就是说一定是reserve的问题，那我们通过调试来发现一下问题：
也就是说压根没有吧数据完全拷贝过去，所以这里的问题是memcpy的问题，而这个问题我们根本不能注意到，也发现不了，所以我们很容易出错，所以我们应该优化拷贝数据的问题，感兴趣的可以看完我的分析：
之前我们在C语言实现过memcpy（这个我没有写博客，需要自己去搜其他博主的博客），我们发现它是一个一个字节的拷贝数据，意味着把string对象的每一个字节一次拷贝过去，哪怕它有buff,如果数据存在指向的空间，它也会把这个空间也拷贝过去，也就是说，tmp的地址是_start地址拷贝过来的，也就是说如果释放了_start的空间，我们也相当于释放了原来存储的数据的空间。
这也相当于memcpy是我们平常说的浅拷贝，最终会使tmp和原来的_start指向同一块空间。这个也是比较容易忽略的点！
所以我们可以改为如下形式：
vector::reserve最终实现
//reserve函数的最终实现
void reserve(size_t n)
{if (n > capacity()){size_t oldSize = size();//开辟新空间T* tmp = new T[n];//拷贝数据for (size_t i = 0; i < oldSize; i++){tmp[i] = _start[i];}//释放空间delete[] _start;_finish = tmp + oldSize;_start = tmp;_end_of_storage = _start + n;}
}那么这样的运行结果为：
9.总结
该讲基本上把vector的函数实现了，不过vector还有一个比较重要的知识：initializer_list，以及我们之前还没实现的另外两种构造函数，这两个知识点比较重要，也是C++11才更新的内容，现在讲了对之后也比较友好，而且之后用得比较多。好了这一讲就到这里了，喜欢的可以一键三连哦，下讲再见！
