【C++】STL快速入門基礎

文章目錄

STL（Standard Template Library）
- 1、一般介紹
- 2、STL的六大組件
- - 2.1、STL容器
  - 2.2、STL迭代器
  - 2.3、相關容器的函數
  - - vector
    - pair
    - string
    - queue
    - priority_queue
    - stack
    - deque
    - set, map, multiset, multimap
    - unordered_set, unordered_map, unordered_multiset, unordered_multimap
    - bitset
- 3、STL算法概述
- - 查找算法
  - 排序和通用算法
  - 刪除和替換算法
  - 排列組合算法
  - 算術算法
  - 生成和異變算法
  - 關系算法
  - 集合算法
  - 堆算法

STL（Standard Template Library）

1、一般介紹

STL（Standard Template Library）是一個具有工業強度的、高效的C++程序庫，被容納于C++標準程序庫中，是ANSI/ISO C++標準中最新的一部分。STL包含了在計算機科學領域常用的基本數據結構和基本算法，為廣大C++程序員提供了一個可擴展的應用框架，高度體現了軟件的可復用性。

STL在邏輯層次上體現了泛型化程序設計的思想，引入了諸多新的名詞，如需求（requirements）、概念（concept）、模型（model）、容器（container）、算法（algorithmn）、迭代子（iterator）等。與OOP（object-oriented programming）中的多態（polymorphism）一樣，泛型也是一種軟件的復用技術。

在實現層次上，整個STL是以一種類型參數化（type parameterized）的方式實現的，基于一個在早先C++標準中沒有出現的語言特性–模板（template）。如果查閱任何一個版本的STL源代碼，你就會發現，模板作為構成整個STL的基石是一件千真萬確的事情。除此之外，還有許多C++的新特性為STL的實現提供了方便。

2、STL的六大組件

STL的六大組件包括：

容器（Container）：包括序列式容器（Sequence containers）和關聯式容器（Associated containers）。
- 序列式容器：每個元素有固定位置，如vector、deque、list。
- 關聯式容器：元素位置取決于特定的排序準則，如set、multiset、map、multimap。
迭代器（Iterator）：提供訪問容器中對象的方法，包括iterator、const_iterator、reverse_iterator和const_reverse_iterator。
算法（Algorithm）：用于操作容器中的數據，如sort()、find()等，與操作的數據結構和類型無關，可在各種數據結構上使用。
仿函數（Function object）：重載了()操作符的struct，用于自定義操作。
迭代適配器（Adaptor）：用于在不同的迭代器之間進行轉換。
空間配置器（Allocator）：用于對象的創建與銷毀、內存的獲取與釋放。

STL的容器比較包括vector、deque、list、set、multiset、map、multimap等，各自具有不同的特點和適用場景。迭代器模式提供了一種方法順序訪問一個聚合對象中的元素，而不需暴露該對象的內部表示，提高了代碼的靈活性和復用性。

2.1、STL容器

STL（標準模板庫）提供了多種容器，用于存儲和管理數據。常見的STL容器包括以下幾種：

序列式容器（Sequence Containers）：
- vector：動態數組，支持快速隨機訪問，尾部插入/刪除速度快，中間插入/刪除較慢。
- deque：雙端隊列，支持快速隨機訪問，首尾插入/刪除速度快，中間插入/刪除較慢。
- list：雙向鏈表，不支持隨機訪問，任意位置插入/刪除速度快。
關聯式容器（Associative Containers）：
- set：集合，內部元素按照某種規則自動排序，元素值唯一。
- multiset：多重集合，內部元素按照某種規則自動排序，可以有重復元素。
- map：映射，鍵值對集合，內部元素按照鍵值排序，鍵值唯一。
- multimap：多重映射，鍵值對集合，內部元素按照鍵值排序，可以有重復鍵值。
無序關聯式容器（Unordered Associative Containers）：
- unordered_set：無序集合，內部元素不按照特定順序存儲，元素值唯一。
- unordered_multiset：無序多重集合，內部元素不按照特定順序存儲，可以有重復元素。
- unordered_map：無序映射，鍵值對集合，內部元素不按照特定順序存儲，鍵值唯一。
- unordered_multimap：無序多重映射，鍵值對集合，內部元素不按照特定順序存儲，可以有重復鍵值。
容器適配器（Container Adapters）：

? 實際上是容器適配器（container adapter），它們并非真正的容器，而是對底層容器（如vector、deque、list等）進行了封裝，提供了特定的功能接口。
- stack：棧，基于底層容器實現的棧數據結構。
- queue：隊列，基于底層容器實現的隊列數據結構。
- priority_queue：優先隊列，基于堆（heap）實現的優先隊列數據結構。

每種容器都有其特定的使用場景和性能特點，選擇合適的容器可以提高程序的效率和可維護性。

各容器的比較：

容器	數據結構	隨機存取	搜索速度（時間復雜度）	快速插入移除
vector	動態數組	Yes	O(1)	尾部
deque	數組的數組	Yes	O(1)	首尾
list	雙向鏈表	No	O(n)	任何位置
set	紅黑樹	No	O(log n)	–
map	紅黑樹	Yes(key)	O(log n)	–
unordered_map	哈希表	Yes	O(1)	–
unordered_set	哈希表	No	O(1)	–
stack	deque	Yes	O(1)	尾部
queue	deque	Yes	O(1)	首部
priority_queue	vector(heap)	Yes	O(log n)	–

2.2、STL迭代器

Iterator（迭代器）模式又稱Cursor（游標）模式，用于提供一種方法順序訪問一個聚合對象中各個元素,而又不需暴露該對象的內部表示。或者這樣說可能更容易理解：Iterator模式是運用于聚合對象的一種模式，通過運用該模式，使得我們可以在不知道對象內部表示的情況下，按照一定順序（由iterator提供的方法）訪問聚合對象中的各個元素。

迭代器的作用：能夠讓迭代器與算法不干擾的相互發展，最后又能無間隙的粘合起來，重載了***，＋＋，＝＝，！＝，＝**運算符。用以操作復雜的數據結構，容器提供迭代器，算法使用迭代器；

常見的一些迭代器的種類包括：

Input Iterator：從容器中讀取元素，只能一次讀入一個元素向前移動，只支持一遍算法。
Output Iterator：向容器中寫入元素，只能一次一個元素向前移動，只支持一遍算法。
Forward Iterator：組合輸入迭代器和輸出迭代器的功能，并保留在容器中的位置。
Bidirectional Iterator：組合正向迭代器和逆向迭代器的功能，支持多遍算法。
Random Access Iterator：組合雙向迭代器的功能與直接訪問容器中任何元素的功能，可以向前向后跳過任意個元素。

上述5種迭代器的繼承關系如下圖所示：

STL容器迭代器失效情況分析、總結（2）_不要訪問已經刪除的迭代器-CSDN博客

要注意，上面這圖表并不是表明它們之間的繼承關系：而只是描述了迭代器的種類和接口。處于圖表下層的迭代器都是相對于處于圖表上層迭代器的擴張集。例如：forward迭代器不但擁有input和output迭代器的所有功能，還擁有更多的功能。

迭代器一般聲明使用示例

vector<T>::iterator it;
list<T>::iterator it;
deque<T>::iterator it；

每種迭代器均可進行包括表中前一種迭代器可進行的操作

迭代器操作	說明
所有迭代器
`p++`	后置自增迭代器
`++p`	前置自增迭代器
輸入迭代器
`*p`	復引用迭代器，作為右值
`p=p1`	將一個迭代器賦給另一個迭代器
`p==p1`	比較迭代器的相等性
`p!=p1`	比較迭代器的不等性
輸出迭代器
`*p`	復引用迭代器，作為左值
`p=p1`	將一個迭代器賦給另一個迭代器
正向迭代器	提供輸入輸出迭代器的所有功能
雙向迭代器
`--p`	前置自減迭代器
`p--`	后置自減迭代器
隨機迭代器
`p+=i`	將迭代器遞增i位
`p-=i`	將迭代器遞減i位
`p+i`	在p位加i位后的迭代器
`p-i`	在p位減i位后的迭代器
`p[i]`	返回p位元素偏離i位的元素引用
`p<p1`	如果迭代器p的位置在p1前，返回true，否則返回false
`p<=p1`	p的位置在p1的前面或同一位置時返回true，否則返回false
`p>p1`	如果迭代器p的位置在p1后，返回true，否則返回false
`p>=p1`	p的位置在p1的后面或同一位置時返回true，否則返回false

2.3、相關容器的函數

vector

變長數組，采用倍增的思想。
size(): 返回元素個數。
empty(): 返回是否為空。
clear(): 清空容器。
front()/back(): 返回第一個/最后一個元素。
push_back()/pop_back(): 在尾部插入/刪除一個元素。
begin()/end(): 返回迭代器指向容器的起始/末尾位置。
[]: 支持下標訪問，按照順序訪問元素。
支持比較運算，按照字典序排序。

pair

存儲一對值，通常用于存儲一對相關聯的數據。
first: 第一個元素。
second: 第二個元素。
支持比較運算，以first為第一關鍵字，以second為第二關鍵字（按照字典序）。

string

字符串容器。
size()/length(): 返回字符串長度。
empty(): 返回是否為空。
clear(): 清空字符串。
substr(start, length): 返回子串。
c_str(): 返回字符串所在字符數組的起始地址。

queue

隊列容器。
size(): 返回隊列中元素個數。
empty(): 返回是否為空。
push(val): 向隊尾插入一個元素。
front(): 返回隊頭元素。
back(): 返回隊尾元素。
pop(): 彈出隊頭元素。

priority_queue

優先隊列容器，默認是大根堆。
size(): 返回優先隊列中元素個數。
empty(): 返回是否為空。
push(val): 插入一個元素。
top(): 返回堆頂元素。
pop(): 彈出堆頂元素。
可以定義成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;。

stack

棧容器。
size(): 返回棧中元素個數。
empty(): 返回是否為空。
push(val): 向棧頂插入一個元素。
top(): 返回棧頂元素。
pop(): 彈出棧頂元素。

deque

雙端隊列容器。
size(): 返回雙端隊列中元素個數。
empty(): 返回是否為空。
clear(): 清空雙端隊列。
front()/back(): 返回第一個/最后一個元素。
push_back()/pop_back(): 在尾部插入/刪除一個元素。
push_front()/pop_front(): 在頭部插入/刪除一個元素。
begin()/end(): 返回迭代器指向容器的起始/末尾位置。
[]: 支持下標訪問，按照順序訪問元素。

set, map, multiset, multimap

基于平衡二叉樹（紅黑樹）的動態維護有序序列容器。
size(): 返回容器中元素個數。
empty(): 返回是否為空。
clear(): 清空容器。
begin()/end(): 返回迭代器指向容器的起始/末尾位置。
++, --: 返回前驅和后繼，時間復雜度 O(logn)。
insert(): 插入一個元素。
find(): 查找一個元素。
count(): 返回某個元素的個數。
erase(): 刪除元素，支持輸入一個元素值或一個迭代器。
lower_bound()/upper_bound(): 返回大于等于/大于某個值的最小元素的迭代器。

unordered_set, unordered_map, unordered_multiset, unordered_multimap

哈希表容器。
增刪改查的時間復雜度是 O(1)。
不支持 lower_bound()/upper_bound()，迭代器的 ++, --。

bitset

位集合容器，用于處理位操作。
bitset<10000> s;
支持位運算操作 ~, &, |, ^, >>, <<.
支持比較操作 ==, !=.
支持 [] 訪問操作。
count(): 返回有多少個1。
any(): 判斷是否至少有一個1。
none(): 判斷是否全為0。
set(): 把所有位設置為1。
set(k, v): 將第k位設置為v。
reset(): 把所有位設置為0。
flip(): 對所有位取反，等價于 ~。
flip(k): 對第k位取反。

3、STL算法概述

STL（Standard Template Library）算法是C++標準模板庫的核心部分，提供了豐富的算法來操作各種容器。STL算法主要由頭文件<algorithm>, <numeric>, <functional>組成。要使用STL中的算法函數必須包含頭文件<algorithm>，對于數值算法需要包含<numeric>，<functional>中定義了一些模板類，用來聲明函數對象。

STL中的算法大致可以分為以下四類：