文章目錄
-
- 前言
- 資源介紹
- STL概述
-
- STL可不止有容器
- STL的序列式容器容器
-
- Vector
- List
前言
其實我剛開始也沒想到會寫這麼快，明顯後面幾篇的資料跟不上第一篇啦。可能是有一部分朋友對CSDN還不是很了解吧。
在文中的藍字是可以點選的超連結，在文章标題下面有文章所屬專欄，也是可以點選的，我這一系列的文章都在一個專欄下：
開發成長之路
你們可以慢慢看，不懂的随時私信我，我在CSDN上還是比較活躍的，一般一個小時内都能回複。
這個專欄你們可以放心，我絕對不會設定成付費專欄的。畢竟這兒是我最開始接觸程式設計的地方，夢想開始的地方。
資源介紹
STL方面的知識，我也不藏着掖着，我就是“搬運工”，從侯捷老師的《STL源碼剖析》中學習，再轉述。
如果想要深入了解C++程式設計之美，一要看設計模式，二要看侯捷老師的書。
這本書我看了三遍，寫了一個專欄，後來被删的差不多了。
因為經常翻新。
這一篇，我先挑最簡單的“使用方法”來講講。
STL概述
STL，雖然是一套程式庫，但卻不僅僅是一套一般印象中的程式庫，而是一個具有劃時代意義的、有着深厚理論基礎的發明。
說是軟體元件史上的一大突破，也當之無愧。
為了建立資料結構與算法的一套标準，降低其間的耦合關系，以及提升各自的互動性、彈性、獨立性，C++社群中誕生了STL.
STL是一個開源項目，是以有很多個版本。我講解及使用的是SGI STL版本，不論是符号命名，還是編碼風格上，這個版本的可讀性非常高。
STL可不止有容器
對于大部分接觸過STL的人來說，對于STL的印象應該是極好的，不過大部分人可能也是簡單的将容器和STL的全部畫起了等号，最多再加上算法，畢竟我們使用STL常用到的也就那兩套頭檔案。說實話我也前也是這麼認為的。
其實STL提供了六大元件，容器和算法隻是其中一部分，它們分别是：
容器、算法、疊代器、仿函數、配接器、配置器。
這些元件都是什麼？
不要急，就算知道也再看一遍吧。
- 容器
- 各種資料結構，如Vector、List、Map，用于存放資料。
- 算法
- 各種常見算法如：排序、增删查等。從實作來看，STL算法屬于泛型函數。
- 疊代器
- 很驚奇，疊代器不屬于容器，也不屬于算法。
- 扮演起容器與算法之間的“粘合劑”，是“泛型指針”。
- 原生指針可以作為一種疊代器，不過疊代器一般是以智能指針的形式存在的。
- 仿真函數
- 行為類似函數，從實作來看是一種重載了operator()的類或模闆類。
- 函數指針可視為狹義上的仿真函數。
- 配接器
- 說來話長，一種用于修飾容器、疊代器、仿真函數的東西。
- 配置器
- 空間配置與管理，如果要深入了解STL代碼，則這一塊将會是奠基石一般的存在。
來看一下STL六大元件聯合工作的圖示：
STL的序列式容器容器
源碼之前，了無秘密
曾經面試官問過我這麼一個問題：請你描述一下，STL中的所有容器，它們的底層實作機制、它們增删查改的時間複雜度是多少。
當時回答的迷迷糊糊的。本篇，就圍繞這個話題展開。
Vector
什麼是Vector？可以了解為是動态數組。
Vector所采用的資料結構非常簡單，連續線性空間。
template <class T,class Alloc * alloc> //模闆，後面會專門出一篇寫C++的模闆程式設計
class vector{
···
protected:
iterator start; //表示目前使用空間的頭
iterator finish; //表示目前使用空間的尾
iterator end_of_storage; //表示目前可用的空間的尾
···
} 複制
為了降低空間配置的時間成本，vector實際配置的大小可能會比用戶端需求的量更大一些，以備将來擴充的可能。
看圖：
運用這三個算子，可以很輕易的實作一些功能：
template <class T,class Alloc * alloc>
class vector{
···
public:
iterator begin(){return start;}
iterator end(){return finish;}
size_type size() const{return size_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);}
//傳回首尾位址
···
} 複制
再來看一些常用函數的底層實作：
void push_back(const T& x){
if(finish != end_of_storage){ //還有備用空間
construct(finish,x); //一個插入函數，暫時知道這個就夠了，偏底層
++finish;
}
else{ //空間不夠用了
insert_aux(end(),x); //更底層了，看上面那張圖
}
} 複制
注意：一旦引起空間重新配置，指向原Vector的所有疊代器都将失效！！！
pop_back() 删除末端元素：
void pop_back(){
--finish;
destroy(finish); //這個destory後面講空間配置器的時候會講到
//就是這麼簡單
} 複制
erase() 清除（first，last）中所有元素：
先看圖：
iterator erase(iterase first,iterase last){
iterator i = copy(last,finish,first) //copy後面的篇章會有，先克服一下困難
destroy(i,finish);
finish = finish - (last - first);
return first;
} 複制
erase() 清除某個位置上的元素：
iterator erase(iterator position){
if(position +1 != end())
copy(position +1,finish,position)
--finish;
destroy(finish);
return position;
} 複制
clear() 方法：
void clear(){
erase(begin(),end());
} 複制
insert() 插入操作：
這個操作的代碼實在是太多的底層細節了，還是看圖吧：
List
Vector可以用數組的知識來覆寫，那麼List，就用連結清單的知識來覆寫吧。
這裡要注意：
list對于任何元素的插入和删除，永遠都是常數時間，我也得去一探究竟啦，我當初回答錯了。
先看看資料結構：
template <class T>
struct __list_node{
typedef void* void_pointer;
void_pointer prev;
void_pointer next;
T data;
} 複制
雙向連結清單！！！
list的疊代器和vector的不同，它的要求更高一些。因為連結清單使用的存儲空間往往是零零散散的，是以list的疊代器必須有能力在雜亂的存儲空間中快速的跳轉。
相對于Vector，List還有一個優勢，就是不論如何的插入和接合操作，都不會造成原有的List疊代器失效。List的删除操作也隻有指向那個被删除的元素的疊代器失效，其它疊代器不會受影響。
SGI list不僅僅是一個雙向連結清單，還是個環狀雙向連結清單，是以它隻需要一個指針，便可以完整的表現連結清單。
template <class T,class Alloc = alloc> //預設使用alloc作為配置器
class list{
protected:
typedef __list_node<T> list_node;
public:
typedef list_node* link_type;
protected:
link_type node; //隻要一個指針，便可以表示整個循環連結清單 複制
如果讓指針node指向刻意置于尾端的一個空白節點，node便能符合STL對于“前閉後開”的區間要求，成為list疊代器。
iterator begin(){return (link_type)((*node).next);}
iterator end(){return node;}
bool empty() const{return node->next == node;}
size_type size() const{
size_type result = 0;
disance(begin(),end(),result); //一個全局函數
return result;
}
reference front(){return *begin();}
reference back(){return *--end();} 複制
關于list的增删改查，其實跟連結清單也就差不多了。
一篇講兩個容器，寫多了怕是大家也看不下去了，那麼今天就寫到這裡啦。
明天我們再會。