總結C++中的STL

1.STL 概述

STL 即標準模板庫，是 C++ 標準程序庫的重要組成部分，包含常用數據結構和算法，體現了泛型化程序設計思想，基于模板實現，提高了代碼的可復用性

2.容器

2.1 序列容器：

? 1.? vector

特性：動態數組，內存連續分配。隨著元素的添加，若內存空間不足，會重新分配更大的內存塊，并將原有元素復制過去。
優缺點：優點是支持隨機訪問，可通過下標快速訪問任意位置的元素；在尾部插入和刪除元素效率高。缺點是在中間或頭部插入和刪除元素效率低，因為需要移動后續元素。
常用操作：
```
#include <vector>
#include <iostream>
int main() {std::vector<int> vec;vec.push_back(10); // 尾部插入元素vec.insert(vec.begin(), 5); // 在開頭插入元素std::cout << vec[1] << std::endl; // 隨機訪問元素vec.pop_back(); // 尾部刪除元素return 0;
}
```
2. deque
- 特性：雙端隊列，由多個固定大小的數組塊組成，支持在兩端快速插入和刪除元素，同時也支持隨機訪問。
- 優缺點：優點是在兩端插入和刪除元素的時間復雜度為常數，適合需要頻繁在兩端操作的場景。缺點是隨機訪問的效率略低于?vector。
- 常用操作：

#include <deque>
#include <iostream>
int main() {std::deque<int> dq;dq.push_front(1); // 頭部插入元素dq.push_back(2); // 尾部插入元素std::cout << dq[0] << std::endl; // 隨機訪問元素dq.pop_front(); // 頭部刪除元素return 0;
}

? ? ? ? 3. list

特性：雙向鏈表，每個節點包含數據和指向前一個節點和后一個節點的指針。
優缺點：優點是在任意位置插入和刪除元素的時間復雜度為常數，適合頻繁插入和刪除的操作。缺點是不支持隨機訪問，訪問元素需要從頭或尾開始遍歷。
常用操作：

#include <list>
#include <iostream>
int main() {std::list<int> lst = {1, 2, 3};auto it = lst.begin();++it;lst.insert(it, 4); // 在指定位置插入元素lst.erase(it); // 刪除指定位置元素for (int i : lst) {std::cout << i << " ";}return 0;
}

2.2 關聯容器：

1.set

特性：元素唯一且有序，底層通常實現為紅黑樹（一種自平衡二叉搜索樹）。插入、刪除和查找元素的時間復雜度為?O(logn)。
優缺點：優點是元素自動排序，且能保證元素的唯一性。缺點是插入和查找操作的時間復雜度不是常數級。
常用操作：

#include <set>
#include <iostream>
int main() {std::set<int> s;s.insert(3);s.insert(1);auto it = s.find(1); // 查找元素if (it != s.end()) {std::cout << "Found" << std::endl;}return 0;
}

2.multiset

特性：與?set?類似，但允許元素重復。
常用操作：基本與?set?相同，只是插入重復元素時不會被忽略。

3.map

特性：鍵值對的集合，鍵唯一且有序，底層同樣是紅黑樹。可通過鍵快速查找對應的值。
優缺點：優點是查找和插入操作的時間復雜度為?O(logn)，且能保證鍵的有序性。缺點是空間開銷較大。
常用操作：

#include <map>
#include <iostream>
#include <string>
int main() {std::map<std::string, int> m;m["apple"] = 10; // 插入鍵值對auto it = m.find("apple"); // 查找鍵if (it != m.end()) {std::cout << it->second << std::endl; // 輸出對應的值}return 0;
}

4.multimap

特性：與?map?類似，但允許鍵重復。

2.2 無序容器

? ?1.unordered_set

特性：無序集合，元素唯一，底層實現為哈希表。插入、刪除和查找元素的平均時間復雜度為?O(1)。
優缺點：優點是查找和插入操作的平均時間復雜度為常數級。缺點是元素無序，且哈希沖突可能會影響性能。
常用操作：

#include <unordered_set>
#include <iostream>
int main() {std::unordered_set<int> us;us.insert(3);auto it = us.find(3); // 查找元素if (it != us.end()) {std::cout << "Found" << std::endl;}return 0;
}

2.unordered_multiset

特性：與?unordered_set?類似，但允許元素重復。

3.unordered_map

特性：無序鍵值對集合，底層為哈希表。適合快速查找鍵對應的值。
常用操作：

#include <unordered_map>
#include <iostream>
#include <string>
int main() {std::unordered_map<std::string, int> um;um["apple"] = 10; // 插入鍵值對auto it = um.find("apple"); // 查找鍵if (it != um.end()) {std::cout << it->second << std::endl; // 輸出對應的值}return 0;
}

4.unordered_multimap

特性：與?unordered_map?類似，但允許鍵重復。

3. 迭代器（Iterators）

3.1 輸入迭代器

特性：只能用于讀取容器中的元素，不支持寫入操作，且只能單向移動，每次移動一步。例如?find?算法使用輸入迭代器來查找元素。

#include <vector>
#include <algorithm>
#include <iostream>
int main() {std::vector<int> vec = {1, 2, 3};auto it = std::find(vec.begin(), vec.end(), 2);if (it != vec.end()) {std::cout << *it << std::endl;}return 0;
}

3.2 輸出迭代器

特性：只能用于向容器中寫入元素，不支持讀取操作，同樣只能單向移動，每次移動一步。例如?copy?算法使用輸出迭代器將元素從一個容器復制到另一個容器。

#include <vector>
#include <algorithm>
#include <iostream>
int main() {std::vector<int> src = {1, 2, 3};std::vector<int> dest(3);std::copy(src.begin(), src.end(), dest.begin());for (int i : dest) {std::cout << i << " ";}return 0;
}

3.3 前向迭代器

特性：支持讀取和寫入操作，并且可以向前移動，允許多次遍歷容器。例如?forward_list?的迭代器就是前向迭代器。

#include <forward_list>
#include <iostream>
int main() {std::forward_list<int> fl = {1, 2, 3};for (auto it = fl.begin(); it != fl.end(); ++it) {*it *= 2; // 寫入操作}for (int i : fl) {std::cout << i << " ";}return 0;
}

3.4 雙向迭代器

特性：支持讀取、寫入和雙向移動，可用于雙向鏈表等數據結構。例如?list?的迭代器就是雙向迭代器。

#include <list>
#include <iostream>
int main() {std::list<int> lst = {1, 2, 3};auto it = lst.end();--it; // 反向移動std::cout << *it << std::endl;return 0;
}

3.5.隨機訪問迭代器

特性：支持隨機訪問，可通過下標快速訪問任意位置的元素，還支持雙向移動和跳躍移動。例如?vector?的迭代器就是隨機訪問迭代器。

#include <vector>
#include <iostream>
int main() {std::vector<int> vec = {1, 2, 3};auto it = vec.begin() + 2; // 跳躍移動std::cout << *it << std::endl;return 0;
}

4.算法

4.1 排序算法：

1.sort

功能：對指定范圍內的元素進行排序，默認使用升序排序。
示例：

#include <vector>
#include <algorithm>
#include <iostream>
int main() {std::vector<int> vec = {3, 1, 2};std::sort(vec.begin(), vec.end());for (int i : vec) {std::cout << i << " ";}return 0;
}

2.stable_sort

功能：與?sort?類似，但能保證相等元素的相對順序不變。

4.2 查找算法：

1.find

功能：在指定范圍內查找指定值的元素，返回第一個匹配元素的迭代器。
示例：

#include <vector>
#include <algorithm>
#include <iostream>
int main() {std::vector<int> vec = {1, 2, 3};auto it = std::find(vec.begin(), vec.end(), 2);if (it != vec.end()) {std::cout << "Found" << std::endl;}return 0;
}

2.binary_search

功能：在有序范圍內進行二分查找，判斷指定值是否存在。
示例：

#include <vector>
#include <algorithm>
#include <iostream>
int main() {std::vector<int> vec = {1, 2, 3};bool found = std::binary_search(vec.begin(), vec.end(), 2);if (found) {std::cout << "Found" << std::endl;}return 0;
}

4.3 遍歷算法：

1. for_each：對容器中的每個元素執行指定的函數或函數對象。

#include <vector>
#include <algorithm>
#include <iostream>
void print(int i) {std::cout << i << " ";
}
int main() {std::vector<int> vec = {1, 2, 3};std::for_each(vec.begin(), vec.end(), print);return 0;
}

2. transform：將一個容器中的元素按照指定的規則轉換為另一個容器中的元素。

4.4 數值算法：

1. accumulate：計算容器中元素的總和，還可以指定一個初始值，時間復雜度為?O(n)。

示例：

#include <vector>
#include <numeric>
#include <iostream>
int main() {std::vector<int> vec = {1, 2, 3};int sum = std::accumulate(vec.begin(), vec.end(), 0);std::cout << sum << std::endl;return 0;
}

2. inner_product：計算兩個容器對應元素的乘積之和，可用于計算向量的內積等。

4.5.仿函數

仿函數是一個重載了函數調用運算符?()?的類或結構體。

可以像函數一樣被調用，并且可以攜帶狀態信息。

在 STL 算法中，常作為參數來定制算法的行為，例如定義比較規則、計算規則等。

1.一元仿函數

示例：定義一個仿函數用于判斷元素是否為偶數。

#include <vector>
#include <algorithm>
#include <iostream>
struct IsEven {bool operator()(int num) const {return num % 2 == 0;}
};
int main() {std::vector<int> vec = {1, 2, 3};auto it = std::find_if(vec.begin(), vec.end(), IsEven());if (it != vec.end()) {std::cout << *it << std::endl;}return 0;
}

2.二元仿函數

示例：定義一個仿函數用于降序排序。

#include <vector>
#include <algorithm>
#include <iostream>
struct GreaterThan {bool operator()(int a, int b) const {return a > b;}
};
int main() {std::vector<int> vec = {1, 2, 3};std::sort(vec.begin(), vec.end(), GreaterThan());for (int i : vec) {std::cout << i << " ";}return 0;
}

6.適配器

6.1 容器適配器：

1.stack：棧適配器，基于 deque 或 vector 實現，提供了后進先出（LIFO）的存儲方式。

常用操作：

#include <stack>
#include <iostream>
int main() {std::stack<int> st;st.push(1);st.push(2);std::cout << st.top() << std::endl; // 訪問棧頂元素st.pop(); // 彈出棧頂元素return 0;
}

2.queue：隊列適配器，基于 deque 實現，提供了先進先出（FIFO）的存儲方式。

常用操作：

#include <queue>
#include <iostream>
int main() {std::queue<int> q;q.push(1);q.push(2);std::cout << q.front() << std::endl; // 訪問隊首元素q.pop(); // 彈出隊首元素return 0;
}

3.priority_queue：優先隊列適配器，基于 vector 實現，元素按照優先級進行存儲和訪問。

常用操作：

#include <queue>
#include <iostream>
int main() {std::priority_queue<int> pq;pq.push(3);pq.push(1);std::cout << pq.top() << std::endl; // 訪問隊首元素pq.pop(); // 彈出隊首元素return 0;
}

6.2 迭代器適配器：

1.reverse_iterator：反向迭代器，用于反向遍歷容器，通過將正向迭代器進行封裝，實現了與正向迭代器相反的遍歷順序。

示例：

#include <vector>
#include <iostream>
int main() {std::vector<int> vec = {1, 2, 3};for (auto it = vec.rbegin(); it != vec.rend(); ++it) {std::cout << *it << " ";}return 0;
}

2.back_insert_iterator：后插入迭代器，用于在容器尾部插入元素，常用于將元素插入到一個動態增長的容器中。

6.3 仿函數適配器：

1.bind：用于綁定仿函數的參數，將一個多參數的仿函數轉換為一個少參數的仿函數。

示例：

#include <iostream>
#include <functional>
int add(int a, int b) {return a + b;
}
int main() {auto add5 = std::bind(add, 5, std::placeholders::_1);std::cout << add5(3) << std::endl; // 輸出 8return 0;
}