1. 核心摘要

本篇笔记详细整理了 C++ 标准模板库 (STL) 中核心数据结构（容器）的特性、适用场景及常用操作。重点解析了 Vector 的动态扩容机制、Map 与 Unordered_map 的底层区别，以及迭代器失效等关键问题，旨在帮助开发者在实际编程中做出最优的数据结构选择。

2. 关键概念/术语

  • 容器 (Containers)：用于存储和管理数据的对象，分为序列式容器（如 vector, list）和关联式容器（如 map, set）。
  • 迭代器 (Iterators)：连接容器与算法的桥梁，提供了一种统一访问容器元素的方法，类似于指针。
  • 底层实现 (Underlying Implementation)：指数据结构在内存中的具体组织方式（如数组、链表、红黑树、哈希表），直接决定了操作的时间复杂度。
  • 均摊复杂度 (Amortized Complexity)：指一系列操作的平均耗时。例如 vector 扩容虽然偶尔耗时，但平均下来插入操作是 $O(1)$。

3. 详细内容整理

3.1 序列式容器 (Sequence Containers)

Vector (动态数组)

最常用的容器，支持随机访问。

  • 特性：连续内存空间，尾部插入/删除效率高，头部或中间插入/删除效率低。
  • 常用操作：
    • push_back(val): 尾部插入。
    • pop_back(): 尾部删除。
    • operator[] / at(): 访问元素（at 带边界检查）。
    • resize(n) / reserve(n): 调整大小 / 预分配容量。
    • front() / back(): 返回首/尾元素引用。

Deque (双端队列)

  • 特性：分段连续内存，支持头尾高效插入/删除。
  • 常用操作：
    • push_front(val) / push_back(val): 头/尾插入。
    • pop_front() / pop_back(): 头/尾删除。

List (双向链表)

  • 特性：非连续内存，支持任意位置高效插入/删除，不支持随机访问。
  • 常用操作：
    • push_back / push_front: 插入。
    • insert(iterator, val): 在指定位置前插入。
    • erase(iterator): 删除指定位置元素。
    • splice(): 链表拼接（高效移动元素）。

3.2 容器适配器 (Container Adapters)

Stack (栈)

  • 特性：先进后出 (LIFO)，默认基于 deque 实现。
  • 常用操作：
    • push(val): 入栈。
    • pop(): 出栈（无返回值）。
    • top(): 获取栈顶元素。
    • empty(): 判空。

Queue (队列)

  • 特性：先进先出 (FIFO)，默认基于 deque 实现。
  • 常用操作：
    • push(val): 入队。
    • pop(): 出队。
    • front(): 获取队头。
    • back(): 获取队尾。

Priority_queue (优先队列)

  • 特性：基于堆 (Heap) 实现，默认大顶堆（最大元素在 top）。
  • 常用操作：
    • push(val): 插入元素并调整堆。
    • pop(): 删除堆顶元素。
    • top(): 获取优先级最高的元素。

3.3 关联式容器 (Associative Containers)

此类容器底层通常基于红黑树实现，插入和查找的时间复杂度均为 $O(\log n)$，且存储是自动排序的。

Set (唯一键集合)

  • 特性：元素即 Key，不允许重复，插入后自动排序。
  • 常用操作：
    • insert(val): 插入元素（若已存在则插入失败）。
    • erase(val): 删除指定值的元素。
    • find(val): 查找元素，返回迭代器。
    • count(val): 返回 1（存在）或 0（不存在）。
    • lower_bound(val): 返回第一个 $\ge$ val 的迭代器。

Multiset (多重集合)

  • 特性：允许存储重复的元素，自动排序。
  • 常用操作：
    • insert(val): 插入元素（总是成功）。
    • erase(val): 删除所有等于 val 的元素。
    • erase(iterator): 仅删除迭代器指向的那一个元素。
    • count(val): 返回元素出现的次数。
    • equal_range(val): 返回 pair，包含等于 val 的元素范围 [first, last)。

Map (唯一键映射)

  • 特性：存储 Key-Value 对，Key 唯一且排序。
  • 常用操作：
    • insert({key, val}): 插入键值对。
    • operator[key]: 访问元素。若 Key 不存在，会创建一个默认值的元素插入。
    • at(key): 访问元素。若 Key 不存在，抛出异常。
    • erase(key): 删除指定 Key 的键值对。
    • find(key): 查找 Key，返回指向 pair 的迭代器。

Multimap (多重映射)

  • 特性：允许 Key 重复，按 Key 排序。不支持 operator[] 和 at()。
  • 常用操作：
    • insert({key, val}): 插入键值对。
    • erase(key): 删除所有该 Key 的键值对。
    • find(key): 返回第一个该 Key 的迭代器。
    • count(key): 统计该 Key 的数量。
    • equal_range(key): 获取该 Key 对应的所有 Value 的范围。

3.4 无序容器 (Unordered Containers)

此类容器基于哈希表 (Hash Table) 实现，内部元素无序。优势是平均增删查改复杂度为 $O(1)$，但在哈希冲突严重时退化为 $O(n)$。

Unordered_set (无序唯一集合)

  • 特性：存储唯一元素，无特定顺序，利用 Hash 函数组织数据。
  • 常用操作：
    • insert(val): 插入元素。
    • erase(val): 删除元素。
    • find(val): 查找元素，返回迭代器。
    • count(val): 检查元素是否存在（0 或 1）。
    • bucket_count(): 返回当前桶的数量（常用于性能调试）。

Unordered_multiset (无序多重集合)

  • 特性：允许存储重复元素，无特定顺序。
  • 常用操作：
    • insert(val): 插入元素。
    • erase(val): 删除所有等于 val 的元素。
    • find(val): 查找任意一个等于 val 的元素迭代器。
    • count(val): 统计元素出现次数。

Unordered_map (无序唯一映射)

  • 特性：存储 Key-Value 对，Key 唯一，无序。
  • 常用操作：
    • insert({key, val}): 插入键值对。
    • operator[key]: 访问或创建元素（若 Key 不存在则默认构造）。
    • at(key): 安全访问，Key 不存在抛异常。
    • erase(key): 删除指定 Key。
    • find(key): 查找 Key。
    • load_factor(): 返回负载因子（元素数量/桶数量），衡量哈希表拥挤程度。

Unordered_multimap (无序多重映射)

  • 特性：允许 Key 重复，Key-Value 对无序。不支持 operator[]。
  • 常用操作：
    • insert({key, val}): 插入键值对。
    • erase(key): 删除所有该 Key 的键值对。
    • find(key): 查找。
    • equal_range(key): 返回 pair，包含所有匹配 Key 的迭代器范围。

4. 关键知识点详解

4.1 Vector 的扩容机制与内存管理

std::vector 之所以高效，在于其巧妙的内存管理策略。

  • Capacity vs Size：
    • size()：当前容器中实际存储的元素个数。
    • capacity()：当前容器已分配内存能容纳的元素个数。
  • 扩容逻辑： 当 push_back 导致 size() > capacity() 时，vector 会触发扩容：
    1. 开辟新空间：通常是当前 capacity 的 1.5倍 或 2倍（取决于编译器实现，如 GCC 是 2 倍，MSVC 是 1.5 倍）。
    2. 数据拷贝：将旧内存区域的数据拷贝（或移动）到新内存区域。
    3. 释放旧空间：销毁旧对象并释放旧内存。
  • 性能影响： 虽然扩容操作涉及内存分配和数据拷贝，是一个 $O(n)$ 的操作，但由于扩容是成倍增长的，插入 $n$ 个元素的总扩容次数是 $\log n$ 级别的。因此，单次插入的均摊复杂度 (Amortized Complexity) 仍为 $O(1)$。
  • 优化建议： 如果在插入前已知大概的数据量，务必使用 reserve(n) 预先分配内存，避免频繁的重新分配和数据拷贝。

4.2 Map 与 Unordered_map 的底层对比

选择正确的 Map 容器对性能至关重要。

特性 std::map std::unordered_map
底层实现 红黑树 (Red-Black Tree) 哈希表 (Hash Table)
有序性 Key 自动递增排序 无序
查找复杂度 $O(\log n)$ (稳定) 平均 $O(1)$，最坏 $O(n)$
插入/删除 $O(\log n)$ 平均 $O(1)$
空间占用 较低 (节点存指针) 较高 (哈希桶+节点)
适用场景 需要按序遍历、范围查找、对稳定性要求高 只需快速查找、无需排序、数据量大

红黑树与哈希表结构示意图

4.3 迭代器失效 (Iterator Invalidation)

这是操作 STL 时最容易导致程序崩溃（Segmentation Fault）的原因。

  1. Vector/Deque 失效：
    • 插入操作：如果插入触发了扩容，所有指向旧内存的迭代器、指针、引用全部失效。如果没有扩容，插入点之后的迭代器失效。
    • 删除操作：被删除元素之后的所有迭代器失效。
    std::vector<int> v = {1, 2, 3, 4};
auto it = v.begin();
v.push_back(5); // 如果触发扩容，it 变成野指针
// std::cout << *it; // 危险操作！
  2. Map/Set/List 失效：
    • 插入操作：不会导致现有迭代器失效（因为节点在内存中是独立的）。
    • 删除操作：仅指向被删除元素的迭代器失效，其他迭代器不受影响。

    正确删除 Map 元素的写法：

    std::map<int, string> m;
auto it = m.begin();
while (it != m.end()) {
    if (it->second == "delete_me") {
        // m.erase(it++); // C++11 之前的经典写法
        it = m.erase(it); // C++11 erase 返回下一个有效迭代器
    } else {
        ++it;
    }
}

4.4 常用算法复杂度速查

在使用 <algorithm> 库时，需清楚其代价：

  • std::sort: 基于快排、堆排和插入排序的混合排序 (Introsort)。平均和最坏复杂度均为 $O(n \log n)$。
  • std::find: 线性查找，$O(n)$。
  • std::binary_search: 二分查找（要求序列已序），$O(\log n)$。
  • std::lower_bound: 二分查找第一个大于等于 value 的位置，$O(\log n)$。