STL再探

看了半天的手撕STL最后面试答的依托答辩，真服了，重新看一下吧

C++ STL 容器的底层实现

C++ 标准模板库（STL）中的容器是高效、灵活的数据结构实现，用于存储和管理数据集合。STL 容器分为三大类：序列容器、关联容器、无序关联容器，以及一类特殊的容器适配器。

1. 序列容器 (Sequence Containers)

序列容器以线性方式存储元素，支持按顺序访问。底层实现通常基于数组或链表。

1.1 std::vector

• 底层实现：动态数组（Dynamic Array）
  • 元素存储在连续内存中。
  • 使用三个指针管理：begin（指向数组开头）、end（指向最后一个元素的下一位置）、capacity（指向分配内存的末尾）。
  • 当插入元素导致大小超过容量时，重新分配更大的内存（通常按 1.5x 或 2x 增长），复制现有元素，并释放旧内存。
• 关键特性：
  • 随机访问：O(1)（通过索引）。
  • 末尾插入/删除：均摊 O(1)（可能触发重新分配）。
  • 中间插入/删除：O(n)，需移动后续元素。
  • 内存分配使用 std::allocator。
• 实现细节：
  • 扩容时通常倍增容量（常见实现为 2x，但标准未强制）。
  • 使用 placement new 在预分配内存上构造元素。
• 为何选择动态数组：
  • 连续内存提供高效的随机访问和缓存友好性。
  • 适合需要频繁访问但插入/删除较少的场景。

1.2 std::array (C++11)

• 底层实现：固定大小的静态数组
  • 封装了 C 风格数组，存储在栈上或嵌入对象中。
  • 大小在编译期确定，内存布局与 T[N] 完全一致。
• 关键特性：
  • 随机访问：O(1)。
  • 无动态分配，插入/删除不可用。
  • 提供 STL 容器接口（如 begin()、end()）。
• 实现细节：
  • 内存布局与原始数组相同，零开销。
  • 不管理动态内存，无需 std::allocator。
• 为何选择静态数组：
  • 适合固定大小、性能敏感的场景（如嵌入式系统）。
  • 提供与 STL 算法兼容的接口，优于裸数组。

1.3 std::deque (Double-Ended Queue)

• 底层实现：分块数组（Block Array）
  • 使用多个固定大小的连续内存块（通常为数组），通过一个索引数组（或指针数组）连接。
  • 每个块存储若干元素，索引数组记录块的地址。
  • 支持两端高效插入/删除。
• 关键特性：
  • 随机访问：O(1)（通过计算块索引和块内偏移）。
  • 两端插入/删除：O(1)（通常不触发重新分配）。
  • 中间插入/删除：O(n)，需移动元素。
• 实现细节：
  • 索引数组（称为“map”）存储指向各内存块的指针。
  • 内存块大小通常为固定值（如 512 字节），由实现定义。
  • 使用 placement new 构造元素。
• 为何选择分块数组：
  • 兼顾随机访问和两端操作的效率。
  • 比 std::vector 更适合频繁两端插入的场景，但内存不完全连续，缓存友好性稍差。

1.4 std::list

• 底层实现：双向链表（Doubly-Linked List）
  • 每个节点包含元素、指向前驱和后继的指针。
  • 节点动态分配，内存非连续。
• 关键特性：
  • 无随机访问，需遍历：O(n)。
  • 插入/删除：O(1)（已知节点位置）。
  • 迭代器在插入/删除后保持有效（除非删除当前节点）。
• 实现细节：
  • 通常包含哨兵节点（dummy node）简化边界操作。
  • 使用 std::allocator 分配节点。
• 为何选择双向链表：
  • 适合频繁插入/删除但不需随机访问的场景。
  • 内存非连续，缓存性能较差。

2. 关联容器 (Associative Containers)

关联容器存储键值对或键，元素按键排序，提供高效查找。底层实现通常基于平衡二叉树。

2.1 std::set 和 std::multiset

• 底层实现：红黑树（Red-Black Tree）
  • 自平衡二叉搜索树，保持键的排序。
  • 每个节点包含键、颜色（红/黑）、左右子节点和父节点指针。
  • std::multiset 允许重复键。
• 关键特性：
  • 查找、插入、删除：O(log n)。
  • 元素按键排序，自动去重（std::set）。
  • 迭代器提供有序遍历。
• 实现细节：
  • 使用 std::allocator 分配节点。
  • 红黑树保证平衡，插入/删除后通过旋转和颜色调整维持 O(log n)。
• 为何选择红黑树：
  • 提供稳定的 O(log n) 性能。
  • 适合需要排序和快速查找的场景。

2.2 std::map 和 std::multimap

• 底层实现：红黑树（Red-Black Tree）
  • 类似 std::set，但节点存储键值对（std::pair<const Key, T>）。
  • std::multimap 允许重复键。
• 关键特性：
  • 查找、插入、删除：O(log n)。
  • 按键排序，迭代器返回键值对。
• 实现细节：
  • 红黑树节点包含 std::pair<const Key, T>。
  • 使用比较器（默认 std::less<Key>）维护键的顺序。
• 为何选择红黑树：
  • 高效的键值查找和排序。
  • 适合需要键值映射且保持排序的场景。

3. 无序关联容器 (Unordered Associative Containers, C++11)

无序关联容器提供快速查找，元素不排序，基于哈希表实现。

3.1 std::unordered_set 和 std::unordered_multiset

• 底层实现：哈希表（Hash Table）
  • 使用桶（buckets）数组，每个桶存储一个链表（或类似结构）处理冲突。
  • 哈希函数将键映射到桶，冲突通过链表（或红黑树，C++11 起部分实现优化）解决。
  • std::unordered_multiset 允许重复键。
• 关键特性：
  • 查找、插入、删除：均摊 O(1)，最坏 O(n)（冲突严重时）。
  • 无序，迭代器不保证顺序。
  • 负载因子（load factor）控制桶数量，影响性能。
• 实现细节：
  • 默认哈希函数为 std::hash<Key>，可自定义。
  • 桶数量动态调整（rehash），保持负载因子低于最大值。
• 为何选择哈希表：
  • 提供接近 O(1) 的查找性能。
  • 适合不需要排序的高速查找场景。

3.2 std::unordered_map 和 std::unordered_multimap

• 底层实现：哈希表（Hash Table）
  • 与 std::unordered_set 类似，但存储键值对（std::pair<const Key, T>）。
  • std::unordered_multimap 允许重复键。
• 关键特性：
  • 查找、插入、删除：均摊 O(1)，最坏 O(n)。
  • 无序，键值对存储。
• 实现细节：
  • 桶内冲突通常用链表解决，部分实现（如 libstdc++）在高冲突时用红黑树优化。
  • 使用 std::allocator 分配桶和节点。
• 为何选择哈希表：
  • 高效键值查找，适合无序键值映射。

4. 容器适配器 (Container Adaptors)

容器适配器基于其他容器提供受限接口，底层实现依赖基础容器。

4.1 std::stack

• 底层实现：基于 std::deque（默认），可指定 std::vector 或 std::list
  • 提供 LIFO（后进先出）接口，仅支持 push、pop、top。
  • 底层容器管理元素存储。
• 关键特性：
  • 插入/删除（push/pop）：O(1)（依赖底层容器）。
  • 无迭代器，仅访问栈顶。
• 实现细节：
  • 默认使用 std::deque 提供高效尾部操作。
  • 可通过模板参数自定义底层容器（需支持 push_back、pop_back、back）。
• **为何选择 std::deque**：
  • 尾部操作高效，内存管理灵活。
  • std::vector 也可用于节省内存，std::list 适合频繁插入。

4.2 std::queue

• 底层实现：基于 std::deque（默认），可指定 std::list
  • 提供 FIFO（先进先出）接口，支持 push（尾部）、pop（头部）、front、back。
• 关键特性：
  • 插入（push）：O(1)。
  • 删除（pop）：O(1)（依赖底层容器）。
  • 无迭代器，仅访问队首/队尾。
• 实现细节：
  • 默认 std::deque 支持高效两端操作。
  • 不使用 std::vector，因为头部删除效率低（O(n)）。
• **为何选择 std::deque**：
  • 两端操作高效，适合队列语义。

4.3 std::priority_queue

• 底层实现：基于 std::vector（默认），使用堆（Heap）算法
  • 底层容器存储元素，堆算法（std::make_heap、std::push_heap、std::pop_heap）维护优先级。
  • 默认大顶堆（最大元素优先）。
• 关键特性：
  • 插入（push）：O(log n)。
  • 删除（pop）：O(log n)。
  • 访问最大/最小元素：O(1)。
• 实现细节：
  • 使用 std::vector 提供连续内存，适合堆操作。
  • 可自定义比较器（如 std::less<T> 或 std::greater<T>）。
• **为何选择 std::vector**：
  • 连续内存适合堆算法的随机访问。
  • 扩容效率高，尾部插入快。

5. 其他注意事项

• 标准未强制具体实现：C++ 标准仅规定容器的时间复杂度和行为，具体数据结构由实现决定。例如，std::map 可能使用红黑树或其他平衡树（如 AVL 树），但红黑树是主流选择。
• 内存管理：所有容器使用 std::allocator（或自定义分配器）管理内存，确保灵活性和可扩展性。
• 线程安全：STL 容器不提供内置线程安全，需用户自行加锁。
• 迭代器失效：
  • std::vector：插入可能导致所有迭代器失效（若重新分配内存）。
  • std::list：插入/删除不影响其他迭代器。
  • std::map/std::set：插入不失效，删除可能失效被删除元素的迭代器。

6. 总结表格

容器	底层数据结构	插入复杂度	删除复杂度	查找复杂度	随机访问	典型用途
std::vector	动态数组	O(1) 均摊	O(1) 均摊	O(1)	是	动态数组、随机访问
std::array	静态数组	不支持	不支持	O(1)	是	固定大小数组
std::deque	分块数组	O(1) 两端	O(1) 两端	O(1)	是	双端队列
std::list	双向链表	O(1)	O(1)	O(n)	否	频繁插入/删除
std::forward_list	单向链表	O(1)	O(1)	O(n)	否	内存敏感、前向遍历
std::set/multiset	红黑树	O(log n)	O(log n)	O(log n)	否	有序集合、去重
std::map/multimap	红黑树	O(log n)	O(log n)	O(log n)	否	有序键值映射
std::unordered_set/multiset	哈希表	O(1) 均摊	O(1) 均摊	O(1) 均摊	否	无序集合、快速查找
std::unordered_map/multimap	哈希表	O(1) 均摊	O(1) 均摊	O(1) 均摊	否	无序键值映射
std::stack	std::deque (默认)	O(1)	O(1)	不支持	否	LIFO 栈
std::queue	std::deque (默认)	O(1)	O(1)	不支持	否	FIFO 队列
std::priority_queue	std::vector + 堆	O(log n)	O(log n)	O(1) 顶部	否	优先级队列