常用STL 容器，空间配置器的使用和底层原理

一、容器四大分类序列容器、有序关联容器、无序哈希容器、容器适配器1. 序列容器按插入顺序存储1vector 动态数组使用场景跟数组有相同的使用场景核心 APIpush_back/pop_back、reserve(n)预分配容量、resize(n)修改有效元素、insert/erase、[]/at()at 带越界检查底层原理底层为一个可扩容的数组2倍扩容或3倍扩容扩容流程开辟新连续内存→拷贝元素→析构旧对象释放内存扩容后所有迭代器、指针、引用全部失效。迭代器失效问题中间insert/erase需要搬移后方元素时间复杂度 O (n)。扩容全失效insert/erase 使当前位置及之后迭代器失效pop_back 仅尾迭代器失效。2list 双向循环链表使用场景跟链表相同的使用场景核心 APIpush_front/push_back、pop_front/pop_back、insert(it,val)、erase(it)、remove(val)、自带sort()。底层原理双向循环链表节点结构prev前驱指针 next后继指针 数据域内存不连续。迭代器特性任意位置增删仅修改指针 O (1)只有被 erase 删除的节点迭代器失效其余全部有效不支持随机访问查找 O (n)。2. 有序关联容器 map /set/multimap /multisetstd::set集合keyvalue元素唯一、自动排序不能重复std::multiset多重集合允许key 重复、自动排序std::map键值对pairkey, valuekey 唯一、key 自动排序value 可修改std::multimap多重映射允许 key 重复、key 自动排序共性底层红黑树自平衡二叉搜索树使用场景set 用于去重有序存储map 用于有序键值映射。核心 APIinsert()返回pair迭代器,bool标记插入是否成功find/count查找lower_bound/upper_bound区间遍历map 独有[]key 不存在自动插入默认 value查询禁止使用。底层特性map 存储pairconst K,Vkey 为 const 不可修改破坏有序树结构迭代器稳定插入不失效仅删除当前节点迭代器失效multimap 无[]支持重复 key。3. 无序哈希容器 unordered_map /unordered_set特点底层哈希表特点不保证顺序平均 O (1) 查找速度更快缺点不支持有序遍历、不支持二分查找适用只做精确查找不需要排序4. 容器适配器无独立内存封装底层容器stack 栈 LIFO 后进先出默认底层 dequeAPIpush/pop/top仅操作栈顶不可遍历使用场景深度优先queue 队列 FIFO 先进先出默认底层 dequeAPIpush/pop/front/back使用场景广度优先priority_queue 优先队列堆默认底层 vector完全二叉堆默认大根堆top 为最大值插入 / 删除堆顶 O (logN)左孩子left i * 2 1右孩子right i * 2 2二、空间配置器 Allocator 底层原理面试重点1. 核心设计思想容器模板默认携带Allocator std::allocatorT将内存分配释放与对象构造 / 析构完全分离解耦容器逻辑与内存管理策略。四大标准接口核心区分内存与对象生命周期allocate(n)分配 n 个 T 的原始裸内存不调用构造函数deallocate(p,n)释放裸内存不调用析构函数construct(p,val)定位 new在已分配内存上构造对象destroy(p)仅调用对象析构函数不释放内存。2. SGI STL 双层配置器经典考点128 字节分界1一级空间配置器 __malloc_alloc_template适用申请内存 128 字节大块内存直接封装malloc/free/realloc分配失败时循环调用自定义out_of_memory异常处理函数重试分配内存。2二级空间配置器 __default_alloc_template小块内存优化解决痛点频繁小块 malloc 产生内存碎片、系统调用开销大。自由链表 free_list维护 16 条链表对应 8/16/24...128 字节步长 8 字节对齐满足内存对齐分配流程① 请求内存向上对齐至 8 的倍数匹配对应 free_list② 链表有空闲块直接取出返回无空闲则调用内存池批量申请一批内存切割后挂入链表③ 内存池耗尽调用一级配置器 malloc 向系统补充内存池释放流程小块内存回收至对应 free_list 缓存不直接还给操作系统复用减少系统调用。3. 自定义 Allocator 应用场景内存监控统计容器内存分配次数、检测内存泄漏高性能内存池后端 / 游戏服务减少频繁 malloc 开销特殊内存共享内存、栈内存分配。三、面试高频区分问答背诵vector vs listvector连续内存随机访问 O (1)中间增删 O (n)扩容迭代器全失效list双向链表无随机访问任意位置增删 O (1)迭代器稳定。map vs unordered_mapmap 底层红黑树有序稳定 O (logN)支持区间查询迭代器不易失效unordered_map 底层哈希表无序平均 O (1)rehash 后全部迭代器失效。为什么需要二级空间配置器频繁分配小块内存会产生大量外部碎片且每次 malloc 系统调用开销高二级配置器通过内存池 自由链表缓存小块消除碎片、降低系统调用次数。allocate 和 construct 的区别allocate 只分配未初始化的裸内存不会创建对象construct 在已有内存上调用构造函数实例化对象。vector 扩容为什么会全部迭代器失效扩容会开辟全新连续内存原内存被释放原有迭代器指向已销毁内存全部失效。