[C++]vector（超详细）
在学习完了string后，我们来学习新的STL容器vector，是真正的属于STL中的一员，vector也是STL的基础容器，英文释义是向量，其实实质上就是顺序表。
在这个部分我们会学习的非常快，第一个原因是由于vector的设计更加简单，第二个原因是因为string和vector都是数组类型的，我们学会了string，这个就信手拈来了。
模拟实现代码放到文章尾部
目录
vector的使用
vector的标准成员函数
vector的构造函数
析构函数
赋值重载
vector的基本操作
vector的遍历
reserve
resize
insert
erase编辑
swap编辑
vector>
vector的模拟实现
析构函数
编辑
拷贝构造
赋值重载
编辑
编辑 迭代器构造
基本的函数
reserve
push_back
pop_back
insert
迭代器失效
erase
迭代器部分
resize
vector的使用
vector的标准成员函数
vector的构造函数
构造函数比较简单，就有四种构造方法，默认构造（无参构造），带参构造，迭代器区间构造，拷贝构造。
如图所示，为默认构造，带参构造，和迭代器区间构造，以及拷贝构造。
析构函数
析构函数会帮我们自动释放空间，也并不复杂
赋值重载
赋值重载也只有一个函数，也并不复杂
我们由此可以对比string，vector是非常简单的一个容器，它的接口也简洁了很多，不会像之前string那样复杂
不过vector是一个标准的模板
第一个模板参数就是vector所要存储的类型，第二个模板参数是一个空间配置器，内存池，在这个部分内，我们不用关系内存池是什么，也不需要显示传递，我们就大概理解，内存池就是和new，malloc一样的，可以获取内存，但是可以提高效率
使用vector，我们要加头文件<vector>
vector的基本操作
相比于string，vector里没有length，只有size，这也使容器变得简洁。
由于很多接口与string的用法类似，我们这里介绍方法会简洁一些
vector的遍历
我们和之前一样三种方法进行遍历
第一种用operate[]直接访问元素
第二章用迭代器，第三种用范围for
当用范围for遍历的时候，我建议带上引用&，因为如果vector数据很长，那就会一直拷贝，效率很低，而带上&就可以解决这个问题
reserve
我们用一段代码来看一下，vector的扩容规律是否与string类似
在VS中的扩容如下，可以看到扩容，大概还是1.5倍扩容，但是有些地方做了特殊处理，向上取整。
我们再在g++中编译这个代码，看看扩容情况
可以看到在g++编译后，是按标准2倍进行扩容的
我们看到reserve中，大致与string的reserve相同，编译器会给vector对象开辟n的空间，但是实际上会开辟比n大的空间
但这里有一点，与string不同
在string里，由于string开辟的空间是不具有约束力的，因此当传入的参数比实际空间小，会取决于编译器进行缩容。（在vs中不缩容，在g++下进行缩容）
而在vector中，vector开辟的空间，在任何情况下是不会缩容的
如下代码所示，VS情况下不缩容
如下所示，为g++编译环境，也不会发生缩容
按照道理来说，内存一般也不应该发生缩容
开辟的一段空间，一般都是从首地址进行释放，将空间全部释放，不应该发生从中间释放空间的情形。
resize
resize在string内也是有这个接口的，但是使用的并不多，但是在vector中，resize会被经常调用
resize会把contains数据个数扩到N，那么这里就有三种情况
关于插入的数据，如果你传值了就按数据就按照传入的值插入，如果没有传入值，那就会调用对应的默认构造对数据进行初始化
vector直接提供了尾插和尾删，但是没有提供头插头删，如果你要使用头插头删就必须使用insert
insert
比起string的insert，这里的设计就简洁了很多，不至于搞一些花里胡哨的
但是这里不支持下标插入了，只是支持迭代器，不够如果想在特点位置插入元素，只需要用迭代器
it+pos即可，毕竟迭代器支持基本运算的
erase
erase也是不支持下标删除，但是支持迭代器删除 ，所以效果与insert也一样
swap
swap的作用就是，防止我们自己使用swap，降低效率，因此提供了专门的接口
以上就是一些重要的接口，对于STL，我们可以在实践过程中，用到的时候再去查阅资料学习即可
vector不支持流插入和流提取，由于string只需要按照顺序打印，遇到\0停止即可，所以有特定的格式，但是vector具有太多的不确定性，因此不支持。但如果我们想自己实现，也很容易，因此我们可以根据我们的需要，自己实现。
这里有一个问题，因为都是顺序表，能否用vector<char>替代string呢？
其中一个重大区别就是'\0'的区别，vector没有'\0'，而string有'\0'，因此string可以很好的兼容C，而vector不行，你可能会想那我在后面加上'\0'不就可以了吗？
那么问题又来了，你是在char类型下加'\0'，那在int，double情况下，你的'\0'是什么意思。
因此string要单独拿出来，它有很大的意义。
vector<vector<int>>
vector<vector<int>>实际上就和我们二维数组一样，我们从大概从底层的角度来描述一下，存储结构，如图所示
用operate[]来访问
vector的模拟实现
我们先看一下库里vector的源码
库里面很喜欢用typedef，把一些类型变成iterator
我们不去关心复杂的源码，我们从入门的来理解
我们可以根据之前的经验，以及图中成员变量的名字，来猜测一下这三个变量代表什么
我们可以通过底层源码的其他函数，来反向推导这三个变量的含义，有兴趣的可以自己去推导一下
三个变量代表的含义如图所示
含义很简单，start就是数据的开头指针，finish是数据结束的位置，end_of_storage是存储位置的结尾。
我们这里仿照底层源码的方式来模拟实现vector
命名风格也和库里一致，这也是一种新的风格
析构函数
拷贝构造
我们这里的拷贝构造写的很有意思，直接将元素pushback进this对象中，直接使用写过的接口完成拷贝构造的实现。
由于 我们vector在写拷贝构造之前，不需要写默认构造，编译器会自动提供一个默认构造，但是当手动写拷贝构造后，编译器就不会给我们提供默认构造了，我们可以用C++11中的新语法，强制生成一份默认构造
赋值重载
传统写法
现代写法
迭代器构造
我们在类模板中，还可以再创建模板，不如迭代器构造
这样不但我们能用vector迭代器区间进行构造，我们还可以用链表对vector进行构造
基本的函数
size，capacity，我们直接用指针-指针的方式，就能求出来相应的值
而判空函数直接通过判断头指针是否等于尾指针即可。
operate[]重载，首先用断言检查是否越界，然后直接用下标返回对应的元素即可，不过要注意这里的返回值是引用类型，不然没法进行修改。
reserve
reserve函数还是之前那一套逻辑，判断n是否大于capacity，正常进行开辟新空间，拷贝数据，删除旧空间，指向新空间，修改变量值。
但是如果我们这样写就坑了，因为size = _finish-_start，由于我们已经修改了_start，size就不能再代表个数了，我们可以修改两个变量修改的先后顺序，但是先修改finish，再修改start，一点不符合逻辑，因此我们不如再添一个变量记录大小，这样也更清晰明了。
如果我们这样写的话 ，如果vector存的数据是指针类型（拷贝时需要深拷贝的类型）时，就会出现错误，原因是memcpy是浅拷贝，当浅拷贝完又delete[]原空间，就会导致新的tmp指向的是已释放的空间，因此我们需要换成深拷贝
push_back
尾插操作也是比较简单的，先判断是否需要扩容，需要就扩容，然后直接将数据放到尾部，++finish即可
pop_back
断言判断是否为空，然后直接--finish
insert
根据我们之前的经验，可以写出如下的代码
我们通过监视窗口，可以发现这个代码在扩容之前是正确的，但是在扩容之后，我们再运行插入逻辑，会发现程序挂掉了
我们发现，当end>=pos后，程序还在运行，说明while这里面有问题
这个问题就是经典的迭代器失效
迭代器失效
第一种情况，实质上就是野指针的情况
画个图，我们就很好理解了
那这个问题也很好解决，我们只需要记录 pos的相对位置，在扩容后，重新赋值即可
如图所示
第二种迭代器失效的情况
迭代器位置的意义已经变化了
由于数据的挪动，当前的迭代器已经改变了意义，也是一种迭代器失效的体现
在VS平台中，在实现operate*的部分，会进行强制的检查，如果发生了迭代器失效，会直接中止程序，规避风险。不过在g++的编译条件下并不会报错，但是这是非常危险的事情，因为当你迭代器失效后，你修改的是哪个数据，你也不清楚。因此，我们得出结论，在不同的平台下，关于迭代器失效的检查是不同的，我们在insert，erase 后就不要再访问迭代器，或者重新给迭代器赋值。
erase
erase的实现，首先assert判断pos位置是否合法，然后依次挪动数据，最后修改finish的值即可
由于erase删除元素后会迭代器失效，因此库里面提供的函数返回值，为删除元素的下一位元素，我们只需要将迭代器重新接收返回值即可。
迭代器部分
由于我们成员变量的定义，对于迭代器部分，非常简单，如下所示
resize
我们resize也要根据n的值和capacity和size的关系分成三种情况来实现
当n<size，我们直接删除数据到n
我们只需要修改_finish的值即可
当n>size，就是要插入数据，但是我们要进行检查扩容 。我们不管需不需要扩容，直接reserve，传入n，然后依次插入数据。
实现如下所示
平常我们使用resize都是用来初始化的。
以上就是vector的全部内容
下面是模拟实现的代码
namespace study
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
/*vector()
{}*/
// C++11 前置生成默认构造
vector() = default;
vector(const vector<T>& v)
{
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}
// 类模板的成员函数，还可以继续是函数模版
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
vector(int n, const T& val = T())
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
void clear()
{
_finish = _start;
}
// v1 = v3
/*vector<T>& operator=(const vector<T>& v)
{
if (this != &v)
{
clear();
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}
return *this;
}*/
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
// v1 = v3
//vector& operator=(vector v)
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
}
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t old_size = size();
T* tmp = new T[n];
//memcpy(tmp, _start, old_size * sizeof(T));
for (size_t i = 0; i < old_size; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
_finish = tmp + old_size;
_end_of_storage = tmp + n;
}
}
void resize(size_t n, T val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
}
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
bool empty() const
{
return _start == _finish;
}
void push_back(const T& x)
{
// 扩容
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;
}
void pop_back()
{
assert(!empty());
--_finish;
}
iterator 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 end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it != end())
{
*(it - 1) = *it;
++it;
}
--_finish;
}
T& operator[](size_t i)
{
assert(i < size());
return _start[i];
}
const T& operator[](size_t i) const
{
assert(i < size());
return _start[i];
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};