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

2022 年 9 月 28 日
筆記
C++, C++編程之美

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 旅行地圖，然後再一一擊破。

Tags: C++ C++編程之美