vector介紹

1. 和我們原來講的string不同，vector并不是類，是一個類模板，加<類型>實例化以后才是類。
2. vector是表示可變大小數組的序列容器。
3. 像數組一樣，vector也采用的連續存儲空間來存儲元素，但是容量可以動態改變。
4. 和其它容器相比，vector訪問元素、尾插、尾刪較高效，但不在尾部的插入和刪除效率比較低，需要頻繁插入和刪除的話不建議使用vector。

vector常用接口

1.構造

函數聲明	功能
vector()（常用）	無參構造
vector （size_type n, const value_type& val = value_type()）	構造并初始化n個val
vector (const vector& x)（常用）	拷貝構造
vector (InputIterator first, InputIterator last)	迭代器區間初始化 (模板，可以傳入其它容器的迭代器區間)

2.迭代器

函數聲明	功能
begin()加end() （常用）	獲取第一個數據位置的iterator/const_iterator，獲取最后一個數據的下一個位置的iterator/const_iterator
rbegin()加rend()	反向迭代器，獲取最后一個數據位置的reverse_iterator，獲取第一個數據前一個位置的reverse_iterator

3.容量

函數聲明	功能
size() （常用）	獲取數據個數
capacity()	獲取容器容量
empty()	判斷是否為空(size為0為空，返回true)
resize(size_type n, value_type val = value_type())	?????1.n>size()時從尾開始填充val直到容器滿； 2.n>容量就先擴容再填充； ?????3.n<size()時縮小size()，保留前n個。
reserve(size_t n = 0)	預留空間，n大于容量時擴容，不然什么都不做

4.增刪查改

函數聲明	功能
push_back (const value_type& val)（常用）	尾插
pop_back()（常用）	尾刪
find (InputIterator first, InputIterator last, const T& val)	不是vector接口，是算法庫里面的模板，傳入一段迭代器區間，可以在該區間查找val
insert (iterator position, const value_type& val)	在position前插入val
erase (iterator position)	刪除position位置的數據
swap (vector& x)	交換兩個vector的數據空間
operator[] (size_type n)	像數組一樣訪問數據

5.練習

• 只出現一次的數字i

題目要求：

題解：

class Solution 
{
public:int singleNumber(vector<int>& nums) {//這個題需要異或這個位運算//異或是相同為0，不同為1。//所以兩個相同的數異或會得到0//0和任何數異或都得到這個數本身//題目明確了只有一個數出現一次，其它都出現兩次//因此我們可以把所有數異或一次，出現兩次的數字會抵消變成0//最后出現一次的數字一定可以留下來int end = 0;vector<int>::iterator it = nums.begin();//auto it = nums.begin();while(it != nums.end()){end ^= *it;it++;}//范圍for同理// for(auto ch : nums)//     end ^= ch;return end;}
};

---

• 刪除排序數組中的重復項

題目要求：

題解：

class Solution {
public:int removeDuplicates(vector<int>& nums) {int sum = 1;int slow = 1;int fast = 1;//快慢指針while(fast < nums.size()){if(nums[fast] > nums[fast-1]){nums[slow++] = nums[fast++];sum++;}else{fast++;}}return sum;        }
};

---

• 楊輝三角

題目要求：

題解：

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> vv;//把size調整為numRowsvv.resize(numRows);for(int i = 0; i < numRows; i++){vv[i].resize(i+1,0);//每一行最后一個和第一個初始為1vv[i][0] = vv[i][vv[i].size()-1] = 1;}for(int i = 0; i < numRows; 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;}
};

vector模擬實現

1.迭代器失效

??????迭代器的主要作用就是讓算法能夠不用關心底層數據結構，而vector迭代器的底層實際是一個指針，在對容器進行操作（例如插入、刪除、修改等）后，之前獲取的迭代器可能會變得無效。

可能會導致其迭代器失效的操作有：

1. 會引起其底層空間改變的操作(擴容)，都有可能是迭代器失效，比如：resize、reserve、insert、push_back等。

#define _CRT_SECURE_NO_WARNINGS 1
#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;
}

2. 指定位置元素的刪除操作–erase

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
#include <vector>
int main()
{vector<int> v{ 1,2,3,4,5,6 };//earse不會影響底層的空間（不進行擴容和縮容）//但是也存在迭代器失效的問題//下面這段代碼用來刪除v中的偶數auto it = v.begin();while (it != v.end()){if (*it % 2 == 0) {//把這個位置數據刪除掉v.erase(it);}it++;}//結果：程序崩潰//原因：看圖解，erase是會改變end()的//解決方法：每次erase操作后都及時更新迭代器//erase會返回被刪除數據下一位置的迭代器//auto it = v.begin();//while (it != v.end())//{//	if (*it % 2 == 0)//	{//		//把這個位置數據刪除掉//		it = v.erase(it);//	}//	else//	{//		it++;//	}//}return 0;
}

2.反向迭代器

??????vector的反向迭代器實現并不困難，只需要復用普通的迭代器，++操作變成調用普通迭代器的–，–調用++即可。

// 反向迭代器需要進行封裝，其實就是復用普通迭代器，然后++和--操作反過來
//這里設計模板參數除了迭代器，還有Ref(引用)和Ptr(指針)
//這樣設計是為了同時生成普通迭代器和const對象的迭代器//普通對象（可讀可寫）：Reverse_iterator<iterator，T&，T*>
//const對象（可讀不可寫）：Reverse_iterator<const_iterator，const T&，const T*>
template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{//給自己也重命名一下，方便用typedef Reverse_iterator<Iterator, Ref, Ptr> self;Iterator _it;Reverse_iterator(Iterator it):_it(it){}self& operator++(){_it--;return *this;}self operator++(int){self tmp(*this);_it--;return tmp;}self& operator--(){_it++;return *this;}self operator--(int){self tmp(*this);_it++;return tmp;}Ref operator*(){return *_it;}//返回指針可以讓自定義類型自行打印，訪問成員//->操作符，比較特殊，it->_num轉換出來其實是it.operator->()->_numPtr operator->(){return _it;}bool operator!=(const self& s){return _it != s._it;}bool operator==(const self& s){return _it == s._it;}
};

3.完整代碼

采用三個迭代器(指針)來維護底層空間：

private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;

#pragma once
#include<iostream>
#include<assert.h>
//#include<vector>
using namespace std;//和庫里面的區分開
namespace MyVector
{// 反向迭代器需要進行封裝，其實就是復用普通迭代器，然后++和--操作反過來//這里設計模板參數除了迭代器，還有Ref(引用)和Ptr(指針)//這樣設計是為了同時生成普通迭代器和const對象的迭代器//普通對象（可讀可寫）：Reverse_iterator<iterator，T&，T*>//const對象（可讀不可寫）：Reverse_iterator<const_iterator，const T&，const T*>template<class Iterator, class Ref, class Ptr>struct Reverse_iterator{//給自己也重命名一下，方便用typedef Reverse_iterator<Iterator, Ref, Ptr> self;Iterator _it;Reverse_iterator(Iterator it):_it(it){}self& operator++(){_it--;return *this;}self operator++(int){self tmp(*this);_it--;return tmp;}self& operator--(){_it++;return *this;}self operator--(int){self tmp(*this);_it++;return tmp;}Ref operator*(){return *_it;}//返回指針可以讓自定義類型自行打印，訪問成員//->操作符，比較特殊，it->_num轉換出來其實是it.operator->()->_numPtr operator->(){return _it;}bool operator!=(const self& s){return _it != s._it;}bool operator==(const self& s){return _it == s._it;}};//vector類模板template <typename 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;iterator begin(){//隱式類型轉換return _start;}iterator end(){return _finish;}const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}reverse_iterator rbegin(){return  _finish-1;}reverse_iterator rend(){return _start-1;}reverse_const_iterator rbegin()const{return _finish-1;}reverse_const_iterator rend()const{return _start-1;}/////無參構造vector(){}//函數模板，傳入容器的一段迭代器區間template <typename InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}//構造vector(const vector<T>& v){//提前開好空間reverse(v.capacity());for (auto& e : v){push_back(e);}}vector(size_t n, const T& val = T()){reverse(n);for (size_t i = 0; i < n; i++){push_back(val);}}//重載給內置類型使用//沒有的話vector<int> v(5,0)會優先和vector(InputIterator first, InputIterator last)匹配//對整形解引用會報錯vector(int n, const T& val = T()){reverse(n);for (int i = 0; i < n; i++){push_back(val);}}~vector(){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 reverse(size_t n){if (n > capacity()){//這里擴容空間會變化，先記錄size//這里擴容空間會變化，先記錄size//這里擴容空間會變化，先記錄sizesize_t sz = size();T* tmp = new T[n];//這里涉及到深淺拷貝for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}}void resize(size_t n, const T& val = T()){if (n <= size()){_finish = _start + n;}else{//先擴容reverse(n);while (_finish < _start + n){*_finish = val;_finish++;}}}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 capacity()const{return _endofstorage - _start;}size_t size()const{return _finish - _start;}/// ///void push_back(const T& x){//復用即可insert(end(), x);}void insert(iterator pos, const T& x){assert(pos <= _finish && pos >= _start);if (_finish == _endofstorage){size_t gap = pos - _start;//初始擴容需要指定給reverse(capacity() == 0 ? 4 : 2 * capacity());pos = _start + gap;}iterator end = _finish;while (end > pos){*end = *(end - 1);end--;}*pos = x;_finish++;			}iterator erase(iterator pos){assert(pos < _finish&& pos >= _start);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;it++;}_finish--;return pos;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};}