一、vector介紹
vector文檔介紹

Vector 是序列容器，表示可以改變大小的數(shù)組。與數(shù)組一樣，Vector使用其元素的連續(xù)存儲位置，這意味著也可以使用指向其元素的常規(guī)指針上的偏移量來訪問其元素，并且與數(shù)組中一樣高效。但與陣列不同的是，它們的大小可以動態(tài)變化，其存儲由容器自動處理。
在內(nèi)部，Vector 使用動態(tài)分配的數(shù)組來存儲其元素。當(dāng)插入新元素時，可能需要重新分配此數(shù)組以增大其大小，這意味著分配一個新數(shù)組并將所有元素移動到該數(shù)組中。就處理時間而言，這是一項(xiàng)相對昂貴的任務(wù)，因此，向量不會在每次將元素添加到容器時重新分配。
相反，vector容器可能會分配一些額外的存儲以適應(yīng)可能的增長，因此容器的實(shí)際容量可能大于嚴(yán)格要求包含其元素的存儲容量（即，其大?。炜梢詫?shí)現(xiàn)不同的增長策略，以平衡內(nèi)存使用和重新分配，但在任何情況下，重新分配只應(yīng)以對數(shù)增長的大小間隔進(jìn)行，以便在向量末尾插入單個元素時可以提供攤銷的恒定時間復(fù)雜度
因此，與陣列相比，vector消耗更多內(nèi)存，以換取以高效方式管理存儲和動態(tài)增長的能力。
與其他動態(tài)序列容器（deques、list和forward_list）相比，向量非常高效地訪問其元素（就像數(shù)組一樣），并且相對高效地從其末端添加或刪除元素。對于涉及在端點(diǎn)以外的位置插入或刪除元素的操作，它們的性能比其他操作差，并且與列表和轉(zhuǎn)發(fā)列表相比，迭代器和引用的一致性較差。
二、vector使用
1.vector構(gòu)造方法

vector() 無參構(gòu)造
vector（size_type n, const value_type& val = value_type()） 構(gòu)造并初始化n個val
vector (const vector& x); 拷貝構(gòu)造
vector (InputIterator first, InputIterator last); 使用迭代器進(jìn)行初始化構(gòu)造

vector<int> v;	//無參構(gòu)造	vector<int> v1(5,6);	//構(gòu)造并用5個6初始化v1	vector<int> v2(v1);	//拷貝構(gòu)造	vector<int> v3(v1.begin(),v1.end());	//使用迭代器進(jìn)行初始化構(gòu)造

第一個是無參構(gòu)造：
構(gòu)造一個沒有元素的空容器。
第二個是構(gòu)造函數(shù)：
構(gòu)造一個包含n個元素的容器。每個元素都是val的副本。
拷貝構(gòu)造：
以相同的順序構(gòu)造一個容器，其中包含x中每個元素的副本。
第4個構(gòu)造函：
用迭代器構(gòu)造構(gòu)造一個容器，其中包含與范圍[first，last]相同數(shù)量的元素，每個元素都是從該范圍內(nèi)對應(yīng)的元素以相同的順序構(gòu)造的。
2.iterator 的使用

begin + end 獲取第一個數(shù)據(jù)位置的iterator/const_iterator， 獲取最后一個數(shù)據(jù)的下一個位置 的iterator/const_iterator
rbegin + rend 獲取最后一個數(shù)據(jù)位置的reverse_iterator，獲取第一個數(shù)據(jù)前一個位置的 reverse_iterator

vector<int>::iterator it = v2.begin();		while (it != v2.end()) {			cout << *it << " ";			it++;		}

正向迭代器從第一個數(shù)開始遍歷，沒打印一個數(shù)就就獲取后一位置的迭代器一直如此直到迭代器指到容器尾部。

vector<int>::reverse_iterator it = v2.rbegin();		while (it != v2.rend()) {			cout << *it << " ";			it++;		}

反向迭代器和正向迭代器相反從容器尾部開始遍歷直到遍歷到容器首部就停止。
3.vector空間增長問題

size 獲取數(shù)據(jù)個數(shù)
capacity 獲取容量大小
empty 判斷是否為空
resize 改變vector的size
reserve 改變vector放入capacity

• capacity的代碼在vs和g++下分別運(yùn)行會發(fā)現(xiàn)，vs下capacity是按1.5倍增長的，g++是按2倍增長的。
  這個問題經(jīng)常會考察，不要固化的認(rèn)為，順序表增容都是2倍，具體增長多少是根據(jù)具體的需求定義
  的。vs是PJ版本STL，g++是SGI版本STL。
• reserve只負(fù)責(zé)開辟空間，如果確定知道需要用多少空間，reserve可以緩解vector增容的代價缺陷問題。
• resize在開空間的同時還會進(jìn)行初始化，影響size。

	vector<int> v;		//無參構(gòu)造		vector<int> v1(5,6);		//構(gòu)造并用5個6初始化v1		cout<<v1.size() << endl;		cout << v1.capacity() << endl;		cout << v.empty() << endl;		cout << v1.empty() << endl;

首先這里v1的size()和capacity()的大小相同但是代表的是不同含義，size()代表是有效數(shù)據(jù)長度，而capacity代表是容器的容量大小在一般情況下不相等。因?yàn)関是無參構(gòu)造所以v.empty（）輸出是1，而v1有數(shù)據(jù)所以輸出了0.
4.vector增刪查改

push_back 尾插
pop_back 尾刪
find 查找。
insert 在position之前插入val
erase 刪除position位置的數(shù)據(jù)
swap 交換兩個vector的數(shù)據(jù)空間
operator[] 像數(shù)組一樣訪問

		vector<int> v;		//無參構(gòu)造	v.push_back(0);	v.push_back(1);	v.push_back(2);	v.push_back(3);	v.push_back(4);		//使用迭代器進(jìn)行初始化構(gòu)造		vector<int>::iterator it = v.begin();		while (it != v.end()) {			cout << *it << " ";			it++;		}		cout << endl;		v.pop_back();		vector<int>::iterator it1 = v.begin();		while (it1 != v.end()) {			cout << *it1 << " ";			it1++;		}		cout << endl;

首先對無參構(gòu)造的v尾插幾個數(shù)打印數(shù)，接著未刪后接著打印一邊數(shù)來驗(yàn)證函數(shù)。

vector的inseert的使用要借助迭代器

		vector<int> v;		//無參構(gòu)造	v.push_back(0);	v.push_back(1);	v.push_back(2);	v.push_back(3);	v.push_back(4);	 		//使用迭代器進(jìn)行初始化構(gòu)造		vector<int>::iterator it = v.begin();		while (it != v.end()) {			cout << *it << " ";			it++;		}		cout << endl;		v.insert(v.begin(),2, 9);		vector<int>::iterator it1 = v.begin();		while (it1 != v.end()) {			cout << *it1 << " ";			it1++;		}		cout << endl;		v.insert(v.begin(), 9);		vector<int>::iterator it11 = v.begin();		while (it11 != v.end()) {			cout << *it11 << " ";			it11++;		}		cout << endl;

通過在指定位置的元素之前插入新元素來擴(kuò)展向量，從而通過插入的元素?cái)?shù)量有效地增加容器大小。
當(dāng)且僅當(dāng)新向量大小超過當(dāng)前向量容量時，這會導(dǎo)致自動重新分配分配分配的存儲空間。

	vector<int> v;		//無參構(gòu)造		int val[5] = { 0,1,2,3,4 };		v.insert(v.begin(), val, val + 5);		//使用迭代器進(jìn)行初始化構(gòu)造		vector<int>::iterator it = v.begin();		while (it != v.end()) {			cout << *it << " ";			it++;		}

因?yàn)橄蛄渴褂脭?shù)組作為其底層存儲，所以在向量末端以外的位置插入元素會導(dǎo)致容器將位置之后的所有元素重新定位到它們的新位置。與其他類型的序列容器對相同操作執(zhí)行的操作相比，這通常是一種低效的操作。

find函數(shù)底層實(shí)際上是對指針的操作

向[first，last]范圍內(nèi)比較等于val的第一個元素返回迭代器。如果未找到此類元素，則函數(shù)返回last。函數(shù)使用運(yùn)算符==將各個元素與val進(jìn)行比較。此函數(shù)模板的行為等效于：

template<class InputIterator, class T>  InputIterator find (InputIterator first, InputIterator last, const T& val){  while (first!=last) {    if (*first==val) return first;    ++first;  }  return last;}

這是文檔給出的解釋。

	vector<int> v;		//無參構(gòu)造		v.push_back(0);		v.push_back(2);		v.push_back(3);		v.push_back(4);		v.push_back(5);		auto it = find(v.begin(), v.end(), 2);		if (it != v.end()) {			cout << "找到了" << endl;		}		v.erase(it);

find函數(shù)找到2的位置迭代器，然后erase刪除it

	auto it1 = v.begin();		while (it1!=v.end()) {			if (*it1 == 2) {				v.erase(it1);			}					it1++;		}

這樣一段程序會出錯，因?yàn)関ector的迭代器也是指針，如果刪除這個指針?biāo)傅臄?shù)據(jù)對于釋放了這個空間，it就變成一個野指針對一個野指針進(jìn)行 it++ 是肯定會出錯的。
我們通過查閱文檔可以看到erase函數(shù)的返回值是這么介紹的：一個迭代器，指定在任何刪除的元素之后剩余的第一個元素，如果不存在這樣的元素，則指定指向向量結(jié)尾的指針
4.vector迭代器失效問題
這里正式簡單解釋一下迭代器實(shí)現(xiàn)
迭代器的主要作用就是讓算法能夠不用關(guān)心底層數(shù)據(jù)結(jié)構(gòu)，其底層實(shí)際就是一個指針，或者是對指針進(jìn)行了
封裝，比如：vector的迭代器就是原生態(tài)指針T*。因此迭代器失效，實(shí)際就是迭代器底層對應(yīng)指針?biāo)赶虻?br /> 空間被銷毀了，而使用一塊已經(jīng)被釋放的空間，造成的后果是程序崩潰(即如果繼續(xù)使用已經(jīng)失效的迭代器，
程序可能會崩潰)。
對于vector可能會導(dǎo)致其迭代器失效的操作有：

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

#include using namespace std;#include int main(){vector<int> v{1,2,3,4,5,6};auto it = v.begin();// 將有效元素個數(shù)增加到100個，多出的位置使用8填充，操作期間底層會擴(kuò)容// v.resize(100, 8);// reserve的作用就是改變擴(kuò)容大小但不改變有效元素個數(shù)，操作期間可能會引起底層容量改變// v.reserve(100);// 插入元素期間，可能會引起擴(kuò)容，而導(dǎo)致原空間被釋放// v.insert(v.begin(), 0);// 給vector重新賦值，可能會引起底層容量改變v.assign(100, 8);/*出錯原因：以上操作，都有可能會導(dǎo)致vector擴(kuò)容，也就是說vector底層原理舊空間被釋放掉，而在打印時，it還使用的是釋放之間的舊空間，在對it迭代器操作時，實(shí)際操作的是一塊已經(jīng)被釋放的空間，而引起代碼運(yùn)行時崩潰。解決方式：在以上操作完成之后，如果想要繼續(xù)通過迭代器操作vector中的元素，只需給it重新賦值即可。*/while(it != v.end()){cout<< *it << " " ;++it;}cout<<endl;return 0;}//我們一般也不這么做。

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

#include using namespace std;#include 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位置的數(shù)據(jù)，導(dǎo)致pos迭代器失效。v.erase(pos);cout << *pos << endl; // 此處會導(dǎo)致非法訪問return 0;}

erase刪除pos位置元素后，pos位置之后的元素會往前搬移，沒有導(dǎo)致底層空間的改變，理論上講迭代器不應(yīng)該會失效，但是：如果pos剛好是最后一個元素，刪完之后pos剛好是end的位置，而end位置是沒有元素的，那么pos就失效了。因此刪除vector中任意位置上元素時，vs就認(rèn)為該位置迭代器失效了。

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;}

迭代器失效解決辦法：在使用前，對迭代器重新賦值即可。