在本篇博客中，我将详细记录从最初的 list 实现，到优化过程中如何使用 unordered_map 提高查询效率，并总结优化过程中学习到的 STL 知识点。
1. 初始代码与问题分析
最初的实现是基于 list<int> 进行插入、删除和查询操作：
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
int main() {
list<int> ls;
ls.push_back(1);
int n;
cin >> n;
while (n--) {
int m;
cin >> m;
if (m == 1) {
int x, y;
cin >> x >> y;
auto it = find(ls.begin(), ls.end(), x);
ls.insert(++it, y);
}
if (m == 2) {
int x;
cin >> x;
auto it = find(ls.begin(), ls.end(), x);
if (++it != ls.end()) cout << *it << endl;
else cout << "0" << endl;
}
if (m == 3) {
int x;
cin >> x;
auto it = find(ls.begin(), ls.end(), x);
ls.erase(it);
}
}
return 0;
}
存在的问题
find(ls.begin(), ls.end(), x)时间复杂度 O(N)，当数据量很大时（例如 $10^5$ 次操作），会导致 超时。- 需要更快的方式来存储元素位置，使得
find(x)可以在 O(1) 时间复杂度 内完成。
2. 优化思路：引入 unordered_map
我们使用 unordered_map<int, list<int>::iterator> 来存储每个元素的位置，使得 find(x) 操作可以在 O(1) 时间内完成。
#include <iostream>
#include <list>
#include <unordered_map>
using namespace std;
int main() {
list<int> ls;
unordered_map<int, list<int>::iterator> pos;
ls.push_back(1);
pos[1] = ls.begin();
int n;
cin >> n;
while (n--) {
int m;
cin >> m;
if (m == 1) {
int x, y;
cin >> x >> y;
auto it = pos[x];
auto new_it = ls.insert(next(it), y);
pos[y] = new_it;
}
if (m == 2) {
int x;
cin >> x;
auto it = pos[x];
if (next(it) != ls.end()) cout << *next(it) << endl;
else cout << "0" << endl;
}
if (m == 3) {
int x;
cin >> x;
auto del_it = pos[x];
pos.erase(x);
ls.erase(del_it);
}
}
return 0;
}
优化点
✅ unordered_map<int, list<int>::iterator> pos; 用于存储元素位置，实现 find(x) 操作 O(1) 复杂度。 ✅ auto new_it = ls.insert(next(it), y); 直接在 O(1) 时间内插入元素，并更新 pos。 ✅ 删除操作 ls.erase(it); 和 pos.erase(x); 确保同步更新，避免悬空迭代器。
3. STL 知识点总结
(1) unordered_map<int, list<int>::iterator> 如何实现 pos.find(x)？
pos 是一个 哈希表，键是整数 x（链表中的值），值是 list<int>::iterator（链表中 x 的迭代器）。
unordered_map<int, list<int>::iterator> pos;
当我们调用 pos.find(x) 时，哈希表会：
使用 x 作为键，在哈希表 pos 中查找
由于 unordered_map 使用 哈希函数，它可以在 O(1) 时间内找到 x 是否存在。
返回 list<int>::iterator（指向链表中 x 的位置）
如果 x 在哈希表中，返回对应的迭代器。
如果 x 不存在，返回 pos.end()。
unordered_map 采用 哈希表 存储键值对，其 find(x) 操作的时间复杂度为 O(1)，可以高效地查找 list<int>::iterator。
auto it = pos.find(x); // O(1) 查找
(2) ls.insert(next(it), y) 的作用是什么？
list<int>::insert(iterator, value)会返回新插入元素的迭代器，所以new_it存储了y的位置。next(it)获取x的下一个位置，保证y被正确插入。
it->second 代表什么？
假设：
unordered_map<int, list<int>::iterator> pos;
pos[x]存储的是 链表list<int>中x的迭代器，即list<int>::iteratorit = pos.find(x)，则：it->first是x（键）it->second是 指向x在链表中的迭代器
所以：
next(it->second)
代表 x 的下一个位置的迭代器。
(3) pos[x] 和 pos.find(x) 有什么区别？
| 表达式 | 作用 | 行为 | 是否会创建新键值对 |
|---|---|---|---|
pos[x] | 访问或修改 x 对应的迭代器 | 若 x 不存在，会自动创建 | ✅ 是 |
pos.find(x) | 查找 x 是否存在 | 若 x 不存在，返回 pos.end() | ❌ 否 |
示例：
unordered_map<int, int> mp;
cout << mp[10]; // ✅ `mp[10]` 自动创建新键值对 (10, 0)
if (mp.find(10) != mp.end()) cout << "Found!"; // ❌ `find()` 不会创建
(4) 为什么 pos.erase(*del_it) 需要解引用？
del_it 是 list<int>::iterator，但 pos.erase() 需要 键值，所以要用 *del_it 取出整数键值：
pos.erase(*del_it); // 取出键值 x，删除 pos[x]
(5) erase() 和 remove() 的区别
| 方法 | 支持容器 | 删除方式 | 参数 |
|---|---|---|---|
erase(iterator) | list / vector / map / set | 按位置删除 | 迭代器 |
erase(value) | map / set / unordered_map | 按值删除 | 具体值 |
remove(value) | list | 删除所有匹配的值 | 具体值 |
std::remove(value) | vector / deque | 移动不匹配的值到前面，不真正删除 | 具体值 |
示例：
vector<int> v = {1, 2, 3, 4, 3, 5};
v.erase(remove(v.begin(), v.end(), 3), v.end()); // ✅ 删除所有 3
4. 总结
🔹 优化前：遍历 list 查找，导致超时 🔹 优化后：用 unordered_map 存储位置，查找时间降至 O(1) 🔹 学习了 STL 容器 erase()、remove()、unordered_map 的高效用法
通过这次优化，深入理解了 C++ STL 容器操作的时间复杂度，以及如何使用哈希表提高性能。希望这篇博客能帮助你更好地理解 list 和 unordered_map 的结合使用！
Comments NOTHING