一、前言
之前我们借助手撕string加深了类和对象相关知识，今天我们将一起手撕一个vector，继续深化类和对象、动态内存管理、模板的相关知识
二、vector相关的前置知识
1、什么是vector？
vector是一个STL库中提供的类模板，它是存储元素对象的顺序表，其中提供了一些有关增删查改的接口，它的特点是可以通过下标的方式在表中的任意位置进行读、写
2、vector中的相关接口
在本文接下来的部分会介绍vector的常用接口，事实上借助这些接口就可以解决平常所能遇到的大部分问题，如果还需要了解vector提供的更多接口及使用方法的话，可以跳转到一下网页：
vector - C++ Reference
https://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的用法、加深类和对象和模板等知识点的理解，感谢大家的阅读，欢迎各位于晏、亦菲和我一起交流、学习、进步！