一、标准库中的vector类
1.1 vector类介绍
1.2 vector的常用接口
1.2.1 常用的构造函数
1.2.2 容量操作接口
（1）size
（2）capacity
（3）empty
（4）resize
（5）reserve
1.2.3 访问和遍历
（1）operator[]
（2）迭代器
（3）at
（4）back
（5）front
1.2.4 vector的增删查改
（1）push_back
（2）pop_back
（3）find
（4）insert
（5）erase
（6）swap
（7）assign
（8）clear
1.3 迭代器失效
二、模拟实现vector类
一、标准库中的vector类
1.1 vector类介绍
vector用于表示大小可以变化的数组。
与数组类似，vector也采用连续的存储空间来存储元素，也就是说我们可以和数组一样使用下标对vector进行随机访问。但是相对于不能改变空间大小的数组而言，vector的优势在于它的大小可以动态改变。
前面我们学习了string类，对于同样使用顺序表结构的vector类而言，二者的很多地方是相通的，例如vector也可以进行尾插和尾删等操作。
vector是一个模板类，在使用时我们需要给出元素的类型。
vector类中通常有三个迭代器类型的成员变量，分别指向vector的开头、最后一个有效元素的后一位和vector的结尾
iterator _start;iterator _finish;iterator _end_of_storage;
所以，vector的有效元素个数就等于_finish - _start，容量等于_end_of_storage - _start
我们通过vector类中的接口就能对这三个迭代器进行操作，从而完成增删查改等功能
在使用vector类时，必须包含头文件<vector>和using namespace std;
1.2 vector的常用接口
1.2.1 常用的构造函数
vector();
vector类的默认构造函数，构造一个没有元素的空容器
例如：
vector(size_type n, const value_type& val = value_type());
构造一个vector类对象并用n个val初始化
例如：
vector(const vector& x);
vector类的拷贝构造函数
例如：
Template<class InputIterator>
vector(InputIterator first, InputIterator last);
使用迭代器进行初始化构造
例如：
1.2.2 容量操作接口
（1）size
size_type size() const;
获取有效元素个数
例如：
（2）capacity
size_type capacity() const;
获取容量大小
例如：
（3）empty
bool empty() const;
判断容器是否为空
例如：
（4）resize
void resize(size_type n, value_type val = value_type());
将有效元素的个数修改为n，并且如果n大于原来的size，多出来的地方用val填充
如果没有给出val，就用0填充
例如：
（5）reserve
void reserve(size_type n);
改变容量大小
例如：
1.2.3 访问和遍历
（1）operator[]
reference operator[](size_type n);
const_reference operator[](size_type n) const;
用下标访问vector
例如：
（2）迭代器
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
迭代器，用于获取容器中第一个元素的位置和最后一个元素的下一个位置
例如：
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
反向迭代器，rbegin获取容器中最后一个元素的位置，rend获取容器中的第一个元素的前一个位置
例如：
需要注意，反向迭代器rit也要用++而不是--
（3）at
reference at(size_type n);
const_reference at(size_type n) const;
返回容器中位置n处的元素的引用
例如：
（4）back
reference back();
const_reference back() const;
返回容器中最后一个元素的引用
例如：
（5）front
reference front();
const_reference front() const;
返回容器中第一个元素的引用
例如：
1.2.4 vector的增删查改
（1）push_back
void push_back(const value_type& val);
从容器尾部插入一个元素
例如：
（2）pop_back
void pop_back();
从容器尾部删除一个元素
例如：
（3）find
template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& val);
在两个迭代器区间寻找val并返回其所在处的迭代器
例如：
需要注意的是，该函数并非vector的成员函数，是标准库中的函数，多个容器共用该find函数
（4）insert
iterator insert(iterator position, const value_type& val);
void insert(iterator position, size_type n, const value_type& val);
在position位置插入元素
例如：
对于这类可能会修改容量的函数，容易导致迭代器失效的问题，后面我们会详细讲
所以insert函数不仅需要完成插入元素的工作，有时还需要返回新的迭代器
（5）erase
iterator erase(iterator position);
iterator erase(iterator first, iterator last);
删除position位置的元素或者 [first，last) 区间的所有元素
例如：
（6）swap
void swap(vector& x);
交换两个vector的数据空间
例如：
（7）assign
template <class InputIterator>
void assign(InputIterator first, InputIterator last);
void assign(size_type n, const value_type& val);
为vector指定新内容，替换其当前内容并修改size
例如：
（8）clear
void clear();
从vector中删除所有元素，不改变容量大小
例如：
1.3 迭代器失效
迭代器的底层实际上就是一个指针或指针的封装，例如vector的迭代器就是一个原生态指针
当迭代器底层的指针指向的空间被销毁时，如果继续在程序中使用该迭代器，就会造成程序崩溃，这就是迭代器失效
对于vector，会导致迭代器失效的操作有：
可能造成空间改变的操作，如resize、reserve、insert、assign、push_back等以上函数在使用时都可能会导致vector扩容，在扩容时原空间会被释放，迭代器就会指向一块被释放的空间
删除操作假设有迭代器pos，使用pos删除pos对应位置的元素后，该迭代器对应的元素发生改变，属于迭代器失效
如果pos刚好对应最后一个元素，删除后迭代器pos就超出了有效元素范围，可能导致非法访问，属于迭代器失效
迭代器失效后，如果我们需要继续使用迭代器，给迭代器重新赋值即可
二、模拟实现vector类
知道了vector类中各种常用接口的用法后，我们就可以开始自己手撕一个自己的vector类了
为了不和标准库中的vector类冲突，我们可以开一个自己的命名空间
#include <iostream>#include <assert.h>#include <string>using namespace std;namespace Eristic{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;vector()//此处包括下面的初始化列表都可以换用缺省值:_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(n);for (size_t i = 0; i < n; ++i){push_back(val);}}vector(int n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(n);for (int i = 0; i < n; ++i){push_back(val);}}vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(v.capacity());for (size_t i = 0; i < v.size(); ++i){_start[i] = v._start[i];}_finish = _start + v.size();}template <class InputIterator>vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){while (first != last){push_back(*first);++first;}}vector<T>& operator=(vector<T>& v){if (this != &v){reserve(v.capacity());for (size_t i = 0; i < v.size(); ++i){_start[i] = v._start[i];}_finish = _start + v.size();return *this;}}iterator begin(){return _start;}const_iterator cbegin() const{return _start;}iterator end(){return _finish;}const_iterator cend() const{return _finish;}size_t capacity() const{return _end_of_storage - _start;}size_t size() const{return _finish - _start;}void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];size_t sz = size();if (_start){for (size_t i = 0; i < sz; ++i){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}}void resize(size_t n, T val = T()){if (n < size()){_finish = _start + n;}if (n > size()){if (n > capacity())reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}}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;}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}iterator insert(iterator pos, const T& val){assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){size_t range = pos - _start; //在扩容前需要记录相对位置//在插入数据时发生了扩容，迭代器的位置会发生改变,叫做迭代器失效reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + range; //将pos也更新到新的位置}iterator end = _finish;while (end > pos){*end = *(end - 1);--end;}*pos = val;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator start = pos + 1;while (start < _finish){*(start - 1) = *start;++start;}--_finish;return pos;}T& front(){return *_start;}const T& front() const{return *_start;}T& back(){return *(_finish - 1);}const T& back() const{return *(_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];}~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}private:iterator _start;iterator _finish;iterator _end_of_storage;};}如有错误，欢迎在评论区指出
完.