欢迎来到干货小仓库!!!
"每个warning都是编译器在说: 我觉得你还能强一点"
1.vector的成员变量定义
三个成员都定义成指针类型，因为指针 - 指针等于之间的个数。
2.vector的使用
2.1构造函数
| 构造函数声明 | 接口说明 |
| vector() | 无参构造 |
| vector（size_type n, const T& val = T()） | 构造并初始 n 个val |
| vector(const vector& x) | 拷贝构造 |
| vector(Inputiterator first,Inputiterator last) | 使用迭代器进行初始化 |
2.2vector iterator 迭代器的使用
| iterator的使用 | 接口说明 |
| begin + end | 获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置的iterator/const_iterator。 |
| rbegin + rend | 获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator。 |
2.3关于空间的函数
| 容量空间 | 接口说明 |
| size() | 获取数据个数 |
| capacity() | 获取容量大小 |
| empty() | 判断是否为空 |
| resize(size_t n) | 改变vector的size |
| reserve(size_t n) | 改变vector的capacity |
capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
resize在开空间的同时还会进行初始化，影响size。
2.4vector的增删查改
| 函数名称 | 接口说明 |
| push_back | 尾插 |
| pop_back | 尾删 |
| find | 查找。(注意这个是算法模块实现，不是vector的成员函数) |
| insert(size_t pos,T val) | 在pos之前插入val |
| erase(size_t pos) | 删除pos位置的数据 |
| swap | 交换两个vector的数据空间 |
| operator[] | 像数组访问一样 |
3.迭代器失效问题
迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。
导致迭代器失效的操作:
①会引起其底层空间改变的操作，都有可能是迭代器失效。比如:resize、reserve、insert、assign、push_back等。
#include <iostream>
using namespace std;
#include <vector>int main()
{vector<int> v{1,2,3,4,5,6};auto it = v.begin();// 将有效元素个数增加到100个，多出的位置使用8填充，操作期间底层会扩容// v.resize(100, 8);// reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变// v.reserve(100);// 插入元素期间，可能会引起扩容，而导致原空间被释放// v.insert(v.begin(), 0);// v.push_back(8);// 给vector重新赋值，可能会引起底层容量改变v.assign(100, 8);/*出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉，
而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的
空间，而引起代码运行时崩溃。解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it重新
赋值即可。*/while(it != v.end()){cout<< *it << " " ;++it;}cout<<endl;return 0;
}②指定位置元素的删除操作---erase
#include <iostream>
using namespace std;
#include <vector>
int main()
{int a[] = { 1, 2, 3, 4 };vector<int> v(a, a + sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvector<int>::iterator pos = find(v.begin(), v.end(), 3);// 删除pos位置的数据，导致pos迭代器失效。v.erase(pos);cout << *pos << endl; // 此处会导致非法访问return 0;
}erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。
示例:删除vector中的所有的偶数，以下那个代码是正确的？
#include <iostream>
using namespace std;
#include <vector>//代码一
int main()
{vector<int> v{ 1, 2, 3, 4 };auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)v.erase(it);++it;}return 0;
}//代码二
int main()
{vector<int> v{ 1, 2, 3, 4 };auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)it = v.erase(it);else++it;}return 0;
}代码二是正确的。
解析：
而代码二中的: it = v.erase(it) 会返回删除元素的下一个元素。
③注意:Linux下，g++编译器对迭代器失效的检测并不是非常的严格，处理也没有vs下严格。
④与vector类似，string在插入+扩容操作+erase之后，迭代器也会失效。
#include <string>
void TestString()
{string s("hello");auto it = s.begin();// 放开之后代码会崩溃，因为resize到20会string会进行扩容// 扩容之后，it指向之前旧空间已经被释放了，该迭代器就失效了// 后序打印时，再访问it指向的空间程序就会崩溃//s.resize(20, '!');while (it != s.end()){cout << *it;++it;}cout << endl;it = s.begin();while (it != s.end()){it = s.erase(it);// 按照下面方式写，运行时程序会崩溃，因为erase(it)之后// it位置的迭代器就失效了// s.erase(it); ++it;}
} 迭代器失效解决办法：在使用前，对迭代器重新赋值即可。
4.深度刨析vector模拟实现遇到的问题
拷贝构造
vector(const vector<T>& v)
{_start = new T[v.capacity()];memcpy(_start, v._start, sizeof(T) * v.size());_finish = _start + v.size();_endofstorage = _start + v.capacity();}//扩容
void reserve(size_t n)
{if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){memcpy(tmp, _start, sizeof(int) * size());delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}
}上述拷贝构造函数，当vector存的是内置类型是正常的。一旦vector存的是自定义类型时，例如vector<string>会出问题，由于memcpy导致的。
1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中。
2. 如果拷贝的是内置类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。
浅拷贝:
解决方式:
//拷贝函数
vector(const vector<T>& v)
{_start = new T[v.capacity()];//memcpy(_start, v._start, sizeof(T) * v.size());for (size_t i = 0; i <v.size(); i++){_start[i] = v._start[i];//例如是string，调用string的赋值(=)重载(进行深拷贝)}_finish = _start + v.size();_endofstorage = _start + v.capacity();}//扩容
void reserve(size_t n)
{if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(int) * size());for (size_t i = 0; i < sz; i++){tmp[i]=_start[i];//例如是string，调用string的赋值(=)重载(进行深拷贝)}delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}
}结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。
5.动态二维数组存储形式
6.vector的模拟实现
6.1反向迭代器的实现
可多容器复用。
成员变量是正向迭代，和正向迭代的逻辑是反的。
template<class iterator,class Ref,class Ptr>
struct Reverse_iterator
{
public:typedef Reverse_iterator<iterator, Ref, Ptr> Self;iterator _it;Reverse_iterator(iterator it):_it(it){ }Self operator++(){--_it;return *this;}Self operator--(){++_it;return *this;}Ref operator*(){iterator tmp = _it;return *(--tmp);}Ptr operator->(){return &(operator*());}bool operator!=(const Self& s) const{return _it != s._it;}
};6.2常用函数的模拟实现
template<class T>
class vector
{
public://正向迭代器typedef T* iterator;typedef const T* const_iterator;//方向迭代器typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;typedef Reverse_iterator<const_iterator, const T&, const T*> reverse_const_iterator;//反向迭代器reverse_iterator rbegin(){return _finish;}reverse_iterator rend(){return _start;}reverse_const_iterator rbegin() const{return _finish;}reverse_const_iterator rend() const{return _start;}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}vector(){}vector(const vector<T>& v){_start = new T[v.capacity()];//memcpy(_start, v._start, sizeof(T) * v.size());for (size_t i = 0; i <v.size(); i++){_start[i] = v._start[i];//例如是string，调用string的赋值(=)重载(进行深拷贝)}_finish = _start + v.size();_endofstorage = _start + v.capacity();}//复用已实现的接口/*vector(const vector<int>& v){_start = reserve(v.capacity());for (auto& e : v){push_back(e);}}*///vector<int> v1(10u, 1);//vector<string> v2(10, "1111");//vector<int> v3(10, 1);vector(int n, const T& val = T()){resize(n, val);}vector(size_t n, const T& val=T()){resize(n, val);}//迭代器区间初始化template<class InputIterator>//[first,last)vector(InputIterator first, InputIterator last){reserve(last - first);while (first != last){*_finish = *first;++first;++_finish;}}//析构函数~vector(){if (_start != nullptr){delete[] _start;_start = _finish = _endofstorage = nullptr;}}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}vector<T>& operator=(vector<T> v){swap(v);return *this;}//扩容void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(int) * size());for (size_t i = 0; i < sz; i++){tmp[i]=_start[i];//例如是string，调用string的赋值(=)重载(进行深拷贝)}delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}}//尾插void push_back(const T& val){/*if (_finish == _endofstorage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = val;++_finish;*/insert(end(), val);}//尾删void pop_back(){auto pos = end();erase(--pos);//erase(--end());}void resize(size_t n, const T& val = T()){if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}}//pos位置前插入iterator insert(iterator pos, const T& val){assert(pos >= _start && pos <= _finish);if (_finish == _endofstorage){size_t gap = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + gap; //防止扩容的时候失效}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = val;_finish++;return pos;}//删除pos位置的数据iterator erase(iterator pos){assert(pos >= _start && pos <= _finish);iterator end = pos + 1;while (end != _finish){*(end - 1) = *end;++end;}_finish--;return pos;}T& operator[](size_t pos){assert(pos < size());return _start[pos];}size_t size() const{return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}private:T* _start=nullptr;T* _finish=nullptr;T* _endofstorage=nullptr;
};
