嵌入式之C/C++（六）容器与算法
在嵌入式 Linux / C++ 面试中，STL 容器几乎是必问内容。面试官不仅关心你“会不会用”，更关心你是否理解：
👉 底层数据结构是什么？
👉 性能差异在哪里？
👉 什么时候该用 map，什么时候该用 unordered_map？
1 map和set有什么区别？是如何实现的？
1.1 相同点
- 都是 关联式容器
- 底层实现：红黑树（RB-Tree）
- 元素自动有序
- 插入、删除、查找时间复杂度：
O(logN)
1.2 不同点对比
| 对比项 | map | set |
|---|---|---|
| 存储结构 | key-value | key |
| 是否允许修改 | value 可改 | 不可改 |
| 迭代器 | 非 const | const |
| 是否支持下标 | ✅ | ❌ |
1.3 为什么不能修改 key？
map/set的有序性依赖 key：
- 修改 key → 破坏红黑树结构
- 需要删除 + 重新插入
- 会导致迭代器失效
📌 设计结论：
STL 从接口层面直接禁止修改 key，保证容器稳定性。
2 map 的 operator[]为什么要慎用？
map<int, int> m; m[10]; // 若 key 不存在，会插入一个 value=0 的元素 ⚠️ 注意点
- 会 隐式插入元素
const map不能使用mapped_type无默认构造函数时不可用- 仅用于 确认存在性 时不推荐
✅ 推荐做法：
auto it = m.find(10); if (it != m.end()) { ... } 3 STL allocator 的作用是什么？
3.1 new/delete的问题
new T; // 分配内存 + 构造 delete T; // 析构 + 释放内存 👉 内存管理与对象生命周期 耦合严重
3.2 allocator 的设计思想
STL allocator 将这两件事拆开：
| 操作 | 函数 |
|---|---|
| 分配内存 | allocate |
| 释放内存 | deallocate |
| 构造对象 | construct |
| 析构对象 | destroy |
3.3 SGI STL 的两级分配器
- >128B：一级配置器
→ 直接malloc / free - ≤128B：二级配置器
→ 内存池 + 空闲链表
📌 核心目的：
减少小块内存频繁申请造成的碎片问题。
4 STL 中如何正确删除元素？
4.1 vector / deque
it = v.erase(it); // erase 返回下一个有效迭代器 ❌ erase 后，后续元素 整体前移
❌ 后面的迭代器全部失效
4.2 map / set
auto next = it; ++next; m.erase(it); it = next; ✔ 红黑树结构
✔ 只会使当前迭代器失效
4.3 list
- 非连续内存
- erase 返回下一个 iterator
- 最安全
5 map 与 unordered_map 的区别？
| 对比 | map | unordered_map |
|---|---|---|
| 底层结构 | 红黑树 | 哈希表 |
| 是否有序 | ✅ | ❌ |
| 查找效率 | O(logN) | O(1) 平均 |
| key 要求 | operator< | hash + == |
📌 结论：
不要求有序时，优先使用 unordered_map，性能更好。
6 vector 和 list 的区别？
| 特性 | vector | list |
|---|---|---|
| 底层 | 数组 | 双向链表 |
| 内存 | 连续 | 非连续 |
| 随机访问 | 快 | 不支持 |
| 插入删除 | 慢 | 快 |
| 扩容 | 2 倍 | 无 |
📌 一句话总结：
vector 适合查找，list 适合频繁插入删除。
7 为什么 STL 需要迭代器？有指针不够吗？
7.1 迭代器的本质
- 不是指针
- 是一个 类模板
- 重载了
* ++ -- ->
📌 本质是指针的抽象与增强
7.2 为什么不用裸指针？
- 不同容器内部结构不同
- 迭代器 统一访问接口
- 屏蔽容器内部实现
👉 这就是 Iterator 设计模式
8 epoll 的工作原理？
8.1 接口顺序
epoll_create() epoll_ctl() epoll_wait() 8.2 内部原理
- 所有 fd → 红黑树
- 就绪 fd → 就绪链表
epoll_wait只返回 活跃 fd
📌 相比 select 的优势：
- 不轮询
- fd 无上限
- 事件驱动
9 resize 和 reserve 的区别？
9.1 resize
- 改变 size
- 可能构造 / 析构对象
v.resize(10); 9.2 reserve
- 改变 capacity
- 不构造对象
v.reserve(10); 📌 性能建议：
已知元素数量时，先 reserve 再 push_back。
10 面试总结
map / set 底层是红黑树unordered_map 是哈希表allocator 解决内存碎片vector erase 会导致迭代器失效epoll 是事件驱动模型reserve 提前分配，resize 改变元素数量
