STL 容器

STL 容器

STL（Standard Template Library）是C++标准库的重要组成部分，提供了一系列高效的数据结构和算法实现。

序列式容器

vector（动态数组）

常用函数

• push_back(element)：在末尾添加元素
• pop_back()：删除最后一个元素
• size()：返回元素个数
• capacity()：返回当前容量
• empty()：判断是否为空
• clear()：清空所有元素
• at(index)：访问指定位置元素（带边界检查）
• operator[]：访问指定位置元素（不带边界检查）
• front()：访问第一个元素
• back()：访问最后一个元素
• begin()/end()：返回迭代器
• insert(pos, element)：在指定位置插入元素
• erase(pos)：删除指定位置元素

注意事项

• 在尾部插入和删除效率高（O(1)）
• 在中间或头部插入/删除效率较低（O(n)）
• 自动扩容，但可能导致内存重新分配

#include <vector>
std::vector<int> vec = {1, 2, 3};
vec.push_back(4);           // 添加元素
vec.pop_back();             // 删除最后一个元素
int size = vec.size();      // 获取大小

queue（队列）

常用函数

• push(element)：在队尾添加元素
• pop()：删除队首元素
• front()：访问队首元素
• back()：访问队尾元素
• empty()：判断队列是否为空
• size()：返回队列中元素个数

注意事项

• 遵循先进先出（FIFO）原则
• 只能访问队首和队尾元素
• 不能使用迭代器遍历

#include <queue>
std::queue<int> q;
q.push(1);                  // 入队
q.push(2);
q.push(3);
int front = q.front();      // 访问队首元素
q.pop();                    // 出队

list（双向链表）

常用函数

• push_front(element)：在头部插入元素
• push_back(element)：在尾部插入元素
• pop_front()：删除头部元素
• pop_back()：删除尾部元素
• insert(pos, element)：在指定位置插入元素
• erase(pos)：删除指定位置元素
• remove(value)：删除所有等于value的元素
• unique()：删除相邻重复元素
• sort()：排序
• merge(other_list)：合并两个已排序列表
• reverse()：反转

注意事项

• 不支持随机访问，只能通过迭代器遍历
• 插入和删除操作效率高（O(1)）
• 内存开销较大（每个节点需要额外指针）

#include <list>
std::list<int> lst = {1, 2, 3};
lst.push_back(4);
lst.remove(2);              // 删除值为2的元素
lst.sort();                 // 排序

关联式容器

set（集合）

常用函数

• insert(element)：插入元素
• erase(element)：删除元素
• find(element)：查找元素
• count(element)：统计元素个数（0或1）
• size()：返回元素个数
• empty()：判断是否为空
• clear()：清空所有元素
• begin()/end()：返回迭代器

注意事项

• 元素唯一且自动排序
• 查找、插入、删除时间复杂度为O(log n)
• 默认使用<运算符比较元素

#include <set>
std::set<int> s;
s.insert(3);
s.insert(1);
s.insert(2);
// s中元素顺序为: 1, 2, 3

multiset（多重集合）

常用函数

• 与set相同，但允许重复元素

注意事项

• 允许存储多个相同值的元素
• 其他特性与set相似

map（映射）

常用函数

• operator[key]：访问或插入键值对
• insert(pair<key,value>)：插入键值对
• erase(key)：删除指定键
• find(key)：查找键
• count(key)：统计键个数（0或1）
• size()：返回键值对个数
• empty()：判断是否为空
• clear()：清空所有键值对

注意事项

• 键唯一且自动按键排序
• 值可以重复
• 访问不存在的键会创建该键并赋予默认值

#include <map>
std::map<std::string, int> m;
m["apple"] = 5;
m["banana"] = 3;
int apple_count = m["apple"];  // 获取值

multimap（多重映射）

常用函数

• 与map类似，但允许重复键

注意事项

• 允许一个键对应多个值
• 其他特性与map相似

无序容器（C++11）

unordered_set（无序集合）

常用函数

• 与set类似，但基于哈希表实现

注意事项

• 元素不排序
• 平均查找、插入、删除时间复杂度为O(1)
• 最坏情况下为O(n)

unordered_map（无序映射）

常用函数

• 与map类似，但基于哈希表实现

注意事项

• 键值对不排序
• 平均查找、插入、删除时间复杂度为O(1)
• 最坏情况下为O(n)

通用注意事项

1. 使用前需包含相应头文件
2. 所有STL容器都不是线程安全的
3. 迭代器失效问题需要注意：
   • vector在插入新元素导致重新分配内存时会使所有迭代器失效
   • deque在中间插入/删除可能使迭代器失效
   • list的迭代器相对稳定，只有在删除元素时对应迭代器失效
4. 容器的拷贝操作可能代价较高，考虑使用引用或指针
5. 根据使用场景选择合适的容器类型