CPP STL

C++ STL（Standard Template Library，标准模板库）主要分为 六大组件：容器 (Containers)、算法 (Algorithms)、迭代器 (Iterators)、函数对象 (Functors)、适配器 (Adaptors) 和 分配器 (Allocators)，通过模板将数据结构、算法和迭代策略解耦，提供了一套通用的、高效的、类型安全的数据结构组件，避免了程序员重复造轮子。

序列式容器

容器	底层结构	特点	典型复杂度	适用场景
std::vector	动态数组	内存连续，支持随机访问，尾部插入快，中间插入慢	随机访问 O(1)，尾插 O(1)摊销	默认首选容器，缓存友好
std::deque	分段连续数组	头尾插入/删除都快，支持随机访问	随机访问 O(1)，头尾插删 O(1)	双端队列，滑动窗口
std::list	双向链表	任意位置插入/删除快，不支持随机访问	插入/删除 O(1)，查找 O(n)	频繁在中间插入/删除
std::forward_list	单向链表	比 list 更省空间，只能向前遍历	同 list	极端内存敏感场景
std::array	静态数组	固定大小，栈上分配，零开销抽象	全部 O(1)	替代原生数组，安全且兼容STL

std::vector

std::vector 是可变大小的动态数组，提供了与原生数组相近的性能和随机访问能力，同时自动管理内存。

vector 使用动态内存分配（通常是 operator new 或 allocate）在堆上申请内存块，其元素被存储在连续的内存地址中，通过 construct / destroy 进行对象构造与析构。

std::vector 的底层是三段式指针（或指针+偏移量）结构：

T* start;        // 指向已分配内存的起始位置
T* finish;       // 指向最后一个有效元素的下一个位置（即 end()）
T* end_of_storage; // 指向已分配内存的末尾（capacity 的上限）

注：GCC (libstdc++) / Clang (libc++)采用 2 倍 扩容，MSVC (Visual Studio)采用 1.5 倍 扩容。

构造

方法	说明
vector<T> v;	默认构造，空容器
vector<T> v(n, val);	n 个 val 的拷贝
vector<T> v(begin, end);	迭代器区间构造
v.assign(n, val);	重新赋值为 n 个 val
v = other; / v = move(other);	拷贝 / 移动赋值

std::vector<double> vectors;创建后，vectors是一个空的 vector 容器，因为容器中没有元素，所以没有为其分配空间。当添加第一个元素（比如使用 push_back() 函数）时，vector 会自动分配内存。vector<T> v(n);可指定初始容量为n，默认值为0。

std::vector<int> v1;              // 初始为空，没有内存开辟
std::vector<int> v2{1, 2, 3};     // 直接调用构造函数
std::vector<int> v3 = {1, 2, 3};  // C++17 起，直接构造，等于上一条

std::vector<int> v4(10);                // 10个0
std::vector<int> v5(10, 42);     // 10个42

std::vector<int> src = {10, 20, 30, 40, 50};
std::vector<int> v6(src.begin() + 1, src.begin() + 4);       // {20, 30, 40}
std::vector<int> v7(std::begin(src), std::end(src)); // {10, 20, 30, 40, 50}

std::vector<int> v8(src);          // {10, 20, 30, 40, 50}
std::vector<int> v9 = src;         // {10, 20, 30, 40, 50}

std::vector<int> v10(std::move(src)); // src is empty

std::vector<int> v11;         // 初始为空，没有内存开辟
v11.assign(10, 1);    // 10个1
v11.assign({1, 2, 3});     // {1, 2, 3}

std::vector<std::string> v12;
v12.push_back(std::string("hello"));  // 构造临时 string 再移动进 vector
v12.emplace_back("world");               // 直接在 vector 内存中调用string的构造函数

std::vector<std::vector<int>> matrix(3, std::vector<int>(4, 0)); // 3行4列的0矩阵

元素访问

方法	说明	边界检查
v[i]	下标访问	不检查
v.at(i)	下标访问	越界抛 out_of_range
v.front() / v.back()	首元素 / 尾元素 的引用	空容器未定义
v.data()	返回指向首元素的裸指针 T*	—

std::vector<int> v = {1, 2, 3, 4, 5};
std::cout << "v[0]: " << v[0] << std::endl;
std::cout << "v.at(0): " << v.at(0) << std::endl;
std::cout << "v.front(): " << v.front() << std::endl;
std::cout << "v.back(): " << v.back() << std::endl;
std::cout << "*v.data(): " << *v.data() << std::endl;

容量

方法	说明
v.size()	当前元素个数
v.capacity()	不重新分配前提下可容纳的元素数
v.empty()	是否为空
v.reserve(n)	预分配至少容纳 n 个元素的空间
v.shrink_to_fit()	请求释放多余容量（C++11，不强制）

修改

方法	说明	均摊复杂度
v.push_back(val)	尾部追加（先创建临时对象，再移动到vector中)	O(1)
v.emplace_back(val)	尾部追加（不创建临时对象，直接在vector中构造）
v.pop_back()	尾部弹出	O(1)
v.insert(pos, val)	在迭代器 pos 前插入	O(n)
v.erase(pos) / v.erase(first, last)	删除单个 / 区间元素	O(n)
v.clear()	清空所有元素（size=0，capacity 不变）	O(n)
v.resize(n, val)	调整大小，新增元素以 val 填充	—
v.swap(other)	交换两个 vector 的内部数据	O(1)

std::deque

std::deque（double-ended queue 双端队列）在头部和尾部插入、删除都非常高效。

std::deque 通常由多个固定大小的内存块组成，再通过内部结构管理这些块。可以随机访问，但不保证元素连续存储。

• 随机访问 O(1)
• 头部，尾部插入push_back() / pop_back()

操作	vector	deque
push_back()	O(1) 均摊	O(1)
pop_back()	O(1)	O(1)
push_front()	O(n)	O(1)
pop_front()	O(n)	O(1)
operator[]	O(1)	O(1)
at()	O(1)	O(1)
中间插入	O(n)	O(n)
中间删除	O(n)	O(n)
连续内存	是	不是
支持随机访问	是	是

初始化

#include <deque>

std::deque<int> dq1; // 空deque
std::deque<int> dq2(5); // 指定数量[0,0,0,0,0]
std::deque<int> dq3(5, 100); // 指定数量和值 [100,100,100,100,100]

std::vector<int> v{1, 2, 3, 4};          
std::deque<int> dq4(v.begin(), v.end());  // 使用另一个容器初始化

关联式容器

容器	底层结构	特点	典型复杂度
std::set / std::multiset	红黑树	有序集合，只存 Key	查找、插入、删除均为 $O(log n)$
std::map / std::multimap	红黑树	有序映射，存 Key-Value 对	查找、插入、删除均为 $O(log n)$

无序容器

容器	底层结构	特点	典型复杂度
std::unordered_set / std::unordered_multiset	哈希表	无序集合，只存 Key	平均 O(1)，最差 O(n)（哈希冲突严重时）
std::unordered_map / std::unordered_multimap	哈希表	无序映射，存 Key-Value 对	平均 O(1)，最差 O(n)（哈希冲突严重时）

容器适配器

容器	底层结构	特点	典型复杂度
std::stack	默认用 deque
std::queue	默认用 deque
std::priority_queue	默认用 vector + make_heap

容器	分类	底层数据结构	随机访问	头部插删	尾部插删	中间插删	查找 (Key)	迭代器类型	迭代器稳定性	有序性	典型适用场景
std::array	序列式	静态数组 (栈)	✅ O(1)	❌ O(n)	❌ O(n)	❌ O(n)	❌ O(n)	Random Access	✅ 永不失效	❌	固定大小数据、替代原生数组、高性能嵌入式
std::vector	序列式	动态数组 (堆)	✅ O(1)	❌ O(n)	⚡ O(1)*	❌ O(n)	❌ O(n)	Contiguous	⚠️ 扩容时全部失效	❌	默认首选、缓存友好、批量数据处理
std::deque	序列式	分段连续数组	✅ O(1)	⚡ O(1)	⚡ O(1)	❌ O(n)	❌ O(n)	Random Access	⚠️ 头尾插删可能失效	❌	双端队列、滑动窗口、需要头尾操作的缓冲区
std::list	序列式	双向链表	❌ O(n)	⚡ O(1)	⚡ O(1)	⚡ O(1)	❌ O(n)	Bidirectional	✅ 仅被删元素失效	❌	频繁任意位置插入/删除、需要稳定迭代器引用
std::forward_list	序列式	单向链表	❌ O(n)	⚡ O(1)	❌ O(n)	⚡ O(1)	❌ O(n)	Forward	✅ 仅被删元素失效	❌	极端内存敏感、只需前向遍历的链表操作
std::set	关联式	红黑树	❌ O(n)	❌ -	❌ -	❌ -	✅ O(log n)	Bidirectional	✅ 仅被删元素失效	✅ 升序	去重且需有序、范围查询、有序集合运算
std::multiset	关联式	红黑树	❌ O(n)	❌ -	❌ -	❌ -	✅ O(log n)	Bidirectional	✅ 仅被删元素失效	✅ 升序	允许重复键的有序集合
std::map	关联式	红黑树	❌ O(n)	❌ -	❌ -	❌ -	✅ O(log n)	Bidirectional	✅ 仅被删元素失效	✅ Key升序	有序键值映射、需要按Key范围遍历
std::multimap	关联式	红黑树	❌ O(n)	❌ -	❌ -	❌ -	✅ O(log n)	Bidirectional	✅ 仅被删元素失效	✅ Key升序	一对多有序映射
std::unordered_set	无序	哈希表	❌ O(n)	❌ -	❌ -	❌ -	⚡ O(1)***	Forward	⚠️ Rehash时全部失效	❌	高速去重查找、不关心顺序
std::unordered_multiset	无序	哈希表	❌ O(n)	❌ -	❌ -	❌ -	⚡ O(1)***	Forward	⚠️ Rehash时全部失效	❌	允许重复的高速查找
std::unordered_map	无序	哈希表	❌ O(n)	❌ -	❌ -	❌ -	⚡ O(1)***	Forward	⚠️ Rehash时全部失效	❌	高频键值查找、缓存/索引系统
std::unordered_multimap	无序	哈希表	❌ O(n)	❌ -	❌ -	❌ -	⚡ O(1)***	Forward	⚠️ Rehash时全部失效	❌	一对多高速映射
std::stack	适配器	默认 deque	❌	❌	⚡ O(1)	❌	❌	🚫 无	-	❌	LIFO 栈、递归模拟、表达式求值
std::queue	适配器	默认 deque	❌	⚡ O(1)	⚡ O(1)	❌	❌	🚫 无	-	❌	FIFO 队列、BFS、任务调度
std::priority_queue	适配器	默认 vector+heap	❌	❌	⚡ O(log n)	❌	❌	🚫 无	-	⚡ 堆序	Top-K问题、Dijkstra、事件驱动调度