四、STL容器与数据结构-北京尧图网络

四、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等经典实现理解底层数组、链表、红黑树、哈希表才能真正做到用对容器、写出高效代码

四、STL容器与数据结构

相关推荐

【自用】AI infra相关

为什么有人说自动启停“省油但伤车“？

船用柴油机气缸盖开裂故障仿真方法探讨

更多资讯

工地太忙根本没时间复习考试？年审电工证在哪练习多少钱全解析

天津电工证改革通过率揭秘：实操考试心里没底怕挂科？看过来！

深圳电工证去哪复审内部消息曝光：别再踩坑了，这波复审攻略你必须知道

老城哪里考电工证怎么走官方报名入口

淮安市电工证考试内部消息：新手怕被坑？这3步帮你避开报名雷区

宣化电工证是什么考试真题与备考技巧

今日更新

金坛办电工证在哪里？考前押题能帮你少走弯路

怎样查看真假电工证怎么考

史密斯内部电工证值不值得考？怕考不过白交培训费的看过来

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？