四、STL容器与数据结构共17项1.C/C中常用容器功能汇总2.介绍一下vector优缺点3.介绍一下list优缺点4.介绍一下deque优缺点5.介绍一下mapset优缺点6.介绍一下mutable关键字的作用7.map的底层原理是什么8.map和unordered_map了解吗9.hashmap和map的区别底层数据结构算法是什么10.介绍一下红黑树11.介绍一下hash12.介绍一下二叉树13.编程实现LRU14.C/C中数组和链表的优缺点15.容器选择的原则16.什么是迭代器有哪几种迭代器17.vector的底层原理和扩容机制是什么结论先行STL 容器可按序列式/关联式/无序关联式三类理解选型核心看随机访问多 →vector频繁插入删除 →list两端操作 →deque查找有序 →map/set红黑树查找无序 →unordered_map哈希表算法题常客LRU→ 哈希表 双向链表 逐条说明1. 常用容器功能汇总容器底层特点vector动态数组随机访问快尾部插入快list双向链表插入删除快无随机访问deque分段连续数组头尾插入删除都快stack/queue适配器基于deque或listset/map红黑树有序O(log⁡n)O(logn)unordered_set/map哈希表平均 O(1)O(1)无序2. vector 优缺点✅ 随机访问 O(1)O(1)尾部插入均摊 O(1)O(1)内存连续缓存友好❌ 中间/头部插入慢扩容有重新分配和拷贝开销3. list 优缺点✅ 任意位置插入删除 O(1)O(1)❌ 无随机访问内存不连续缓存不友好4. deque 优缺点✅ 头尾插入删除 O(1)O(1)支持随机访问❌ 中间插入慢迭代器实现复杂5. map set 优缺点✅ 自动排序查找/插入/删除 O(log⁡n)O(logn)❌ 比哈希表慢需要自定义比较器6. mutable 关键字允许在const成员函数中修改该成员常用于缓存、计数器、互斥锁class A { mutable int count 0; public: void foo() const { count; } // ✅ OK };7. map 的底层原理通常基于红黑树实现键值按比较器有序排列保证 O(log⁡n)O(logn) 的查找、插入、删除。8. map vs unordered_map维度mapunordered_map底层红黑树哈希表有序性有序无序查找O(log⁡n)O(logn)平均 O(1)O(1)最坏 O(n)O(n)内存较少较多9. hashmap vs map底层数据结构map红黑树有序O(log⁡n)O(logn)hashmapunordered_map哈希表 拉链/开放寻址平均 O(1)O(1)10. 红黑树自平衡二叉搜索树五大性质保证高度近似 log⁡nlogn节点红或黑根黑叶子NIL黑红节点的子节点黑任意节点到叶子路径黑节点数相同通过旋转 变色维持平衡。11. 哈希Hash通过哈希函数把键映射到数组下标实现快速查找。冲突解决方法拉链法、开放寻址法、再哈希法等。12. 二叉树每个节点最多两个子节点的树结构。常见变体二叉搜索树BST平衡二叉树AVL红黑树堆完全二叉树13. 编程实现 LRU核心哈希表 双向链表保证 O(1)O(1) 查找和删除class LRUCache { int cap; listpairint,int lst; // (key, value) unordered_mapint, listpairint,int::iterator mp; public: LRUCache(int capacity) : cap(capacity) {} int get(int key) { if (!mp.count(key)) return -1; lst.splice(lst.begin(), lst, mp[key]); // 移到队头 return mp[key]-second; } void put(int key, int val) { if (mp.count(key)) { mp[key]-second val; lst.splice(lst.begin(), lst, mp[key]); } else { if (lst.size() cap) { mp.erase(lst.back().first); lst.pop_back(); } lst.emplace_front(key, val); mp[key] lst.begin(); } } };14. 数组 vs 链表维度数组链表访问随机 O(1)O(1)顺序 O(n)O(n)插入删除中间 O(n)O(n)O(1)O(1)内存连续缓存友好不连续扩容需要重新分配动态增长15. 容器选择原则需要索引/排序 →vector/deque频繁插入删除中间元素 →list键值查找且需有序 →map/set键值查找只需快 →unordered_map/set优先保证缓存友好 → 连续容器16. 迭代器及种类迭代器是访问容器元素的“泛型指针”。C 分 5 类迭代器能力输入迭代器只读单次遍历输出迭代器只写单次遍历前向迭代器可多读单向双向迭代器可双向移动list随机访问迭代器可n、-nvector17. vector 底层原理和扩容机制底层是一块连续动态数组。size()当前元素数capacity()容量扩容当size capacity时重新申请更大内存常见1.5 倍或 2 倍拷贝/移动元素释放旧内存。GCC libstdc2 倍MSVC1.5 倍频繁扩容可先用reserve预分配减少拷贝开销 ⚡整体联系这 17 题串起了STL 容器选型 → 底层数据结构 → 算法复杂度 → 经典应用LRU容器接口底层数据结构时间/空间复杂度场景化选型LRU等经典实现理解底层数组、链表、红黑树、哈希表才能真正做到用对容器、写出高效代码