STL 容器

概念讲解

常用容器

容器 底层结构 特点
vector 动态数组 随机访问 O(1)
deque 双端队列 两端操作 O(1)
list 双向链表 插入删除 O(1)
set 红黑树 有序、去重
map 红黑树 键值对、有序
unordered_set 哈希表 无序、去重
unordered_map 哈希表 键值对、无序

vector

12345678910#include <vector>

vector<int> v;
v.push_back(1);     // 尾部添加
v.pop_back();       // 尾部删除
v.size();           // 大小
v.empty();          // 是否为空
v[i];               // 随机访问
v.front();          // 第一个元素
v.back();           // 最后一个元素

set

12345678#include <set>

set<int> s;
s.insert(1);        // 插入
s.erase(1);         // 删除
s.count(1);         // 是否存在
s.find(1);          // 查找
s.size();           // 大小

map

123456789101112#include <map>

map<string, int> mp;
mp["key"] = 1;      // 插入/修改
mp.erase("key");    // 删除
mp.count("key");    // 是否存在
mp.size();          // 大小

// 遍历
for (auto& [k, v] : mp) {
    cout << k << ": " << v << endl;
}

优先队列

1234567891011#include <queue>

// 大根堆
priority_queue<int> pq;

// 小根堆
priority_queue<int, vector<int>, greater<int>> pq;

pq.push(1);         // 插入
pq.top();           // 堆顶
pq.pop();           // 弹出堆顶

考点分析

初赛考查方式

  1. 选择题： 容器特性
  2. 程序阅读： STL 操作
  3. 编程题： 容器应用

常见考点

  • 容器时间复杂度
  • 选择合适容器
  • STL 操作

例题精讲

例题 1：set 去重

题目： 对数组去重并排序。

解答：

123set<int> s;
for (int i = 0; i < n; i++) s.insert(a[i]);
for (int x : s) cout << x << " ";

例题 2：map 计数

题目： 统计字符串中每个字符出现次数。

解答：

12345map<char, int> mp;
for (char c : s) mp[c]++;
for (auto& [c, cnt] : mp) {
    cout << c << ": " << cnt << endl;
}

练习题

  1. vector 和 deque 的区别是什么？
查看答案
特性 vector deque
底层结构 动态数组 双端队列
随机访问 O(1) O(1)
头部操作 O(n) O(1)
尾部操作 O(1) O(1)
空间 连续内存 分段连续
  1. set 和 unordered_set 的区别是什么？
查看答案
特性 set unordered_set
底层结构 红黑树 哈希表
有序性 有序 无序
插入 O(log n) O(1) 平均
查找 O(log n) O(1) 平均
删除 O(log n) O(1) 平均
  1. 如何创建小根堆？
查看答案
12345678910#include <queue>

// 小根堆
priority_queue<int, vector<int>, greater<int>> pq;

pq.push(3);
pq.push(1);
pq.push(2);

cout << pq.top();  // 输出 1

易错点

⚠️ 注意：

  1. set 自动去重和排序
  2. map 的 key 不存在时会自动创建
  3. 优先队列默认大根堆
  4. 注意迭代器失效问题