vector
1. 序列式容器
vector、list、deque、forward_list(C++11)等STL容器，其底层为线性序列的数据结构，里面存储的是元素本身，这样的容器被统称为序列式容器。
2. vector容器
vector使用模板作为参数，所以在使用的时候必须将模板实例化，否则编译器无法识别你写的对象是什么类型。
必须实例化模板
C++11 支持了一种特殊的赋值方式，编译器是通过把{}识别成了std::initializer_list类模板来实现的。
这种赋值方式对一般的内置类型也适用：
但这种赋值方式使用不多（因为太不c++了）
3. vector的成员函数
3.1 vector的成员函数介绍
1. vector的构造函数
| 函数声明 | 功能介绍 |
|---|---|
| vector< T > v() | 构造一个空的vector |
| vector< T > v(n,val) | 构造一个内容为n个val的vector |
| vector< T > v (v1.iterator1(),v1.iterator2()) | 构造一个从v1的iterator1到iterator2的vector |
| vector< T >v(v1) | 拷贝构造一个v1的vector |
2. vector的迭代器
| 函数名 | 功能介绍 |
|---|---|
| begin和end | begin:首元素的位置；end：下一个元素的位置 |
| rbegin和rend | c指const，cbegin和cend指向的内容不能修改 |
| cbegin和cend | 反向迭代器，rbegin从end开始，rend从begin开始，其++和–的方向相反 |
| crbegin和crend | 与前一个功能相同，但指向的内容不能修改 |
3.vector的容量与元素访问
| 函数名 | 函数声明 | 功能介绍 |
|---|---|---|
| size | size_type size() const | 返回vector中有效元素个数 |
| resize | void resize (size_type n, value_type val = value_type()) | 如果n小于size，则缩小vector到n个有效元素（大于n的位置的元素被删除）；如果n大于size，则增大vector到n，大于size的部分用val填补（无参则补val的默认构造） |
| capacity | size_type capacity() const | 返回vector开设的空间的元素大小（注意是以元素而不是字节计数） |
| reserve | void reserve (size_type n) | 将vector的空间增大到n个有效元素的大小，如果n小于size则无效 |
| operator[] | reference operator[] (size_type n) | 返回指向vector第n个位置的迭代器 |
4. vector的修改
| 函数名 | 函数声明 | 功能介绍 |
|---|---|---|
| push_back | void push_back (const value_type& val) | 尾插元素（vector只支持单个数据的尾插） |
| pop_back | void pop_back() | 尾删元素 |
| insert | iterator insert (iterator position, const value_type& val) void insert (iterator position, size_type n, const value_type& val) | 在pos位置插入一个元素 在pos位置插入n个元素 |
| erase | iterator erase (iterator position) iterator erase (iterator first, iterator last) | 删除pos位置的元素 删除first位置到last位置的元素 |
3.2 vector的resize
resize在不传val参数时会使用缺省值，但是对于不同类型的数据，其缺省值也应用不同的值，resize是怎么实现的呢？
void resize (size_type n, value_type val = value_type())
resize通过调用实例化的模板的默认构造来实现传递不同的缺省值，但如果模板实例化的类型不是自定义类型而是内置类型呢？
实际上，c++的内置类型也有默认构造：
int main()
{int i = int();float f = float();double d = double();char c = char();return 0;
}
这使得内置类型和自定义类型都能使用模板的缺省值传参。
3.3 二维vector与二维数组的异同
创建一个二维数组和一个二维vector，它们的访问方式都是一模一样的:
int n[i][j];
vector<vector<int>> n;
n[i][j]
但它们实现的原理不同：
二维数组的访问的底层是靠指针的解引用实现的，而二维vector的访问的底层是通过函数调用实现的
4. 复现vector
4.1 填充构造函数和范围构造函数的冲突
vector实例化为int类型时，使用这种初始化方式会导致以下两种构造函数都使用，但第一种更匹配。导致错误调用了本不该调用的构造函数。
两个构造函数的重载冲突造成了编译错误。
这种错误类型只针对int类型，size_t类型都不会有相同的冲突。因此解决方法很简单，只需要专门为 int 类型写一个重载的 fill 构造函数即可：
4.2 扩容导致的隐含浅拷贝问题
vector的reserve()在扩容时，不能使用memcpy()交换新旧空间的指针，因为当vector实例化为string类时，string会浅拷贝。在释放旧的空间后，新的空间也会一同释放，造成越界访问的错误。
解决方法很简单，只需要把旧空间的内容一个一个拷贝到新的空间即可：
4.3 扩容和删除导致迭代器失效问题
迭代器失效是迭代器指向的元素或空间发生了变化，导致迭代器不再指向预期的元素或变得无效。
扩容：
insert()函数在一般的确定类型的数据结构中，pos一般都是一个整型，但由于vector支持多类型的数据，所以vector的pos是一个迭代器类型(iterator)，而iterator是一个模板的指针。即pos也是一个模板的指针，这使得在扩容等操作时，如果没有对pos以iterator的形式操作，导致它失效。
当扩容时，底层调用
malloc()，当前方没有足够的空间原地扩容时，malloc()会另找一块足够大的空间，将原数据拷贝过去，那么此时的 pos 是一个模板指针类型，如果不对其进行更新，就会变成野指针。
删除：
vector的 erase() 在 STL 中不允许迭代器在调用函数后继续使用迭代器，因为在以下场景会产生问题。
这是一个删除 vector<int> 类型里的所有偶数的代码：
int main()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);vector<int>::iterator it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){v1.erase(it);}++it;}for (auto e : v1){std::cout << e << " ";}return 0;
}
它能够正常运行，但当 vector 里的数据有两个偶数相连，或两个相连的偶数在最后的位置时：
vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(4);v1.push_back(5);
//或
vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);v1.push_back(6);
两种情况：一种是结果有问题，而另一种直接造成了程序的崩溃
查阅stl库里的vecotr的erase()函数可以看到，这个函数有一个返回值，并且它的返回值是迭代器：
所以官方实际上是通过直接更新迭代器来避开这个问题的，重构代码和删除的写法如下：
4.4 完整代码
#pragma once
#include<iostream>
#include<assert.h>namespace myvector
{template <class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}//defaultvector(){}//fillvector(size_t n, const T& val = T()){reserve(n);for (int 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);}}//rangetemplate<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++_finish;}}//initializer list c++11支持vector(std::initializer_list<T> il){reserve(il.size());for (auto& e : il){push_back(e);}}//copyvector(const T& v){reserve(v.size());for (auto& e : v){push_back(e);}}~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}void reserve(size_t n){if(n>capacity()){T* temp = new T[n];size_t old_size = size();//使用memcpy会引发隐含浅拷贝for (size_t i = 0; i < old_size; i++){temp[i] = _start[i];}delete[] _start;_start = temp;_finish =temp+old_size;_endofstorage = temp + n;}}void push_back(const T& val){insert(end(), val);}void pop_back(){erase(end() - 1);}void insert(iterator pos, const T& val)//vector只支持单数据插入{assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage){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 = val;++_finish;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;++it;}--_finish;return pos;//返回删除的下一个（更新后）的位置}void swap(vector<T>& v){std::swap(_start,v._start);std::swap(_finish,v._finish);std::swap(_endofstorage,v._endofstorage);}size_t capacity() const{return _endofstorage - _start;}size_t size() const{return _finish - _start;}void resize(size_t n, const T& val = T()){if (n > size()){reserve(n);while (_finish < _start + n){*_finish = val;++_finish;}}else{_finish = _start + n;}}bool empty(){return _start == _finish;}vector<T>& operator=(vector<T> v){swap(v);return *this;}T& operator[](size_t pos){assert(pos <= size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos <= size());return _start[pos];}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};
}
