目錄

????????1.序列式容器和關(guān)聯(lián)式容器

????????2.vector的定義和結(jié)構(gòu)

????????3.vector的構(gòu)造函數(shù)和析構(gòu)函數(shù)的實現(xiàn)

????????4.vector的數(shù)據(jù)結(jié)構(gòu)以及實現(xiàn)源碼

????????5.vector的元素操作

---

前言

? ? ? ? 本系列將重點對STL中的容器進行講解，而在容器的分類中，我們將容器分為序列式容器和關(guān)聯(lián)式容器。本章作為容器的實現(xiàn)源碼的講解，將簡單介紹這兩種類型的容器的區(qū)別，再對每一個類型所含的容器的實現(xiàn)源碼進行講解。

---

序列式容器和關(guān)聯(lián)式容器

????????序列式容器：按照元素的添加順序來組織元素。提供了一種線性的數(shù)據(jù)結(jié)構(gòu)，可以快速何位置的元素，插入和刪除操作可能需要移動其他元素

????????關(guān)聯(lián)式容器：通過鍵值對來存儲元素，并且通常使用某種形式的平衡樹或哈希表來組織元素。特別是對于大量數(shù)據(jù)，關(guān)聯(lián)式容器在查找、插入和刪除操作上通常具有較高的效率

? ? ? ? 序列式容器和關(guān)聯(lián)式容器的區(qū)別：

	序列式容器	關(guān)聯(lián)式容器
存儲方式	元素添加順序存儲	按鍵的順序或哈希值存儲
訪問速度	支持快速隨機訪問	不支持快速隨機訪問
插入和刪除	在插入和刪除時要移動元素，可能較慢	能提供快速的插入和刪除操作
元素唯一性	不保證元素的唯一性	保證元素的唯一性
迭代器類型	隨機訪問迭代器	雙向迭代器或正向迭代器

? ? ? ? 表1.序列式容器和關(guān)聯(lián)式容器的區(qū)別

---

vector的定義和結(jié)構(gòu)

? ? ? ? vector屬于序列式容器，定義在頭文件<vector>中，但是SGI STL將其實現(xiàn)放在更底層的<stl_vector.h>頭文件中。vector和數(shù)組很像，但是vector屬于動態(tài)存儲空間，能自動隨著元素的插入而自行擴充空間以容納新的元素，數(shù)組只能通過new或者malloc重新分配更大的空間，并將元素移動到新的空間。

? ? ? ? 在閱讀過《STL源碼刨析：迭代器概念與Traits編程方法》后，我們應該清楚以下幾點：

? ? ? ? ? ? ? ? 1.每一個容器和具體的實現(xiàn)算法是分開定義的，而為了將容器和算法串聯(lián)在一起，我們要為其定義迭代器(PS:vector的迭代器類型為隨機迭代器，因為使用vector容器時支持下標操作)

? ? ? ? ? ? ? ? 2.針對迭代器的類型，我們還需要對其封裝并判斷傳入模板的類型(Traits編程方法)

? ? ? ? ? ? ? ? 3.每一個容器都需要為其分配內(nèi)存空間，所以我們還需要一個空間配置器?????????

? ? ? ? 在以上三點的基礎(chǔ)上，我們還需要對容器定義三個迭代器，分別指向使用空間的頭，使用空間的尾和空閑空間的尾。所以我們的vector容器的結(jié)構(gòu)應該大體如下：

//vector容器的大體結(jié)構(gòu)
template<class T, class Alloc = alloc>    //alloc是默認的配置器
class vector{
public:typedef T value_type;           //傳入的參數(shù)的類型    typedef value_type* pointer;    //傳入的參數(shù)的指針typedef value_type* iterator;   //傳入的參數(shù)的迭代器typedef value_type& reference;  //傳入的參數(shù)的引用typedef size_t size_type;       //傳入的大小typedef ptrdiff_t difference_type;    //傳入的元素之間的距離
protector:typedef simple_alloc<value_type, Alloc> data_allocator;    //配置器的定義iterator start;         //表示可用空間的頭iterator finish;        //表示可用空間的尾iterator end_od_storage;//表示空閑空間的尾
}//simple_alloc配置器的實現(xiàn)
template<class T, class Alloc = alloc>
class simple_alloc{
public://分配空間static T* allocate(size_t n){ return 0 == n ? (T*)Alloc:: allocate(n * sizeof(n)); }static T* allocate(void){ return (T*)Alloc :: allocate(sizeof(T)); }//釋放空間statice T* deallocate(T* p, size_t n){if(0 != n){ Alloc::deallocate(p,n * sizeof(T));}}statice T* deallocate(T* p){ Alloc::deallocate(p,sizeof(n));}
}

---

vector的構(gòu)造函數(shù)和析構(gòu)函數(shù)的實現(xiàn)

? ? ? ? vector作為常用的容器類型，無論是在項目中還是在算法題中常常出現(xiàn)，所以我們對其構(gòu)造函數(shù)并不陌生，以下便是的構(gòu)造函數(shù)和析構(gòu)函數(shù)的實現(xiàn)（PS：千萬不要在容器中存放指針，指針如果是使用new進行分配的，并不能直接通過調(diào)用vector的析構(gòu)函數(shù)對其元素進行釋放，必須得遍歷整個容器依次釋放，否則會存在內(nèi)存泄漏）：

/*  針對代碼中的uninitalized_fill_n()和destroy函數(shù)請參見《STL源碼刨析：空間配置器(allocator)》中內(nèi)存基本處理函數(shù)  *///vector容器的構(gòu)造函數(shù)
vecotr() : start(0), finish(0), end_of_storage(0){}    //列表初始化
vector(int n, const T& value){ fill_initialize(n,value); }
vector(long n,const T& value){ fill_initialize(n,value); }
explicit vector(szie_type n){ fill_initialize(n,T()); }    //explicit用于禁止隱式轉(zhuǎn)換
vector(size_type n, const T& value){ fill_initialize(n,value); }void fill_initialize(size_type n,const T& value){start = allocate_and_fill(n,value);    //使用配置器分配空間finish = start + n;end_of_storage = finish;
}iterator allocate_and_fill(size_type new_size, const T& x){iterator result = data_allocator::allocate(n);    //分配空間uninitalized_fill_n(result,n,x);    return result;
}//vector容器的析構(gòu)函數(shù)
~vector(){destroy(start,finish);deallocate();
}void deallocate(){if(start){data_allocator::deallocate(start, end_of_storage - start);    //釋放空間}
}

---

vector的數(shù)據(jù)結(jié)構(gòu)以及實現(xiàn)源碼

? ? ? ? vector容器的數(shù)據(jù)結(jié)構(gòu)采用的是線性連續(xù)空間，以定義的迭代器start和finish分別指向以及使用的空間的頭部和尾部(范圍)，并以迭代器end_of_storage指向分配的空間的尾部（PS：start和finish指向的是使用的空間，end_of_storage指向的分配的全部空間的尾部），使用這三個迭代器我們將可以使用首尾元素，容器大小，整體容量，空容器的判斷，下標運算符[]，頭元素和尾元素的值的接口函數(shù)，整體實現(xiàn)如下：

//返回頭元素指針
iterator begin(){ return start; }
//返回尾元素指針
iterator end() { return finish; }
//返回容器使用的空間大小
size_type size() const { return szie_type(end() - begin());}
//返回容器的全部空間大小
size_type capacity() const {return size_type(end_of_storage - begin());
}
//返回容器是否為空
bool empty() const { return begin() == end(); }
//返回指定下標的元素
reference operator[](size_type n){ return *(begin() + n); }
//返回容器的頭元素的值
reference front(){ return *begin(); }
//返回容器的尾元素的值
reference back() {return *(end() - 1); }

? ? ? ? 閱讀本段，可能會產(chǎn)生疑問。全部空間是什么？已經(jīng)使用的空間是什么？為什么back返回的值是尾指針-1后的值？針對這些疑問，獲取閱讀下圖便會清晰：

圖1.vector的數(shù)據(jù)結(jié)構(gòu)

? ? ? ? 參考上圖可知，迭代器finish指向的并不是最后一個元素的地址，而是指向最后一個元素的地址的下一個地址。而且size()函數(shù)返回的是已經(jīng)使用的空間大小，capacity()函數(shù)返回的是系統(tǒng)分配的整體空間的大小

---

vector的元素操作

? ? ? ? 關(guān)于vactor容器的元素操作，我們常用的便是push_back()，pop-back()，clear()和insert()，在此基礎(chǔ)上，還要有一個用于清除元素的操作erase()，其中clear()函數(shù)也是調(diào)用的erase()函數(shù)。針對以上的四個函數(shù)實現(xiàn)如下。

? ? ? ? 1.push_back()函數(shù)實現(xiàn)源碼：

//push_back函數(shù)主要用于在容器的尾部插入元素
void push_back()(const T& x){if(finish != end_of_storage){    //存在多余空間construct(finish,x);         //參見《STL源碼刨析：空間配置器(allocator)》，配置器初始化++finish;}elseinsert_aux(end(),x);
}template <class T, class Alloc>
void vector<T,Alloc>::insert_aux(iterator position, const T& x){if(finish != end_of_storage){    //存在多余空間construct(finish,*(finish - 1));++finish;    //調(diào)整尾指針T x_copy = x;copy_bcakward(position,finish - 2,finish - 1);*position = x_copy;}else{    //無多余空間const size_type old_size = size();    //當前使用空間const size_type len = ild_size != 0 ? 2 * old_size : 1;//當前空間為0則分配一個內(nèi)存大小，當前空間不為0則分配2倍的當前空間的大小iterator new_start = data_allocator::allocate(len);iterator new_finish = new_statr;try{    //嘗試將先前的元素拷貝到新申請的空間new_finish = uninitialized_copy(start,positon,new_start);//將原容器中的元素插入新容器construct(new_finish,x);++new_finish;new_finish = uninitialized_copy(position,finish,new_finish);//將新元素插入新容器    }catch(){//捕獲異常destroy(new_start,new_finish);    //釋放分配的空間data_allocator::deallocate(new_start,len);throw;}destory(begin(),end());    //釋放原來容器的空間deallocate();//更新迭代器start = new_start;finish = new_finish;end_of_storage = new_start + len;    }
}

? ? ? ? 2.pop_back()函數(shù)實現(xiàn)源碼：

//pop_back()函數(shù)主要用于將容器尾部的元素刪除
void pop_back(){--finish;destroy(finish);    //使用配置器釋放空間
}

? ? ? ? 3.erase()函數(shù)實現(xiàn)源碼：

//erase()函數(shù)主要用于清除容器中的指定范圍的元素或指定元素
iterator erase(iterator first, iterator last){    //清除容器中[first,last)范圍中的元素iterator i = copy(last,finish,first);    //將last后的元素復制到firstdestroy(i,finish);    //釋放空間finish = finish - (last - first);return finish;
}iterator erase(iterator position){    //清除指定位置的元素if(position + 1 != end())copy(position + 1, finish, position);--finish;destory(finish);return position;
}        

? ? ? ????????? 針對erase()函數(shù)，可參考下圖，直觀了解其實現(xiàn)過程：

圖2.erase()函數(shù)的調(diào)用過程

? ? ? ? 4.clear()函數(shù)實現(xiàn)源碼：

//clear()函數(shù)主要用于將容器的元素刪除
void clear() { erase(begin(),end()); } 

? ? ? ? 5.insert()函數(shù)實現(xiàn)源碼：

//insert()函數(shù)主要用于將容器的元素插入
template<class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x){if(n != 0){    //插入的元素個數(shù)不為0if(size_type(end_of_storage - finish) >= n){    //空閑空間大于插入個數(shù)T x_copy = x;const size_type elems_after = finish - position;    //獲取當前位于插入位置后的元素個數(shù)iterator old_finish = finish;if(elems_after > n){    //插入點后的元素個數(shù)大于插入的元素個數(shù)uninitialized_copy(finish - n, finish, finish);     //將插入點后的元素后移finish += n;copy_backward(position, old_finish - n, old_finish);fill(position,position + n,x_copy);    //從插入點填充新的元素}else{    //插入點后的元素個數(shù)小于等于插入的元素個數(shù)uninitialized_fill_n(finih, n - elems_after, x_copy);//將多出的插入元素填充到空閑內(nèi)存中finish += n;uninitialized_copy(position, old_finish, finish);    //將插入點后的元素后移finish += elems_after;fill(position, old_finish, x_copy);    //將插入的元素填充至插入點}}else{const size_type old_size = size();    //當前容器大小const size_type len = old_size + max(old_size,n);//計算新的容器大小iterator new_start = data_allocator::allocate(len);iterator new_finish = mew_start;_STL_TRY{    //嘗試將元素移動至新的空間new_finish = uninitialized_copy(start,position,new_stars);//將插入點前的當前容器的元素復制到新的空間new_finish = uninitialized_fill_n(new_finish,n,x);//將插入的元素填充至新的空間new_finish = uninitialized_copy(position,finish,new_finish);//將插入點后的當前容器的元素復制到新的空間}#ifdef _STL_USE_EXCEPTIONScatch(...){    //捕獲異常destroy(new_stzrt,new_finish);data_allocator::deallocate(ner_start,len);throw;}#endif /*_STL+USE_EXCEPTIONS*/    //無異常destroy(start,finish);deallocate();start = new_start;finish = new_finish;end_of_atorage = new_start + len;}}
}

---

? ? ? ? 以上便是本章的內(nèi)容，針對insert()函數(shù)，個人覺得關(guān)鍵點在于插入的元素的個數(shù)，如果插入的元素個數(shù)大于當前插入點到尾指針的元素個數(shù)，則向把舊元素分配至新的空間內(nèi)再插入新的元素。如果插入的元素個數(shù)小于等于當前插入點到尾指針的元素個數(shù)，則先將要插入的多出來的元素填充至尾指針后多余的空間內(nèi)，再將舊元素復制到新的空間內(nèi)，最后吧插入的元素再填充進去