STL？vector！！！
一、前言
之前我们借助手撕string加深了类和对象相关知识，今天我们将一起手撕一个vector，继续深化类和对象、动态内存管理、模板的相关知识
二、vector相关的前置知识
1、什么是vector？
vector是一个STL库中提供的类模板，它是存储元素对象的顺序表，其中提供了一些有关增删查改的接口，它的特点是可以通过下标的方式在表中的任意位置进行读、写
2、vector中的相关接口
在本文接下来的部分会介绍vector的常用接口，事实上借助这些接口就可以解决平常所能遇到的大部分问题，如果还需要了解vector提供的更多接口及使用方法的话，可以跳转到一下网页：
vector - C++ Referencehttps://legacy.cplusplus.com/reference/vector/vector/?kw=vector
三、手撕一个vector类
1、成员变量与整体框架
注意：之前的顺序表我们都是通过记录指针、元素个数和空间大小来完成的，顺序表的实现自然也可以这样，但是STL库中不是这样实现的，所以今天我们学习一下STL库中的实现方式
上面的_start、_finish、_endofstorge分别代表着指向有效元素起始位置、终止位置的下一个位置和空间终止位置的迭代器，所以在上面我们已经定义了迭代器，事实上就是指针类型，这是由于顺序表的一大特点就是在内存中连续存储，所以可以直接使用未封装的指针；另一方面，我们在声明成员变量的同时都给了一个缺省值，这是由于它们都是指针类型，在初始化时我们都要先初始化成空指针再进行下一步操作，所以我们可以直接在这里给一个缺省值，这样避免了在初始化列表多次的显示初始化成空指针
2、构造函数
库中的函数头：
以上的三个构造函数我们都会一一实现，在这里补充一点：在上面的构造函数中出现了"clloc"，事实上，这是一个内存池，而后面所给的缺省值是STL库中提供的一个默认的内存池，它可以有效的提高开辟空间的时间消耗，但是比较复杂，所以在这里我们直接new空间，在之后，我们会专门的进行讲解
(1).空构造：
在这里实现的空构造是非常简单的，这是由于我们在声明时已经给了缺省值，但是该空构造是一定要写的，这是因为我们还要实现别的构造函数，这时候编译器就不在自动生成默认构造函数了
(2).用n个元素对象进行初始化：
在使用n个元素对象进行初始化时，我们在参数部分给了一个缺省值T()，很明显，这是一个匿名对象，同时调用了对应的默认构造函数，这是没有问题的，但是如果T是int、float等内置类型呢？事实上，这点不用担心，这是由于C++将这些内置类型都进行了升级，使它们可以象自定义类型一样调用默认构造函数，举个例子：如果T是int类型，那么此时T()就会返沪一个0进行初始化
(3).使用一个迭代器区间进行初始化：
在上面的构造函数中，我们再次使用了模板，但这里是函数模板，这是由于我们不仅要支持顺序表的迭代器类型初始化，还要支持其它类型的迭代器初始化
3、返回顺序表一些性质的函数
(1).size函数：返回此时vector中的元素个数
库中的函数头：
实现：
(2).capacity函数：返回此时vector中的空间大小
库中的函数头：
实现：
4、拷贝构造函数
库中的函数头：
实现：
这里需要注意：我们不可以使用memcpy，这是由于memcpy会按字节将x的内容拷贝到_start，但如果T类型是动态开辟内存，也就是说是深拷贝的话，那么虽然vector整体进行了深拷贝，但是vector中的内容却只完成了浅拷贝，会出现深浅拷贝的问题，此时选择上面的方式就万无一失了，这要求元素对象重载了赋值运算符，这一点是必须的
5、迭代器相关函数
(1).begin函数：
库中的函数头：
begin函数进行了两个重载，分别是普通begin和const begin它们分别可以返回一个可读可写的迭代器和一个只读不写的迭代器，都指向vector的首元素位置：
(2).end函数:
库中的函数头：
end函数仍然进行了两个重载，返回的迭代器都指向末尾元素的下一个位置：
6、[]操作符重载
库中的函数头：
库中对[]操作符进行了两个重载，与上面的begin类似：
库中对于很多类型进行了封装，事实上上面我们实现的与库中的本质是一样的
7、交换函数
库中的函数头：
这里的交换一定是要涉及深拷贝的，在这里我们借用一下算法库中的swap函数，因为它恰好就是深拷贝：
8、赋值运算符重载
库中的函数头：
在这里我们对该函数实现进行一点小改动，但是对于用户的使用来说是相同的：
在上面的实现中，我们采用了传值传参，此时形参是实参的拷贝，拷贝会调用我们之前实现过的拷贝构造函数进行深拷贝，再调用swap函数，它也会进行深拷贝之下的交换，最终*this就变成了x的拷贝，最后x这一拷贝出作用域销毁，调用析构函数(后面会实现)，进行了空间的释放
9、开空间相关函数
(1).reserve函数：会开辟指定大小的空间，如果原来有元素，会进行拷贝，否则不进行任何处理
库中的函数头:
实现：
在上面我们又遇到了象拷贝构造函数同样的问题，所以再次使用了赋值运算符重载的方式进行处理
(2).resize函数：会开辟指定大小的空间，用val进行初始化，缺省值为T()
库中的函数头：
实现:
这里我们直接对之前的函数进行复用即可
10、插入相关函数
(1).insert函数：在迭代器指定的位置直接插入一个值，返回最后该位置的迭代器
库中的函数头：
实现：
从上面的代码可以看出：在insert函数内部可能开辟空间，这时候pos就不是原来的pos了，所以在函数外部，传给过insert函数的迭代器是不能再次使用的，因为使用过的迭代器可能已经失效，这时候我们通过反回值的方式解决了这个问题，所以如果想再次使用的话，要接受函数的返回值
(2).push_back函数：在vector尾部插入一个对象
库中的函数头：
实现：
事实上在这个位置我们直接复用刚才写过的insert就非常方便
11、删除相关函数
(1).erase函数：删除迭代器指定位置的元素，返回该位置的迭代器
库中的函数头：
实现：
erase所删除的位置有可能是最后一个，此时删除之后传入的迭代器·就失效了，所以要接收返回值并判断
(2).pop_back函数
库中的函数头：
实现：
直接复用刚才写过的erase函数即可
12、析构函数
由于析构函数的特殊性，这里就不提供库中的函数头了：
四、vector
下面就是我们今天一起完成的vector了：
#include <iostream> #include <cassert> #include <algorithm> using namespace std; namespace bea { template<class T> class vector { typedef T* iterator; typedef const T* const_iterator; public: //空构造 vector() {} //用n个元素对象进行初始化 vector(size_t n, const T& val = T()) { _start = new T[n + 5]; for (size_t i = 0; i < n; i++) { _start[i] = val; } _finish = _start + n; _endofstorge = _start + n + 4; } //使用一个迭代器区间进行初始化 template<class InputIterator> vector(InputIterator first, InputIterator last) { size_t n = last - first; _start = new T[n + 5]; InputIterator it1 = first, it2 = _start; while (it1 < last) { *it2 = *it1; it1++, it2++; } _finish = _start + n; _endofstorge = _start + n + 4; } //拷贝构造函数 vector(const vector& x) { size_t sz = x.size(); _start = new T[sz + 5]; for (size_t i = 0; i < sz; i++) { _start[i] = x._start[i]; } _finish = _start + sz; _endofstorge = _start + sz + 4; } //size函数 size_t size() const { return _finish - _start; } //capacity函数 size_t capacity() const { return _endofstorge - _start + 1; } //begin函数 iterator begin() { return _start; } const_iterator begin() const { return _start; } //end函数 iterator end() { return _finish; } const_iterator end() const { return _finish; } //[]操作符重载 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 swap(vector& x) { std::swap(x._start, _start); std::swap(x._finish, _finish); std::swap(x._endofstorge, _endofstorge); } //赋值运算符重载 vector& operator=(const vector x) { swap(x); return *this; } //开空间相关函数 void reserve(size_t n) { size_t sz = size(); if (n <= size()) return; iterator tmp = new T[n + 5]; if (_start) { for (size_t i = 0; i < sz; i++) { tmp[i] = _start[i]; } delete[] _start; } _finish = tmp + sz; _start = tmp; _endofstorge = tmp + n + 4; } //insert函数 iterator insert(iterator pos, const T& val) { assert(pos <= _finish); int n = pos - _start; if (capacity() < size() + 1) { reserve(size() + 5); } pos = _start + n; iterator end = _finish - 1, next = _finish; while (next > pos) { *next = *end; end--, next--; } *pos = val; _finish++; return pos; } void push_back(const T& val) { insert(_finish, val); } void resize(size_t n, T& val = T()) { vector(n, val); } //erase函数 iterator erase(iterator pos) { assert(pos < _finish); iterator end = pos + 1, front = pos; while (end < _finish) { *front = *end; front++, end++; } _finish--; if (pos == _finish) return nullptr; else return pos; } //pop_back函数 void pop_back() { erase(_finish - 1); } //析构函数 ~vector() { delete[] _start; _start = nullptr; _finish = nullptr; _endofstorge = nullptr; } private: iterator _start = nullptr; iterator _finish = nullptr; iterator _endofstorge = nullptr; }; } 五、结语
这就是我们所实现的vector的全部内容了，我们的目的仍然是了解vector的用法、加深类和对象和模板等知识点的理解，感谢大家的阅读，欢迎各位于晏、亦菲和我一起交流、学习、进步！
