一、vector底層實(shí)現(xiàn)機(jī)制刨析

通過分析 vector 容器的源代碼不難發(fā)現(xiàn)，它就是使用 3 個(gè)迭代器（可以理解成指針）來表示的：
其中statrt指向vector 容器對(duì)象的起始字節(jié)位置；
finish指向當(dāng)前最后一個(gè)元素的末尾字節(jié)
end_of指向整個(gè) vector 容器所占用內(nèi)存空間的末尾字節(jié)。
如圖 演示了以上這 3 個(gè)迭代器分別指向的位置

如圖 演示了以上這 2個(gè)迭代器分別指向的位置

在此基礎(chǔ)上，將 3 個(gè)迭代器兩兩結(jié)合，還可以表達(dá)不同的含義，例如：
start 和 finish 可以用來表示 vector 容器中目前已被使用的內(nèi)存空間；
finish 和 end_of可以用來表示 vector 容器目前空閑的內(nèi)存空間；
start和 end_of可以用表示 vector 容器的容量。
二、vector的核心框架接口的模擬實(shí)現(xiàn)

1.vector的迭代器實(shí)現(xiàn)

typedef T* Iteratot;
typedef T* const_Iteratot;

Iteratot cend()const {			return final_end;		}		Iteratot cbegin()const {			return start;		}			Iteratot end() {			return final_end;		}		Iteratot begin() {			return start;		}

vector的迭代器是一個(gè)原生指針,他的迭代器和String相同都是操作指針來遍歷數(shù)據(jù)：

• begin()返回的是vector 容器對(duì)象的起始字節(jié)位置；
• end()返回的是當(dāng)前最后一個(gè)元素的末尾字節(jié)；

2.reserve()擴(kuò)容

	void reserve(size_t n) {			if (n > capacity()) {				T* temp = new T  [n];				//把statrt中的數(shù)據(jù)拷貝到temp中				size_t size1 = size();				memcpy(temp, start, sizeof(T*) * size());							start = temp;			  final_end = start + size1;				finally = start + n;			}		}

當(dāng) vector 的大小和容量相等（size==capacity）也就是滿載時(shí)，如果再向其添加元素，那么 vector 就需要擴(kuò)容。vector 容器擴(kuò)容的過程需要經(jīng)歷以下 3 步：

• 完全棄用現(xiàn)有的內(nèi)存空間，重新申請(qǐng)更大的內(nèi)存空間；
• 將舊內(nèi)存空間中的數(shù)據(jù)，按原有順序移動(dòng)到新的內(nèi)存空間中；
• 最后將舊的內(nèi)存空間釋放。

這也就解釋了，為什么 vector 容器在進(jìn)行擴(kuò)容后，與其相關(guān)的指針、引用以及迭代器可能會(huì)失效的原因。

由此可見，vector 擴(kuò)容是非常耗時(shí)的。為了降低再次分配內(nèi)存空間時(shí)的成本，每次擴(kuò)容時(shí) vector 都會(huì)申請(qǐng)比用戶需求量更多的內(nèi)存空間（這也就是 vector 容量的由來，即 capacity>=size），以便后期使用。

vector 容器擴(kuò)容時(shí)，不同的編譯器申請(qǐng)更多內(nèi)存空間的量是不同的。以 VS 為例，它會(huì)擴(kuò)容現(xiàn)有容器容量的 50%。

使用memcpy拷貝問題
reserve擴(kuò)容就是開辟新空間用memcpy將老空間的數(shù)據(jù)拷貝到新開空間中。
假設(shè)模擬實(shí)現(xiàn)的vector中的reserve接口中，使用memcpy進(jìn)行的拷貝，以下代碼會(huì)發(fā)生什么問題？

int main(){bite::vector<bite::string> v;v.push_back("1111");v.push_back("2222");v.push_back("3333");return 0;}

問題分析:

1. memcpy是內(nèi)存的二進(jìn)制格式拷貝，將一段內(nèi)存空間中內(nèi)容原封不動(dòng)的拷貝到另外一段內(nèi)存空間中
2. 如果拷貝的是自定義類型的元素，memcpy即高效又不會(huì)出錯(cuò)，但如果拷貝的是自定義類型元素，并且
   自定義類型元素中涉及到資源管理時(shí)，就會(huì)出錯(cuò)，因?yàn)閙emcpy的拷貝實(shí)際是淺拷貝。
   
   
   
   
   結(jié)論：如果對(duì)象中涉及到資源管理時(shí)，千萬不能使用memcpy進(jìn)行對(duì)象之間的拷貝，因?yàn)閙emcpy是淺拷貝，否則可能會(huì)引起內(nèi)存泄漏甚至程序崩潰。
   3.尾插尾刪(push_back(),pop_back())

	void push_back(const T&var) {			if (final_end ==finally) {				size_t newcode = capacity() == 0 ? 4 : capacity() * 2;				reserve(newcode);			}			*final_end = var;			++final_end;		void pop_back() {					final_end--;		}

插入問題一般先要判斷空間是否含有閑置空間，如果沒有，就要開辟空間。我們final_end==finally來判斷是否含有閑置空間。如果容器含沒有空間先開辟4字節(jié)空間，當(dāng)滿了后開2capacoity()空間。在final_end部插入數(shù)據(jù)就行了。對(duì)final_end加以操作。
4.對(duì)insert()插入時(shí)迭代器失效刨析

		Iteratot insert(Iteratot iterator,const T&var) {			assert(iterator <= final_end && iterator >= start);			size_t pos = iterator - start;			if (final_end == finally) {								size_t newcode = capacity() == 0 ? 4 : capacity() * 2;				reserve(newcode);				}			//插入操作			auto it = final_end;			while (it >= start+pos) {				*(it+1)=*it;				it--;			}			*iterator = var;			final_end++;						return iterator;		}

假設(shè)這是一段vector空間要在pos插入數(shù)據(jù)，但是剛剛好final_end和final在同一位置，這個(gè)容器滿了，要對(duì)這這個(gè)容器做擴(kuò)容操作。首先對(duì)開辟和這個(gè)空間的2唄大小的空間

接著把老空間數(shù)據(jù)拷貝到新空間中釋放老空間。

由于老空間釋放了pos指向的內(nèi)存不見了。pos指針就成了野指針。
這如何解決呢就是在老空間解決之間保存這個(gè)指針，接著讓他重新指向新空間的原來位置。

而insert()函數(shù)返回了這個(gè)位置迭代器這為迭代器失效提供了方法，這個(gè)方法就是重新賦值。讓這個(gè)指針重新指向該指向的位置。

5.對(duì)erase()數(shù)據(jù)刪除時(shí)迭代器失效刨析

	Iteratot erase(Iteratot iterator) {				assert(iterator <= final_end && iterator >= start);				auto it = iterator;				while (it <final_end) {					*it = *(it+1);					it++;				}				final_end--;				return iterator;			}

vector使用erase刪除元素，其返回值指向下一個(gè)元素，但是由于vector本身的性質(zhì)（存在一塊連續(xù)的內(nèi)存上），刪掉一個(gè)元素后，其后的元素都會(huì)向前移動(dòng)，所以此時(shí)指向下一個(gè)元素的迭代器其實(shí)跟剛剛被刪除元素的迭代器是一樣的。
以下為解決迭代器失效方案：

#include #include using namespace std; int main(){    int a[] = {1, 4, 3, 7, 9, 3, 6, 8, 3, 3, 5, 2, 3, 7};    vector<int> vector_int(a, a + sizeof(a)/sizeof(int));    /*方案一*/    // for(int i = 0; i < vector_int.size(); i++)    // {    //     if(vector_int[i] == 3)    //     {    //         vector_int.erase(vector_int.begin() + i);    //         i--;    //     }    // }  /*方案二*/    // for(vector::iterator itor = vector_int.begin(); itor != vector_int.end(); ++itor)    // {    //     if (*itor == 3)    //     {    //         vector_int.erase(itor);    //         --itor;    //     }     // } /*方案三*/vector<int>::iterator v = vector_int.begin();while(v != vector_int.end()){    if(*v == 3)    {        v = vector_int.erase(v);        cout << *v << endl;    }    else{        v++;    }} /*方案四*/// vector::iterator v = vector_int.begin();// while(v != vector_int.end())// {//     if(*v == 3)//     {//         vector_int.erase(v); //     }//     else{//         v++;//     }// }     for(vector<int>::iterator itor = vector_int.begin(); itor != vector_int.end(); itor++)    {        cout << * itor << "  ";    }    cout << endl;    return 0;}

一共有四種方案。

方案一表明vector可以用下標(biāo)訪問元素，顯示出其隨機(jī)訪問的強(qiáng)大。并且由于vector的連續(xù)性，且for循環(huán)中有迭代器的自加，所以在刪除一個(gè)元素后，迭代器需要減1。

方案二與方案一在迭代器的處理上是類似的，不過對(duì)元素的訪問采用了迭代器的方法。

方案三與方案四基本一致，只是方案三利用了erase()函數(shù)的返回值是指向下一個(gè)元素的性質(zhì)，又由于vector的性質(zhì)（連續(xù)的內(nèi)存塊），所以方案四在erase后并不需要對(duì)迭代器做加法。