C++ STL 基礎與多線程安全性說明文檔

一、STL 簡介

STL（Standard Template Library，標準模板庫）是 C++ 標準庫的重要組成部分，提供了常用的數據結構和算法的泛型實現，極大地提高了代碼的復用性和開發效率。

STL 的六大組件

1. 容器（Containers）：如 vector、list、deque、set、map、unordered_map 等，用于存儲數據。
2. 算法（Algorithms）：如 sort、find、for_each 等，作用于容器。
3. 迭代器（Iterators）：提供一種統一方式遍歷容器元素，是容器與算法之間的橋梁。
4. 函數對象（Function Objects / Functors）：可作為算法的參數，具有函數調用運算符。
5. 適配器（Adapters）：對容器或函數進行包裝，如 stack、queue、priority_queue、bind。
6. 分配器（Allocators）：內存分配策略的封裝，一般使用默認即可。

---

二、STL 容器性能對比

常見 STL 容器性能分析

容器	插入	刪除	查找	隨機訪問	是否排序	是否允許重復
vector	尾部 O(1)，中間 O(n)	O(n)	O(n)	O(1)	否	是
list	任意位置 O(1)*	O(1)*	O(n)	否	否	是
deque	頭尾 O(1)，中間 O(n)	O(n)	O(n)	O(1)	否	是
set / map	O(log n)（紅黑樹）	O(log n)	O(log n)	否	是	否
unordered_set / unordered_map	平均 O(1)，最壞 O(n)	O(1)	O(1)	否	否	否
stack / queue / priority_queue	O(1) 或 O(log n)	O(1) 或 O(log n)	無查找	否	否	N/A

注：list 的插入/刪除在給定迭代器位置下是 O(1)，但查找該位置是 O(n)

推薦使用場景

場景需求	推薦容器
快速插入刪除，頻繁操作兩端	deque、list
快速尾部插入和隨機訪問	vector
快速查找，自動排序	set、map
快速查找，順序無關	unordered_set、unordered_map
需要先進先出 / 后進先出	queue、stack
需要大頂堆、小頂堆	priority_queue

Demo: 查找性能對比

#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <chrono>using namespace std;
using namespace std::chrono;const int N = 1e6;
int target = N - 1;int main() {vector<int> v;set<int> s;unordered_set<int> us;for (int i = 0; i < N; ++i) {v.push_back(i);s.insert(i);us.insert(i);}auto t1 = high_resolution_clock::now();auto it1 = find(v.begin(), v.end(), target);auto t2 = high_resolution_clock::now();cout << "vector find time: " << duration_cast<microseconds>(t2 - t1).count() << "us" << endl;t1 = high_resolution_clock::now();auto it2 = s.find(target);t2 = high_resolution_clock::now();cout << "set find time: " << duration_cast<microseconds>(t2 - t1).count() << "us" << endl;t1 = high_resolution_clock::now();auto it3 = us.find(target);t2 = high_resolution_clock::now();cout << "unordered_set find time: " << duration_cast<microseconds>(t2 - t1).count() << "us" << endl;return 0;
}

---

三、STL 容器的多線程安全性分析

STL 容器線程安全原則

• ? 只讀共享是安全的（多個線程只讀）
• ? 寫入操作必須加鎖保護
• ? 多線程同時修改同一個容器是危險的

各容器線程安全性對比

容器	多線程只讀	多線程寫入	是否自帶同步
vector	? 安全	? 不安全	? 無同步
map / set	? 安全	? 不安全	? 無同步
unordered_map	? 安全	? 不安全	? 無同步
queue / stack	? 一般不安全	? 不安全	? 無同步

常見錯誤示例

#include <vector>
#include <thread>std::vector<int> v;void writer() {for (int i = 0; i < 10000; ++i) {v.push_back(i);  // ? 非線程安全}
}int main() {std::thread t1(writer);std::thread t2(writer);t1.join();t2.join();return 0;
}

正確寫法：加鎖保護

#include <vector>
#include <mutex>
#include <thread>std::vector<int> v;
std::mutex mtx;void safe_writer() {for (int i = 0; i < 10000; ++i) {std::lock_guard<std::mutex> lock(mtx);v.push_back(i);}
}

替代方案與推薦庫

目標	替代建議
并發隊列	boost::lockfree::queue、TBB、Folly、MoodyCamel
并發哈希表	tbb::concurrent_hash_map、libcds
自定義多線程容器封裝	封裝 std::mutex 或使用 shared_mutex

---

四、最佳實踐

• 所有寫操作務必加鎖，或使用原子容器
• 避免在遍歷期間修改容器
• 如果性能要求高，考慮使用專用并發容器庫
• 使用 condition_variable + mutex 實現生產者消費者模型