常用STL 容器，空间配置器的使用和底层原理
一、容器四大分类：序列容器、有序关联容器、无序哈希容器、容器适配器
1. 序列容器（按插入顺序存储）
（1）vector 动态数组
使用场景
跟数组有相同的使用场景
核心 API
push_back/pop_back、reserve(n)预分配容量、resize(n)修改有效元素、insert/erase、[]/at()（at 带越界检查）
底层原理
底层为一个可扩容的数组，2倍扩容或3倍扩容，扩容流程：开辟新连续内存→拷贝元素→析构旧对象释放内存；扩容后所有迭代器、指针、引用全部失效。
迭代器失效问题：中间insert/erase需要搬移后方元素，时间复杂度 O (n)。扩容全失效；insert/erase 使当前位置及之后迭代器失效；pop_back 仅尾迭代器失效。
（2）list 双向循环链表
使用场景
跟链表相同的使用场景
核心 API
push_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 /multiset
std::set：集合，key=value，元素唯一、自动排序，不能重复std::multiset：多重集合，允许key 重复、自动排序std::map：键值对pair<key, value>，key 唯一、key 自动排序，value 可修改std::multimap：多重映射，允许 key 重复、key 自动排序
共性底层：红黑树（自平衡二叉搜索树）
使用场景
set 用于去重有序存储，map 用于有序键值映射。
核心 API
insert()返回pair<迭代器,bool>标记插入是否成功；
find/count查找；
lower_bound/upper_bound区间遍历；
map 独有[]（key 不存在自动插入默认 value，查询禁止使用）。
底层特性
- map 存储
pair<const K,V>，key 为 const 不可修改（破坏有序树结构）； - 迭代器稳定：插入不失效，仅删除当前节点迭代器失效；multimap 无
[]，支持重复 key。
3. 无序哈希容器 unordered_map /unordered_set
特点
- 底层：哈希表
- 特点：不保证顺序，平均 O (1) 查找，速度更快
- 缺点：不支持有序遍历、不支持二分查找
- 适用：只做精确查找，不需要排序
4. 容器适配器（无独立内存，封装底层容器）
stack 栈 LIFO 后进先出默认底层 deque；
API：push/pop/top；仅操作栈顶，不可遍历；
使用场景：深度优先
queue 队列 FIFO 先进先出默认底层 deque；
API：push/pop/front/back；
使用场景：广度优先
priority_queue 优先队列（堆）默认底层 vector，完全二叉堆（默认大根堆，top 为最大值）；
插入 / 删除堆顶 O (logN)；左孩子：left = i * 2 + 1右孩子：right = i * 2 + 2
二、空间配置器 Allocator 底层原理（面试重点）
1. 核心设计思想
容器模板默认携带Allocator = std::allocator<T>，将内存分配释放与对象构造 / 析构完全分离，解耦容器逻辑与内存管理策略。
四大标准接口（核心区分内存与对象生命周期）
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 扩容为什么会全部迭代器失效？扩容会开辟全新连续内存，原内存被释放，原有迭代器指向已销毁内存，全部失效。