[CPP] STL 簡介

STL 即标準模闆庫（Standard Template Library），是 C++ 标準庫的一部分，裡面包含了一些模闆化的通用的資料結構和算法。STL 基于模版的實作，是以能夠支援自定義的資料結構。

STL 中一共有 6 大元件：

容器 (container)
疊代器 (iterator)
算法 (algorithm)
配置設定器 (allocator)
仿函數 (functor)
容器擴充卡 (container adapter)

參考資料：

[1] https://oi-wiki.org/lang/csl/container/
[2] https://en.cppreference.com/w/cpp/container
[3] http://c.biancheng.net/view/409.html

仿函數

仿函數 (Functor) 的本質就是在結構體中重載

()

運算符。

例如：

struct Print
{ void operator()(const char *s) const { cout << s << endl; } };
int main()
{
    Print p;
    p("hello");
}

這一概念将會在

priority_queue

中使用（在智能指針的

unique_ptr

自定義 deleter 也會用到）。

容器

容器 (Container) 在 STL 中又分為序列式容器 (Sequence Containers) ，關聯式容器 (Associative Containers) 和無序容器 (Unorderde Containers) .

序列式容器

常見的序列式容器包括有：

vector, string, array, deque, list, forward_list

vector/string

底層實作：

vector

是記憶體連續、自動擴容的數組，實質還是定長數組。

特點：

随機通路：重載 [] 運算符
動态擴容：插入新元素前，如果 size == capacity 時，那麼擴容為目前容量的 2 倍，并拷貝原來的資料
支援 ==, !=, <, <=, >, >= 比較運算
- C++20 前，通過上述 6 個重載運算符實作；C++20中，統一「封裝」為一個 <=> 運算符 (aka, three-way comparsion )。
- 不難了解，時間複雜度為 \(O(n)\) 。

PS：

string

的底層實作與

vector

是類似的，同樣是記憶體連續、自動擴容的數組（但擴容政策不同）。

array (C++11)

底層實作：

array

是記憶體連續的、固定長度的數組，其本質是對原生數組的直接封裝。

特點（主要是與

vector

比較）：

支援 6 種比較運算符，支援 [] 随機通路
丢棄自動擴容，以獲得跟原生數組一樣的性能
不支援 pop_front/back, erase, insert 這些操作。
長度在編譯期确定。 vector 的初始化方式為函數參數（如 vector<int> v(10, -1) ，長度可動态确定），但 array 的長度需要在編譯期确定，如 array<int, 10> a = {1, 2, 3} .

需要注意的是，

array

的

swap

方法複雜度是 \(\Theta(n)\) ，而其他 STL 容器的

swap

是 \(O(1)\)，因為隻需要交換一下指針。

deque

又稱為“雙端隊列”。

底層實作：多個不連續的緩沖區，而緩沖區中的記憶體是連續的。而每個緩沖區還會記錄首指針和尾指針，用來标記有效資料的區間。當一個緩沖區填滿之後便會在之前或者之後配置設定新的緩沖區來存儲更多的資料。

特點：

支援 [] 随機通路
線性複雜度的插入和删除，以及常數複雜度的随機通路。

list

底層實作：雙向連結清單。

特點：

不支援 [] 随機通路
常數複雜度的插入和删除

forwar_list (C++11)

底層實作：單向連結清單。

特點：

相比 list 減少了空間開銷
不支援 [] 随機通路
不支援反向疊代 rbegin(), rend()

關聯式容器

關聯式容器包括：

set/multiset

，

map/multimap

。

multi

表示鍵值可重複插入容器。

底層實作：紅黑樹。

特點：

内部自排序，搜尋、移除和插入擁有對數複雜度。
對于任意關聯式容器，使用疊代器周遊容器的時間複雜度均為 \(O(n)\) 。

自定義比較方式：

如果是自定義資料類型，重載運算符 <
如果是 int 等内置類型，通過仿函數

struct cmp { bool operator()(int a, int b) { return a > b; } };
set<int, cmp> s;

無序容器

無序容器 (Unorderde Containers) 包括：

unordered_set/unordered_multiset

unordered_map/unordered_multimap

底層實作：哈希表。在标準庫實作裡，每個元素的散列值是将值對一個質數取模得到的，

特點：

内部元素無序
在最壞情況下，對無序關聯式容器進行插入、删除、查找等操作的時間複雜度會與容器大小成線性關系。這一情況往往在容器内出現大量哈希沖突時産生。

在實際應用場景下，假設我們已知鍵值的具體分布情況，為了避免大量的哈希沖突，我們可以自定義哈希函數（還是通過仿函數的形式）。

struct my_hash { size_t operator()(int x) const { return x; } };
unordered_map<int, int, my_hash> my_map;
unordered_map<pair<int, int>, int, my_hash> my_pair_map;

小結

四種操作的平均時間複雜度比較：

增：在指定位置插入元素
删：删除指定位置的元素
改：修改指定位置的元素
查：查找某一進制素

Containers	底層結構	增	删	改	查
`vector/deque`	vector: 動态連續記憶體 deque: 連續記憶體+連結清單	\(O(n)\)	\(O(n)\)	\(O(1)\)	\(O(n)\)
`list`	雙向連結清單	\(O(1)\)	\(O(1)\)	\(O(1)\)	\(O(n)\)
`forward_list`	單向連結清單	\(O(1)\)	\(O(n)\)	\(O(1)\)	\(O(n)\)
`array`	連續記憶體	不支援	不支援	\(O(1)\)	\(O(n)\)
`set/map/multiset/multimap`	紅黑樹	\(O(\log{n})\)	\(O(\log{n})\)	\(O(\log{n})\)	\(O(\log{n})\)
`unordered_{set,multiset}` `unordered_{map,multimap}`	哈希表	\(O(1)\)	\(O(1)\)	\(O(1)\)	\(O(1)\)

容器擴充卡

容器擴充卡 (Container Adapter) 其實并不是容器（個人了解是對容器的一種封裝），它們不具有容器的某些特點（如：有疊代器、有

clear()

函數……）。

常見的擴充卡：

stack

，

queue

，

priority_queue

。

對于擴充卡而言，可以指定某一容器作為其底層的資料結構。

stack

預設容器： deque
不支援随機通路，不支援疊代器
top, pop, push, size, empty 操作的時間複雜度均為 \(O(1)\) 。

指定容器作為底層資料結構：

stack<TypeName, Container> s;  // 使用 Container 作為底層容器

queue

預設容器： deque
不支援随機通路，不支援疊代器
front, push, pop, size, empty 操作的時間複雜度均為 \(O(1)\) 。

指定容器：

queue<int, vector<int>> q;

priority_queue

又稱為 “優先隊列” 。

預設容器： vector
\(O(1)\)： top, empty, size
\(O(\log{n})\) : push, pop

模版參數解析：

priority_queue<T, Container = vector<T>, Compare = less<T>> q;
// 通過 Container 指定底層容器，預設為 vector
// 通過 Compare 自定義比較函數，預設為 less，元素優先級大的在堆頂，即大頂堆
priority_queue<int, vector<int>, greater<int>> q;
// 傳入 greater<int> 那麼将構造一個小頂堆
// 類似的，還有 greater_equal, less_equal

疊代器

疊代器 (Iterator) 實際上也是 GOF 中的一種設計模式：提供一種方法順序通路一個聚合對象中各個元素，而又不需暴露該對象的内部表示。

疊代器的分類如下圖所示。

各容器的疊代器

STL 中各容器/擴充卡對應使用的疊代器如下表所示。

Container	Iterator
array	随機通路疊代器
vector	随機通路疊代器
deque	随機通路疊代器
list	雙向疊代器
set / multiset	雙向疊代器
map / multimap	雙向疊代器
forward_list	前向疊代器
unordered_{set, multiset}	前向疊代器
unordered_{map, multimap}	前向疊代器
stack	不支援疊代器
queue	不支援疊代器
priority_queue	不支援疊代器

疊代器失效

疊代器失效是因為向容器插入或者删除元素導緻容器的空間變化或者說是次序發生了變化，使得原疊代器變得不可用。是以在對 STL 疊代器進行增删操作時，要格外注意疊代器是否失效。

網絡上搜尋「疊代器失效」，會發現很多這樣的例子，在一個

vector

中去除所有的 2 和 3，故意用一下疊代器掃描（大家都知道可以用下标）：

int main()
{
    vector<int> v = {2, 3, 4, 6, 7, 8, 9, 3, 2, 2, 2, 2, 3, 3, 3, 4, 5, 6};
    for (auto i = v.begin(); i != v.end(); i++)
    {
        if (*i==2 || *i==3) v.erase(i), i--;
        // correct code should be
        // if (*i==2 || *i==3) i=v.erase(i), i--;
    }
    for (auto i = v.begin(); i != v.end(); i++)
        cout << *i << ' ';
}

我很久之前用 Dev C++ （應該是内置了很古老的 MinGW）寫代碼的時候，印象中也遇到過這種情況，

v.erase(i), i--

這樣的操作是有問題的。

erase(i)

會使得

及其後面的疊代器失效，進而發生段錯誤。

但現在 MacOS (clang++ 12), Ubuntu16 (g++ 5.4), Windows (mingw 9.2) 上測試，這段代碼都沒有問題，并且能輸出正确結果。編譯選項為：

g++ test.cpp -std=c++11 -O0

實際上也不難了解，因為是連續記憶體，

指向的記憶體位置，在

erase

之後被其他資料覆寫了（這裡的行為就跟我們使用普通數組一樣），但該位置仍然在

vector

的有效範圍之内。在上述代碼中，當

i = v.begin()

時，執行

erase

後，對

進行自減操作，這已經是一種未定義行為。

我猜應該是 C++11 後（或者是後來的編譯器更新），對疊代器失效的這個問題進行了優化。

雖然能夠正常運作，但我認為最好還是嚴謹一些，更嚴格地遵循疊代器的使用規則：

if (*i==2 || *i==3) i=v.erase(i), i--;

以下為各類容器可能會發生疊代器失效的情況：

數組型 ( vector, deque )
- insert(i) 和 erase(i) 會發生資料挪動，使得 i 後的疊代器失效，建議使用 i = erase(i) 擷取下一個有效疊代器。
- 記憶體重新配置設定：當 vector 自動擴容時，可能會申請一塊新的記憶體并拷貝原資料（也有可能是在目前記憶體的基礎上，再擴充一段連續記憶體），是以所有的疊代器都将失效。
連結清單型 ( list, forward_list )： insert(i) 和 erase(i) 操作不影響其他位置的疊代器， erase(i) 使得疊代器 i 失效，指向資料無效， i = erase(i) 可獲得下一個有效疊代器，或者使用 erase(i++) 也可（在進入 erase 操作前已完成自增）。
樹型 ( set/map )：與連結清單型相同。
哈希型 ( unodered_{set_map} )：與連結清單型相同。