STL（Standard Template Library）容器分为序列式容器（元素有序排列，如 vector、list、deque）和关联式容器（元素按键值关联，有序关联式如 map/set 底层为红黑树，无序关联式如 unordered_map 底层为哈希表）。以下基于经典 SGI STL / GCC libstdc++ 源码实现，逐一解析核心容器的底层原理。

一、前置基础：空间配置器 alloc

所有 STL 容器的内存申请 / 释放都不直接使用malloc/free，而是通过空间配置器（allocator） 间接管理。SGI STL 采用两级配置器架构：

• 一级配置器：直接调用malloc/free，处理 >128 字节的大块内存，分配失败时调用new_handler尝试释放内存。
• 二级配置器：用内存池管理 ≤128 字节的小内存，维护 16 个自由链表（分别管理 8、16...128 字节大小的内存块），减少内存碎片和系统调用开销。

容器默认使用std::allocator，其底层封装了上述空间配置逻辑。

---

二、序列式容器

1. vector：动态数组

底层数据结构

vector 本质是连续内存的动态数组，核心通过三个指针（迭代器）维护内存区间：

cpp

运行

// 简化源码结构
template <class T, class Alloc = alloc>
class vector {
    T* start;          // 数组起始地址（已使用空间的头部）
    T* finish;         // 已使用元素的尾部（下一个可构造位置）
    T* end_of_storage; // 整个分配内存的尾部
};

• size() = finish - start：已存储元素个数
• capacity() = end_of_storage - start：总可用容量

核心机制

1. 扩容机制

   • 当size() == capacity()时触发扩容，GCC/SGI 实现为2 倍扩容，VS 为 1.5 倍扩容。
   • 扩容流程：
     1. 按新容量申请一块连续的新内存；
     2. 将旧空间的元素通过拷贝构造 / 移动构造逐个复制到新空间；
     3. 析构旧空间的所有元素，释放旧内存。
   • 注意：扩容会导致所有指向原 vector 的迭代器、指针、引用全部失效。

2. 核心操作实现

   • push_back：先检查是否有备用空间，有则直接在finish位置构造元素，finish++；无则先扩容再插入。
   • emplace_back：直接在尾部内存上原地构造对象，避免临时对象的拷贝 / 移动，性能优于push_back。
   • insert/erase：需要移动插入 / 删除点之后的所有元素，时间复杂度O(n)，会导致操作位置之后的迭代器失效。
   • reserve(n)：仅扩容到至少 n 的容量，不构造元素；resize(n)：改变元素个数，不足则构造默认值，超出则析构。

特性与适用场景

• 迭代器类型：随机访问迭代器，支持[]下标访问，访问效率 O (1)。
• 优势：尾插尾删效率高，随机访问快，内存连续缓存友好。
• 劣势：中间插入删除效率低，扩容有性能开销。
• 适用：频繁随机访问、主要在尾部增删的场景。

2. list：双向循环链表

底层数据结构

list 底层是带头结点的双向循环链表，每个节点独立分配内存，节点结构分为基类和数据类：

cpp

运行

// 节点基类，仅存指针，降低类型依赖
struct _List_node_base {
    _List_node_base* prev;
    _List_node_base* next;
};

// 数据节点，继承基类并存储数据
template <class T>
struct _List_node : public _List_node_base {
    T data;
};

template <class T, class Alloc = alloc>
class list {
    _List_node_base* node; // 仅维护一个头结点指针
    // C++11后新增 size_t _M_size; 实现O(1)获取size
};

• 头结点不存储数据，node->next指向第一个元素，node->prev指向最后一个元素，形成闭环。

核心机制

1. 内存管理：每个节点单独申请 / 释放，无扩容概念，插入 / 删除仅修改前后节点的指针，时间复杂度O(1)（前提是已找到目标位置）。
2. 专属成员函数
   • splice：将另一个 list 的节点直接接合到当前 list 指定位置，仅修改指针，无元素拷贝，O (1) 复杂度。
   • sort：list 自带排序成员函数，采用归并排序实现。因为std::sort要求随机访问迭代器，而 list 迭代器不支持算术运算，无法使用标准算法。
3. 迭代器失效：插入操作不会导致任何迭代器失效；删除操作仅使被删除元素的迭代器失效，其他迭代器不受影响。

特性与适用场景

• 迭代器类型：双向迭代器，不支持随机访问，访问元素需遍历，O (n) 复杂度。
• 优势：任意位置插入删除效率高，无内存移动，迭代器失效范围小。
• 劣势：随机访问慢，内存不连续，缓存命中率低，每个节点有额外指针开销。
• 适用：频繁在中间位置增删元素、不需要随机访问的场景。

---

三、关联式容器

1. map：红黑树实现的有序映射

底层数据结构

map 底层封装了红黑树（Red-Black Tree），这是一种自平衡的二叉搜索树，通过颜色约束保证树的高度平衡（高度约为log2(n)）。

红黑树核心性质

1. 每个节点非红即黑；
2. 根节点必须是黑色；
3. 所有叶子节点（空节点 NIL）都是黑色；
4. 红色节点的两个子节点必须是黑色（不能有连续红节点）；
5. 任意节点到其所有叶子节点的路径上，黑色节点数量相同。

节点与容器结构

cpp

运行

// 红黑树节点
struct _Rb_tree_node_base {
    _Rb_tree_color color;
    _Rb_tree_node_base* parent;
    _Rb_tree_node_base* left;
    _Rb_tree_node_base* right;
};

template <class Value>
struct _Rb_tree_node : public _Rb_tree_node_base {
    Value value_field; // map中为 pair<const Key, T>
};

// map 底层直接持有红黑树实例
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
    typedef pair<const Key, T> value_type;
    _Rb_tree<Key, value_type, ...> _M_t; // 红黑树成员
};

• map 的元素是pair<const Key, T>，key 被 const 修饰，不能直接修改，否则会破坏红黑树的有序性。
• 默认按less<Key>升序排列，中序遍历红黑树即可得到有序序列。

核心机制

1. 插入操作

   • 先按二叉搜索树规则找到插入位置，检查 key 是否重复（map 不允许重复 key）；
   • 插入新节点（默认红色），若破坏红黑树性质，则通过左旋、右旋、变色三种操作调整，恢复平衡。
   • 时间复杂度：O(log n)。

2. 查找操作

   • 从根节点开始，按 key 大小比较向左 / 向右子树遍历，直到找到匹配节点或到达空节点。
   • 时间复杂度：O(log n)。

3. 删除操作

   • 按二叉搜索树规则删除节点，替换为后继节点；
   • 删除后若破坏红黑树性质，同样通过旋转 + 变色调整平衡。
   • 时间复杂度：O(log n)。

特性与适用场景

• 迭代器类型：双向迭代器，按 key 有序遍历。
• 优势：元素有序，查找 / 插入 / 删除均为稳定的 O (log n)，无最坏情况。
• 劣势：内存开销大（每个节点带 4 个指针 + 颜色），插入删除需要平衡调整。
• 适用：需要有序遍历、对性能稳定性要求高的键值对存储场景。

2. unordered_map：哈希表实现的无序映射

底层数据结构

unordered_map 底层是哈希表（散列表），采用开链法（链地址法） 解决哈希冲突。核心结构是一个桶数组（bucket array），每个桶对应一个哈希值，桶内挂载一个链表存储冲突元素。

cpp

运行

// 简化底层结构
template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>, ...>
class unordered_map {
    // 桶数组：每个元素是链表头指针
    vector<_Node*> _M_buckets;
    size_t _M_element_count; // 元素总数
    float _M_max_load_factor; // 最大负载因子，默认1.0
};

// 链表节点
struct _Node {
    _Node* _M_next;
    pair<const Key, T> _M_storage;
};

核心机制

1. 哈希与定位

   • 通过哈希函数Hash(key)计算哈希值，再对桶数量取模，得到元素所属的桶下标。
   • 若多个 key 哈希后落到同一个桶，则挂在该桶的链表上。

2. 负载因子与重哈希（rehash）

   • 负载因子 = 元素总数 / 桶数量，反映哈希表的拥挤程度。
   • 当负载因子超过阈值（默认 1.0）时，触发重哈希：
     1. 申请一个更大的桶数组（SGI 实现为质数序列扩容，如 53、97、193...）；
     2. 遍历所有元素，重新计算哈希值，放入新桶的链表中；
     3. 释放旧桶数组。
   • 重哈希会导致所有迭代器失效。

3. 核心操作复杂度

   • 插入 / 查找 / 删除：平均时间复杂度O(1)，最坏情况（所有元素哈希冲突到同一个桶）退化为O(n)。

特性与适用场景

• 迭代器类型：前向迭代器，遍历顺序无序，由哈希分布决定。
• 优势：平均情况下增删查效率极高，是最快的键值存储容器。
• 劣势：元素无序，最坏情况性能退化，有重哈希开销，内存碎片化。
• 适用：对顺序无要求、追求极致查找性能的场景。

---

四、核心容器对比总结

表格

容器	底层结构	迭代器类型	随机访问	插入删除（平均）	查找（平均）	有序性	适用场景
vector	动态数组	随机访问迭代器	O(1)	尾部 O (1)，中间 O (n)	O(1)	插入序	随机访问多、尾增删多
list	双向循环链表	双向迭代器	O(n)	O(1)	O(n)	插入序	中间增删多、无需随机访问
map	红黑树	双向迭代器	O(log n)	O(log n)	O(log n)	key 有序	需要有序、性能稳定的键值存储
unordered_map	哈希表（开链）	前向迭代器	O(1)	O(1)	O(1)	无序	追求极致查找速度、无需有序

---

五、补充关键细节

1. 迭代器失效总结

   • vector：扩容全失效；insert/erase 导致操作点之后失效。
   • list：仅被删除元素的迭代器失效。
   • map：仅被删除元素的迭代器失效。
   • unordered_map：重哈希全失效；删除仅被删元素失效。

2. map 的 operator []

   • 若 key 不存在，会自动插入一个默认构造的 value并返回引用，因此只读查找场景建议用find()，避免意外插入。

3. 自定义类型适配

   • map：需提供operator<或自定义比较函数。
   • unordered_map：需提供哈希函数（可特化std::hash）和相等判断函数。