一、vector介紹
vector文檔介紹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

		vector<int> v;		//無參構造	v.push_back(0);	v.push_back(1);	v.push_back(2);	v.push_back(3);	v.push_back(4);		//使用迭代器進行初始化構造		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;

首先對無參構造的v尾插幾個數打印數，接著未刪后接著打印一邊數來驗證函數。

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

		vector<int> v;		//無參構造	v.push_back(0);	v.push_back(1);	v.push_back(2);	v.push_back(3);	v.push_back(4);	 		//使用迭代器進行初始化構造		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;

通過在指定位置的元素之前插入新元素來擴展向量，從而通過插入的元素數量有效地增加容器大小。
當且僅當新向量大小超過當前向量容量時，這會導致自動重新分配分配分配的存儲空間。

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

因為向量使用數組作為其底層存儲，所以在向量末端以外的位置插入元素會導致容器將位置之后的所有元素重新定位到它們的新位置。與其他類型的序列容器對相同操作執行的操作相比，這通常是一種低效的操作。

find函數底層實際上是對指針的操作

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

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;		//無參構造		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函數找到2的位置迭代器，然后erase刪除it

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

這樣一段程序會出錯，因為vector的迭代器也是指針，如果刪除這個指針所指的數據對于釋放了這個空間，it就變成一個野指針對一個野指針進行 it++ 是肯定會出錯的。
我們通過查閱文檔可以看到erase函數的返回值是這么介紹的：一個迭代器，指定在任何刪除的元素之后剩余的第一個元素，如果不存在這樣的元素，則指定指向向量結尾的指針
4.vector迭代器失效問題
這里正式簡單解釋一下迭代器實現
迭代器的主要作用就是讓算法能夠不用關心底層數據結構，其底層實際就是一個指針，或者是對指針進行了
封裝，比如：vector的迭代器就是原生態指針T*。因此迭代器失效，實際就是迭代器底層對應指針所指向的
空間被銷毀了，而使用一塊已經被釋放的空間，造成的后果是程序崩潰(即如果繼續使用已經失效的迭代器，
程序可能會崩潰)。
對于vector可能會導致其迭代器失效的操作有：

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();// 將有效元素個數增加到100個，多出的位置使用8填充，操作期間底層會擴容// v.resize(100, 8);// reserve的作用就是改變擴容大小但不改變有效元素個數，操作期間可能會引起底層容量改變// v.reserve(100);// 插入元素期間，可能會引起擴容，而導致原空間被釋放// v.insert(v.begin(), 0);// 給vector重新賦值，可能會引起底層容量改變v.assign(100, 8);/*出錯原因：以上操作，都有可能會導致vector擴容，也就是說vector底層原理舊空間被釋放掉，而在打印時，it還使用的是釋放之間的舊空間，在對it迭代器操作時，實際操作的是一塊已經被釋放的空間，而引起代碼運行時崩潰。解決方式：在以上操作完成之后，如果想要繼續通過迭代器操作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位置的數據，導致pos迭代器失效。v.erase(pos);cout << *pos << endl; // 此處會導致非法訪問return 0;}

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

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

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