C++ STL 基础与多线程安全性说明文档
一、STL 简介
STL（Standard Template Library，标准模板库）是 C++ 标准库的重要组成部分，提供了常用的数据结构和算法的泛型实现，极大地提高了代码的复用性和开发效率。
STL 的六大组件
- 容器（Containers）：如
vector、list、deque、set、map、unordered_map 等，用于存储数据。
- 算法（Algorithms）：如
sort、find、for_each 等，作用于容器。
- 迭代器（Iterators）：提供一种统一方式遍历容器元素，是容器与算法之间的桥梁。
- 函数对象（Function Objects / Functors）：可作为算法的参数，具有函数调用运算符。
- 适配器（Adapters）：对容器或函数进行包装，如
stack、queue、priority_queue、bind。
- 分配器（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 实现生产者消费者模型