要努力，但不要着急，繁花锦簇，硕果累累都需要过程！
目录
1.vector的介绍及使用
1.1vector的介绍
1.2vector的使用
2.vector模拟实现
3.vector常见试题
1.vector的介绍及使用
1.1vector的介绍
1. vector是表示可变大小数组的序列容器。
2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
1.2vector的使用
1.vector的学习一定要会查看文档：vector文档介绍
2.vector常用接口介绍
2.1构造接口
| vector() | 无参构造 |
| vector(size_type n, const value_type& val = value_type()) | 构造并初始化n个val |
| vector (const vector& x) | 拷贝构造 |
| vector (InputIterator first, InputIterator last) | 使用迭代器进行初始化构造 |
2.2vector iterator迭代器
| begin+end | 获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置 的iterator/const_iterator |
| rebegin+rend | 获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的 reverse_iterator |
void Test1() {vector<int> v1(3, 2);//使用迭代器进行遍历vector<int>::iterator it = v1.begin();while (it != v1.end()){cout << *it << " ";it++;}cout << endl; } int main() {Test1();return 0; }
void Test1() {vector<int> v1(3, 2);//rbegin()+rend()遍历：vector<int>::reverse_iterator rit = v1.rbegin();while (rit != v1.rend()){cout << *rit << " ";rit++;}cout << endl; } int main() {Test1();return 0; }
2.3vector空间有关接口：
| size() | 获取数据个数 |
| capacity() | 获取容量大小 |
| resize() | 改变vector的size |
| reserve() | 改变vector的capacity |
| empty() | 判断是否为空 |
resize()存在三种情况：
1.n < size:删除数据
2.size < n <=capacity:插入数据
3.n > capacity:扩容+插入数据
vector扩容机制：
在不同的平台上增容倍数是不相同的，在vs上是以1.5倍增容的，在g++上是以2倍增长的！
g++:
2.4vector增删查改
| push_back() | 尾插 |
| pop_back() | 尾删 |
| find() | 查找。（注意这个是算法模块实现，不是vector的成员接口） |
| insert() | 在position之前插入val |
| erase() | 删除position位置的数据 |
| swap() | 交换两个vector的数据空间 |
| operator[] | 像数组一样访问 |
2.vector模拟实现
//用命名空间封装避免和库里的冲突 namespace N {template<typename T>class vector{public:typedef T* iterator;//迭代器typedef const T* const_iteratorprivate:iterator _start;iterator _finsh;iterator _endofstorage;}; }
构造函数：
//无参构造vector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr){}//构造并初始化n个val//vector<int> v(10, 2); // 两个参数都是int,走模板，然后对int类型解引用，造成非法间接寻址//vector<char> v(10, 'a');//一个是int,一个是char,模板不能推演为两种类型，所以只能走下面这种//解决方法：重载一个参数是int类型的构造函数template<typename InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}vector(int n, const T& val = T()):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){reserve(n);for (int i = 0; i < n; i++){push_back(val);}}vector(size_t n, const T& val = T()):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}拷贝构造函数：
//拷贝构造传统写法1：vector(vector<T>& v){_start = new T[v.capacity()];memcpy(_start, v._start, sizeof(T) * v.size());_finish = _start + v.size();_endofstorage = _start + v.capacity();}//拷贝构造传统写法2：vector(vector<T>& v):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){reserve(v.capacity());for (auto& e : v)//必须要用引用，否则如果是自定义类型，就会有浅拷贝的问题{push_back(e);}}template<typename InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}//拷贝构造现代写法：vector(vector<T>& v):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){vector<T> tmp(v.begin(), v.end());swap(tmp);}赋值重载函数：
void swap(vector<T>& v){//调用算法库里面的swapstd::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}vector<T>& operator=(vector<T> v){swap(v);return *this;}析构函数:
~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}迭代器：
iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}operator[]函数：
T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}容量相关的接口：
size_t size(){return _finish - _start;}size_t capacity(){return _endofstorage - _start;}bool empty(){return _start == _finish;}void reserve(size_t n){if (n > capacity()){size_t oldsize = size();T* tmp = new T[n];if (_start){memcpy(tmp, _start, sizeof(T) * oldsize);delete[] _start;}_start = tmp;//size()=_finish-_start:而_start已经被改了，会出现程序崩溃//_finish = _start + size();_finish = _start + oldsize;_endofstorage = _start + n;}}void push_back(const T& x){if (_finish == _endofstorage){size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);}*_finish = x;_finish++;}void resize(size_t n, T val = T()){//n > capacity():扩容+插入数据if (n > capacity()){reserve(n);}// size() < n <= capacity:插入数据if (n > size()){while (_finish < _start + n){*_finish = val;_finish++;}}else//n < size():删除数据{_finish = _start + n;}}void pop_back(){assert(!empty());--_finish;}void clear(){_finish = _start;}insert函数接口：
//扩容会导致迭代器失效，pos位置无意义/*void insert(iterator pos, const T& val){assert(pos >= _start);assert(pos < _finish);if (_finish = _endofstorage){size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = val;_finish++;}*///解决方法：更新pos//insert以后，it不能继续使用，迭代器失效导致野指针问题/*void insert(iterator pos, const T& val){assert(pos >= _start);assert(pos < _finish);if (_finish = _endofstorage){size_t len = pos - _start;size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = val;_finish++;}*///解决方法：利用返回值iterator insert(iterator pos, const T& val){assert(pos >= _start);assert(pos < _finish);if (_finish = _endofstorage){size_t len = pos - _start;size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = val;_finish++;return pos;}//删除之后使用it会产生问题：/*void erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *(begin);++begin;}--_finish;}*///解决方法：带返回值iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *(begin);++begin;}--_finish;return pos;}深层次的深拷贝问题：
扩容导致自定义类对象浅拷贝再析构的时候程序崩溃了：
当插入第五个的时候就会扩容：
memcpy是浅拷贝，所以tmp将指向的空间的释放掉，而_start就指向了一块被释放的空间
解决方法：使用自定义类对像自己的深拷贝
3.vector常见试题
1.只出现一次的数字：oj链接
思路：异或：相同则为1，相异则为0
class Solution { public:int singleNumber(vector<int>& nums) {int ret = 0;for(auto e:nums){ret ^= e;}return ret;} };2.杨辉三角：oj链接
思路：
class Solution { public:vector<vector<int>> generate(int numRows) {vector<vector<int>> vv;vv.resize(numRows);for(int i = 0; i < vv.size(); i++){vv[i].resize(i+1);vv[i][0] = vv[i][vv[i].size()-1] = 1;}for(int i = 0; i < vv.size(); i++){for(int j = 0; j < vv[i].size(); j++){if(vv[i][j] == 0){vv[i][j] = vv[i-1][j] + vv[i-1][j-1];}}}return vv;} };3.电话号码的字母组合：oj链接
思路：
class Solution {string _str[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; public:void Combin(const string& digits,int i,vector<string>& vCombin,string CombinStr){if(i == digits.size()){vCombin.push_back(CombinStr);return;}int num = digits[i]-'0';string str = _str[num];for(auto& e:str){Combin(digits,i+1,vCombin,CombinStr+e);}}vector<string> letterCombinations(string digits) {vector<string> vCombin;if(digits.empty())return vCombin;int i = 0;string str;Combin(digits,i,vCombin,str);return vCombin;} };4.只出现一次的数字II：oj链接
class Solution { public:int singleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());int i = 0;for(i = 0; i < nums.size(); i+=3){if(i + 1 < nums.size()){if(nums[i] != nums[i + 1]){break;}}else{break;} }return nums[i];} };5.只出现一次的数字III：oj链接
class Solution { public:vector<int> singleNumber(vector<int>& nums) {vector<int> v;v.resize(2);int pos = 0;sort(nums.begin(),nums.end());for(int i = 0; i < nums.size(); i++){if(i + 1 < nums.size()){if(nums[i] != nums[i+1]){v[pos++] = nums[i];}else{i++;}}else{v[pos++] = nums[i];}}return v;} };6.数组中出现超过一半的数字：oj链接
class Solution { public:int MoreThanHalfNum_Solution(vector<int> numbers) {if(numbers.empty())return 0;//如果两个数不相同就消去int result = numbers[0];int times = 1;for(int i = 1; i < numbers.size(); i++){if(times != 0){if(numbers[i] != result){times--;}else{times++;}}else{result = numbers[i];times = 1;}}//统计最后result出现的次数times = 0;for(int i = 0; i <numbers.size(); i++){if(numbers[i] == result){times++;}}//判断出现的次数是否大于一半的数if(times > numbers.size()/2){return result;}return 0;} };
