常用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

1. std::set：集合，key=value，元素唯一、自动排序，不能重复
2. std::multiset：多重集合，允许key 重复、自动排序
3. std::map：键值对pair<key, value>，key 唯一、key 自动排序，value 可修改
4. std::multimap：多重映射，允许 key 重复、key 自动排序

共性底层：红黑树（自平衡二叉搜索树）

使用场景

set 用于去重有序存储，map 用于有序键值映射。

核心 API

insert()返回pair<迭代器,bool>标记插入是否成功；

find/count查找；

lower_bound/upper_bound区间遍历；

map 独有[]（key 不存在自动插入默认 value，查询禁止使用）。

底层特性

1. map 存储pair<const K,V>，key 为 const 不可修改（破坏有序树结构）；
2. 迭代器稳定：插入不失效，仅删除当前节点迭代器失效；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>，将内存分配释放与对象构造 / 析构完全分离，解耦容器逻辑与内存管理策略。

四大标准接口（核心区分内存与对象生命周期）

1. allocate(n)：分配 n 个 T 的原始裸内存，不调用构造函数；
2. deallocate(p,n)：释放裸内存，不调用析构函数；
3. construct(p,val)：定位 new，在已分配内存上构造对象；
4. destroy(p)：仅调用对象析构函数，不释放内存。

2. SGI STL 双层配置器（经典考点，128 字节分界）

（1）一级空间配置器 __malloc_alloc_template

适用：申请内存 > 128 字节大块内存

• 直接封装malloc/free/realloc；
• 分配失败时循环调用自定义out_of_memory异常处理函数，重试分配内存。

（2）二级空间配置器 __default_alloc_template（小块内存优化）

解决痛点：频繁小块 malloc 产生内存碎片、系统调用开销大。

1. 自由链表 free_list：维护 16 条链表，对应 8/16/24...128 字节（步长 8 字节对齐，满足内存对齐）；
2. 分配流程① 请求内存向上对齐至 8 的倍数，匹配对应 free_list；② 链表有空闲块直接取出返回；无空闲则调用内存池批量申请一批内存，切割后挂入链表；③ 内存池耗尽，调用一级配置器 malloc 向系统补充内存池；
3. 释放流程：小块内存回收至对应 free_list 缓存，不直接还给操作系统，复用减少系统调用。

3. 自定义 Allocator 应用场景

1. 内存监控：统计容器内存分配次数、检测内存泄漏；
2. 高性能内存池：后端 / 游戏服务减少频繁 malloc 开销；
3. 特殊内存：共享内存、栈内存分配。

三、面试高频区分问答（背诵）

1. vector vs listvector：连续内存随机访问 O (1)，中间增删 O (n)，扩容迭代器全失效；list：双向链表无随机访问，任意位置增删 O (1)，迭代器稳定。
2. map vs unordered_mapmap 底层红黑树有序，稳定 O (logN)，支持区间查询，迭代器不易失效；unordered_map 底层哈希表无序，平均 O (1)，rehash 后全部迭代器失效。
3. 为什么需要二级空间配置器？频繁分配小块内存会产生大量外部碎片，且每次 malloc 系统调用开销高；二级配置器通过内存池 + 自由链表缓存小块，消除碎片、降低系统调用次数。
4. allocate 和 construct 的区别？allocate 只分配未初始化的裸内存，不会创建对象；construct 在已有内存上调用构造函数，实例化对象。
5. vector 扩容为什么会全部迭代器失效？扩容会开辟全新连续内存，原内存被释放，原有迭代器指向已销毁内存，全部失效。