一、STL容器总览

口诀：三容器两适配，序列关联加无序

1.1 容器分类

  • 序列容器：vector(动态数组)、list(双向链表)、deque(双端队列)、array(固定数组)、forward_list(单向链表)
  • 关联容器：set(有序唯一集合)、map(有序键值对)、multiset(有序可重复集合)、multimap(有序可重复键值对)
  • 无序容器：unordered_set、unordered_map、unordered_multiset、unordered_multimap
  • 容器适配器：stack(栈)、queue(队列)、priority_queue(优先队列)

1.2 底层结构与性能对比

  • vector/deque: 动态数组，支持随机访问
  • list/forward_list: 链表，高效插入删除
  • set/map: 红黑树，有序且查找/插入为O(logN)
  • unordered_*: 哈希表，平均O(1)查找/插入，无序

二、序列容器详解

口诀：vector动态连续，list插入灵活，deque双端高效，array固定性能高

2.1 vector（动态数组）

  • 核心特性：连续内存存储，随机访问O(1)，尾部插入删除高效
  • 内存管理：通过三个指针维护：start(起始)、finish(当前末尾)、end_of_storage(容量末尾)
  • 扩容机制：空间不足时，分配1.5~2倍新内存(GCC为2倍，VS为1.5倍)，复制/移动元素后释放旧内存
  • push_back vs emplace_back
    • push_back：复制/移动已创建对象到容器末尾
    • emplace_back：直接在容器末尾原地构造对象，避免临时对象开销

2.2 list（双向链表）

  • 核心特性：节点不连续存储，每个节点包含前后指针，支持双向遍历
  • 性能特点：任意位置插入删除O(1)，不支持随机访问(O(n))
  • 插入删除实现：创建新节点并调整相邻节点指针；删除时释放目标节点并重连指针
  • 缓存友好性：节点分散导致缓存命中率低，遍历速度慢于vector

2.3 deque（双端队列）

  • 核心结构：中控器(map数组)+多个缓冲区，每个缓冲区存储固定数量连续元素
  • 性能特点：头尾插入删除O(1)，中间插入删除O(n)，随机访问O(1)
  • 与vector区别：deque无需整体扩容(只需添加新缓冲区)，但随机访问稍慢

2.4 array（固定数组）

  • 核心特性：编译时固定大小，栈上分配内存(全局/动态分配除外)
  • 使用场景：元素数量固定、性能要求高、无需扩容的场景
  • 对比vector：无需动态内存管理，访问速度更快，但大小不可变

三、关联容器详解

口诀：map键值对，set存键值，multi允重复，查找logN

3.1 map与set共性

  • 底层实现：均基于红黑树，保证元素有序存储
  • 性能特点：查找、插入、删除操作均为O(logN)
  • 迭代器特性：遍历有序，且插入/删除不影响其他元素的迭代器(节点地址不变)

3.2 map与set区别

  • 存储内容：map存储键值对(pair<const Key, T>)，set仅存储键(元素)
  • 访问方式：map支持operator[]通过键访问值，set只能通过迭代器访问
  • 用途不同：map适用于字典/映射场景，set适用于去重/集合操作

3.3 multimap与multiset

  • 核心特点：允许键重复，其他特性与map/set类似
  • 排序规则：multimap中相同键的元素按值排序；multiset中相同值的元素内部有序
  • 查找方法：需要使用lower_bound/upper_bound/equal_range查找范围

3.4 元素查找方法

  • find()：查找特定键，返回迭代器，未找到则返回end()
  • count()：返回指定键的元素个数(map/set返回0或1)
  • lower_bound()：返回不小于给定键的首个元素迭代器
  • upper_bound()：返回大于给定键的首个元素迭代器
  • equal_range()：返回包含lower_bound和upper_bound的迭代器对

四、无序容器详解

口诀：无序基于哈希表，平均查找O(1)，无自动排序

4.1 unordered_map与map区别

  • 底层实现：unordered_map基于哈希表，map基于红黑树
  • 性能差异：unordered_map平均O(1)查找/插入，最坏O(n)；map稳定O(logN)
  • 有序性：map自动按键排序，unordered_map无序
  • 内存开销：unordered_map需额外空间存储哈希表桶
  • 迭代器失效：unordered_map在扩容时所有迭代器失效，map仅被删除元素的迭代器失效

五、容器适配器

口诀：stack后进先出，queue先进先出，priority_queue优先级

5.1 stack（栈）

  • 底层实现：默认基于deque实现，也可使用list或vector
  • 核心操作：push(入栈)、pop(出栈)、top(访问栈顶)、empty(判空)
  • 特点：后进先出(LIFO)，仅允许访问栈顶元素

5.2 queue（队列）

  • 底层实现：默认基于deque实现，也可使用list
  • 核心操作：push(入队)、pop(出队)、front(队首)、back(队尾)、empty(判空)
  • 特点：先进先出(FIFO)，允许访问队首和队尾

5.3 priority_queue（优先队列）

  • 底层实现：基于vector实现的二叉堆结构
  • 核心特性：自动保持最大元素在队首(默认大顶堆)
  • 性能特点：插入O(logN)，获取最大元素O(1)
  • 应用场景：任务调度、事件处理等需要优先级的场景

六、迭代器详解

口诀：迭代器是容器指针，不同容器类型异，失效规则要牢记

6.1 迭代器类型与功能

  • 输入迭代器：只读一次，只能递增
  • 输出迭代器：只写一次，只能递增
  • 前向迭代器：可读写多次，只能递增(如forward_list)
  • 双向迭代器：可读写多次，可递增递减(如list、map、set)
  • 随机访问迭代器：可读写多次，支持随机访问(如vector、deque、array)

6.2 迭代器失效情况

  • vector：插入/删除元素可能导致插入点之后的迭代器失效；扩容时所有迭代器失效
  • deque：头部/尾部插入可能使迭代器失效(取决于实现)；中间插入使所有迭代器失效
  • list：插入不影响任何迭代器；删除只影响被删除元素的迭代器
  • map/set：插入/删除不影响其他元素的迭代器
  • unordered_*：插入可能导致扩容，使所有迭代器失效；删除只影响被删除元素的迭代器

七、STL容器使用场景总结

口诀：vector随机访问，list频繁插入，map有序映射，unordered_map高效查找

  • vector：需要随机访问、动态扩容的场景(如vector scores)
  • list：频繁在中间插入删除的场景(如list history)
  • deque：需要双端操作的场景(如deque window)
  • map：需要按键排序的键值对场景(map<string, int> dict)
  • unordered_map：需要高效查找的键值对场景(unordered_map<int, User> users)
  • set：需要去重且有序的集合场景(set unique_ids)
  • priority_queue：需要优先级处理的场景(priority_queue tasks)

八、重要概念辨析

口诀：resize改大小，reserve预分配，erase返下一，迭代器失效各不同

8.1 resize()与reserve()区别

  • resize(n)：改变容器大小，若n大于当前size则创建新元素，否则销毁多余元素
  • reserve(n)：预分配内存但不创建元素，只改变capacity，不改变size
  • 使用建议：预先知道元素数量时，使用reserve()避免多次扩容

8.2 erase()返回值与迭代器更新

  • vector/list/deque：erase(iter)返回指向下一个元素的迭代器
  • map/set：erase(iter)不返回值，需手动更新迭代器
  • 使用示例：
    1
    2
    3
    4
    5
    6
    7
    8
    // 正确遍历删除方式
    for (auto it = container.begin(); it != container.end();) {
        if (need_remove(*it)) {
            it = container.erase(it); // 使用返回值更新迭代器
        } else {
            ++it;
        }
    }

8.3 map/set迭代器不失效原因

  • 基于红黑树实现，插入/删除操作仅调整节点间的指针，不移动节点位置
  • 被删除的节点迭代器失效，但其他节点的迭代器不受影响
  • 因此可以安全地在遍历过程中删除元素(需正确更新迭代器)