C++ STL 概述_嚴絲合縫的合作者們

1. 初識 STL

什麼是STL？

STL（Standard Template Library） 是C++以模板形式提供的一套標準庫，提供了很多開發過程需要的通用功能模組。使用 STL ，可以讓開發者將主要精力用於解決程式的高階業務邏輯，而無須關心底層的基礎邏輯呼叫。

STL 由 6 大部分組成：

• 容器：儲存和組織資料的類別範本，是STL的核心。
• 迭代器：獨立於容器，提供存取容器中資料的通用操作元件。
• 演演算法：提供通用基礎演演算法功能，演演算法通過迭代器對容器中的資料進行查詢、計算……。
• 函數物件：過載了括號運運算元（）的模板類，為演演算法提供靈活的策略。
• 介面卡：通過對已有的容器、迭代器、函數物件進行適配，創造出新的程式設計元件。
• 設定器：為容器服務，負責其記憶體空間的設定與管理。

6大部件遵循單一職責設計思想，元件與元件之間彼此獨立，每一個元件在各自內部高度自治性地實現分配到的功能。

各元件在合作關係上，互為依賴，相互之間形成服務與被服務關係。從而構建出一個精密、靈活、具有高度自適應的程式設計環境。

如下圖為元件之間的分工合作關係：

學習STL包括：

• 瞭解、熟悉各元件的使用。
• 掌握各元件之間的服務關係。

因STL知識體系龐大而複雜，非一言二語能講透。本文僅俯瞰一下STL，對STL有一個大概瞭解，對每一個元件的細節討論將留到系列文章中講解。

下面通過一個簡單的案例初步瞭解容器、迭代器、演演算法、函數物件之間的合作關係。

案例需求：求解一個已知數列中的所有質數（質數：只能被 1 和自身整除的數位）。

設計流程：

• 首先在原始碼檔案的頭部包含程式中需要用到的所有標頭檔案。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

• 認識STL的vector容器，使用它儲存已知數列。

STL中的容器種類繁多，容器之間有共性操作、也存在個體差異性，可適配於不同的應用場景。

在常規操作時，可選擇vector容器，需要包含<vector>標頭檔案。

vector<int> nums= {2,9,10,13,21,5}; 

• 認識迭代器，遍歷容器。迭代器類似於指標，用於存取容器。

//獲取到指向容器第一個資料的迭代器 
vector<int>::iterator begin=nums.begin();
//獲取到指向器結束位置的迭代器，注意，並不是最後一個資料，而是最後一個資料的下一個儲存位置
vector<int>::iterator end=nums.end();
//使用迭代器輸出容器中資料
while(begin!=end){
    cout<<*begin<<"\t";
    begin++;
}  
cout<<endl;

• 認識函數物件，使用函數物件編寫求解質數的演演算法。函數物件可以為STL的演演算法元件提供特定的演演算法策略，演演算法元件充當了平臺功能，利用平臺耦合容器、函數物件。類似於拼搭遊戲，可以有各種可能。

下面程式碼用到了 sqrt函數，需要包含 <cmath> 標頭檔案。

//使用結構體作為函數物件
template <typename T>
struct Zs {
	// 函數物件的特點：過載 () 運運算元
	void operator()(T & x) const {
        //求解質數的演演算法
		bool isZs=true;
		for(T i=2; i<=sqrt(x); i++) {
			if (x % i==0) {
				isZs=false;
				break;
			}
		}
		if(isZs)
            cout<<x<<"是質數"<<endl;
	}
};

• 使用for_each 演演算法 。STL提供了大量演演算法，使用時需要包含 <algorithm>標頭檔案。

//重新指向容器的開始位置（因為前面的操作移動過迭代器） 
begin=nums.begin();
//使用 for_each 演演算法元件
for_each(begin,end,Zs<int>()); 

• 輸出結果。

STL使用了高內聚、低耦合的設計理念，各元件的專業能力非常強，合作時又能做到嚴絲合縫、潤物細無聲。

• 容器專注於資料的儲存。
• 迭代器專注於容器的存取。
• 函數物件提供具體的演演算法策略。
• 演演算法相當於發動機，提供聚合動力。

容器是STL的核心(無資料無程式)元件，且型別繁多，下文將簡要介紹容器的共性操作。

2. 容器

STL中的容器和陣列相似，能夠儲存資料集，但有其自身的特點：

• 支援容量的自動增長。當新增資料時，如果容量不夠時，容器會自動分配新的記憶體。
• 容器可以迭代。
• 支援資料型別引數(泛型程式設計)。

2.1 分類

STL中的容器眾多，有點亂入花叢漸迷眼的既視感。一般會按照儲存方式對其進行分類：

• 序列式容器：資料以新增時的順序進行儲存，當然可以對資料排序。
• 關聯式容器：資料由鍵和值兩部分組成。

2.1.1 序列式容器

序列式容器的儲存方案有 2 種：

• 連續（線性）儲存：基於陣列的儲存方式，資料與資料在記憶體中是相鄰的。

• 鏈式（非線性）儲存：以節點的方式非線性儲存。資料與資料在記憶體中並不一定相鄰，結點之間通過儲存彼此的地址知道對方的位置。

STL中常用到的序列式容器物件：

• vector：向量，線性儲存，類似於陣列。需要包含 <vector>標頭檔案。
• list：雙向連結串列，非線性儲存。需要包含 <list>標頭檔案。
• slist：單向連結串列，非線性儲存。需要包含 <slit>標頭檔案。
• deque：雙向佇列。需要包含<deque>標頭檔案。
• stack：棧，先進後出。需要包含<stack>標頭檔案。
• queue：佇列，資料先進先出。需要包含<queue>標頭檔案。
• priority_queue：優先順序佇列。需要包含<queue>標頭檔案。

2.1.2 關聯式容器

關聯式容器也有 2 種儲存方案：

• 使用搜尋二元樹：容器中的元素依照鍵值進行排序。STL是用紅黑樹實現關聯容器，紅黑樹是一種查詢效率很高的平衡搜尋二元樹。

• 使用雜湊表：對鍵值進行雜湊演演算法，然後根據雜湊值把資料儲存在不同的單元中。

STL中常用的關聯容器：

• set：集合。包含標頭檔案 <set>。
• map：對映。包含標頭檔案<map>。
• multiset：可重複集合。包含標頭檔案<set>。
• multimap：可重複對映。包含標頭檔案<map>。

2.2 容器的通用操作

2.2.1 初始化

使用容器時包含：

• 建立容器。

• 初始化容器。初始化時可以指定容器的容量、為容器指定一系列初始值、為容器中的資料指定比較方法……

初始化序列化容器：

#include <iostream>
#include <vector>
#include <algorithm>
#include <list>
#include <set>
using namespace std;
//使用結構體作為函數物件
int main(int argc, char** argv) {
//初始容量為 12 向量容器
vector<int> vec(12);
cout<<"容器大小："<<vec.size()<<endl;
//初始化長度為 2，且值為 12 、30的向量容器
vector<int> vec1 {12,30};
cout<<"容器大小："<<vec1.size()<<endl;
//構造整型連結串列，初始容量 34
list<int> lst(34);
cout<<"容器大小："<<lst.size()<<endl;
//整型陣列
int ary1[5]= {1,2,3,4,5};
//用陣列初始化
vector<int> vec2(ary1,ary1+5);
cout<<"容器大小："<<vec2.size()<<endl;
//用向量初始化連結串列
list<int> intList(vec.begin(),vec.end());
cout<<"容器大小："<<intList.size()<<endl;
//用連結串列初始化集合
set<int> intSet(lst.begin(),lst.end());
cout<<"容器大小："<<intSet.size()<<endl;
return 0;
}

輸出結果：

初始化map、set容器時。

//建立並初始化集合
set<int> mySet {1,5,3};
//構造 map 容器
map<std::string, int> myMap;
//構造並初始化
std::map<std::string, int>myMap{ {"rose",1},{"jone",2} };
//輸出
for (auto iter = myMap.begin(); iter != myMap.end(); ++iter) {
        cout << iter->first << " " << iter->second << endl;
}

輸出結果：

jone 2
rose 1

2.2.2 新增資料

一般要求容器元件提供對資料進行常規維護的方法（增、刪、改、查……）。

STL為 2類容器提供了insert方法，可以在指定的位置為容器加入新的資料。

這裡需要注意：STL位置一般用迭代器描述，而不是索引位置。

// 初始化向量
vector<int> vec {1, 2, 3, 4, 5};
//開始迭代器
vector<int>::iterator begin=vec.begin();
//結束迭代器
vector<int>::iterator end=vec.end();
cout<<"原向量容器資料"<<endl;
for(; begin!=end; begin++) {
    cout<<*begin<<"\t";
}
//重置開始位置
begin=vec.begin();
// 指向容器vec的第三個元素
begin =begin + 2;
//在位置 3 插入資料
vec.insert( begin, 6 );
//重置開始和結束位置
begin=vec.begin();
end=vec.end();
cout<<"\n插入資料後："<<endl;
for(; begin!=end; begin++) {
    cout<<*begin<<"\t";
}   

輸出結果：

關聯式容器的插入資料效果和序列式容插入效果會有不同。

• 序列式容器中插入資料後，期望位置和最終結果位置是一樣的。如期望插入在第 3 個資料之後，實際也是插入在第 3 個資料之後。
• 關聯式容器會自動按鍵進行位置重排，會出現期望位置和最終位置不一樣的情況（特別在以紅黑樹儲存資料時，為了保持平衡性，會對資料進行平衡處理）。

STL還為序列式容器提供了push、push_back、push_front方法，此方法只能在容器頭或容器尾進行資料新增。

// 宣告一個向量
vector<int> vec(10);
// 壓入資料
vec.push_back(1);
vec.push_back( 1 );
vec.push_back( 2 );
// 宣告一個連結串列
list<int> ls(10);
// 壓入資料
ls.push_back( 1 );
ls.push_front( 2 );
// 宣告一個棧,棧只有 push 方法
stack<string> st;
// 壓入資料
st.push("A");	

2.2.3 刪除資料

STL的容器都有 erase方法，用來刪除指定位置或區間的資料。也提供有clear方法，用來清除整個容器。

位置和區間都需使用迭代器指定。

// 初始化向量 
vector<int> vec  {1, 2, 3, 4, 5, 6};  
//指向容器vec的第三個元素
vector<int>::iterator iter = vec.begin() + 2;
// 刪除第三個元素
vec.erase(iter);   
//指向容器vec的第三個元素               
iter = vec.begin() + 2;     
// 刪除第二個元素之後的所有元素       
vec.erase(iter, vec.end() );  
// 構造一個集合    
set<int> intSet( ary1, ary1+5 );   
// 刪除鍵值為4的元素（集合的鍵值與實值是一致的）
intSet.erase( 4 );                    

2.2.4 查詢資料

序列式容器沒有提供查詢方法，但是，如果某容器類過載了[]運運算元，則可以通過給定資料的索引號找到相應資料，也可以通過 at方式進行查詢。

// 初始化向量 
vector<int> vec  {1, 2, 3, 4, 5, 6};  
int tmp= vec[2];
cout<<tmp<<endl;
//效果上面一樣
tmp= vec.at(2);
cout<<tmp<<endl;

序列式容器一般都會提供front和back方法，用來返回第一個和最後一個資料。因為棧的特殊性，只有top方法用來返回棧頂資料。

vector<int> vec {1, 2, 3, 4, 5, 6};        
list<int> intList( vec.begin(), vec.end() );
//返回第一個資料
x = intList.front();  
//返回最後一個資料
x = intList.back();                  
stack<int,vector<int> > st;    
//返回棧頂資料
x = st.top();

關聯式容器提供有專門的find方法，可通過指定鍵值進行查詢，注意，返回的是用迭代器所描述的位置。

// 整數型陣列
int ary[5] = { 3, 1, 5, 2, 4};        
// 構造集合     
set<int> intSet( ary, ary+5 );   
// 查詢集合中鍵值為4的元素          
set<int>::iterator iter = intSet.find( 4 );
//輸出
cout<<*iter<<endl;

基於元件的分工合作設計思想，容器自身的查詢只會提供一些基本功能。當有更復雜的查詢需求時，可以使用STL演演算法中相應的函數模板進行查詢，例如find，find_if，find_end和find_first_of。

2.2.5 修改資料

可以先查詢到要修改的資料，然後直接修改，如果查詢資料時返回的是迭代器，則可以通過迭代器進行修改。

// 構造向量 
vector<int> vec  { 3, 1, 5, 2, 4};
//直接修改
vec[3] =9;
//[] 反回的是向量資料的參照
int &refTmp=vec[3];
//和前面的直接修改一樣
refTmp=9;

map<int,int>  myMap();
//按鍵值查詢，返回迭代器
map<int,int>::iterator iter=myMap.find(10);
//通過迭代器修改
iter->second=8;
//和上面的效果一樣
myMap[10]=8;

2.2.6 其它方法

• begin ： 返回容器開始位置的迭代器。
• end：返回容器尾部資料後一個儲存位置的迭代器。
• rbegin：求指向容器反向開始元素的迭代器。
• rend：求容器反向結尾元素後一個儲存單元的迭代器。
• swap：交換兩個容器的內容。swap方法用來交換兩個容器的內容。要求兩個容器的型別、大小相同。

//構造兩個向量
vector<int> v1 {1, 2, 3};
vector<int> v2 {4, 5, 6};
//交換兩個向量
v1.swap(v2);
vector<int>::iterator iter = v2.begin();
//輸出向量v2的內容
for(; iter != v2.end(); iter++) {
    cout<<*iter<<endl;
}

• ==、!=、<、<=、>、>=：比較運運算元，判斷兩個容器之間的關係。比較返回結果是第一對不相等資料間的比較結果。如果兩個容器的資料數目不相等，則容器不相等。

// 定義兩個向量
vector <int> v1, v2;
// 在v1中加入資料
v1.push_back( 1 );
v1.push_back( 2 );
v1.push_back( 3 );
// 在v2中加入資料
v2.push_back( 1 );
v2.push_back( 3 );
//返回結果是 V1 第一個資料與 V2 中第一個資料的比較結果
bool res=v1 < v2;
// 輸出1，true 如果 v1 的第一個資料是 4 則，輸出 0
cout<< "v1 < v2：" <<res  <<endl;    

3. 總結

STL是一個龐大且功能非常完善的元件庫，本文僅對其做了一個大概的描述，但是，一葉也能知秋，旨在理順其脈絡，先畫出STL 旅行地圖，然後再一一擊破。