STL思维导图

这是一篇关于STL的思维导图，必备复习资料分享，方便大家备考时翻阅查看，提高复习效率，希望对大家备考有所帮助。

STL

• Sequence containers
  • array C++11
    • 静态连续数组，聚合类型 aggregate type
    • 使用
      • 默认构造的数组不为空
      • swapping 复杂度是线性的
      • 长度为 0 的 array，array.begin() == array.end() 对此 array 调用 front() 或 back() 结果不确定
      • 通常在 array 的整个生命周期中，迭代器永不失效
  • vector
    • 动态连续数组，封装动态大小的数组，连续存储（既可通过迭代器读取，又可通过偏移量读取）
    • 使用
      • 按需增长，通常分配比 array 更多的内存，因为如需增长需要整体开辟一块大内存然后整体复制过去。
      • 多余的内存可以通过 shrink_to_fit() 还给系统
      • reserve() 提前分配足够的内存，防止后续内存不够进行再分配操作
      • vector<bool> 特殊实现，节省内存
  • deque
    • 双端队列；存储不连续；支持头尾快速插入和删除，典型的实现是通过数个大小固定的数组，索引需要 2 次指针解引用（vector只需要一次）
    • 使用
      • 按需增长，内存增长消耗比 vector 小，因为不需要复制已有元素到新的内存位置 但是，当只有一个元素的时候，还是要分配整个内部数组
  • forward_list C++11 单向链表
    • 单链表；支持任意位置快速插入和删除；与 std::list 相比，该容器在不需要双向迭代时更省空间
    • 使用
      • 删除元素不会使迭代器失效，关联元素被删时才会失效（ erase_after(pos) 会使迭代器或引用失效（删掉pos后面那个元素））
  • list
    • 双向链表，支持常数时间在任意位置插入和删除
    • 使用
      • 删除元素不会导致迭代器或引用失效，关联元素被删时才会失效
• Associative containers
  • set
    • 红黑树（自平衡二叉查找树）；搜索、插入和删除操作时间复杂度O(log)；按各元素排序，且各个元素唯一
  • map
    • 红黑树（自平衡二叉查找树）；时间复杂度O(log)；根据唯一 key 排序，value 可以重复；
  • multiset
    • 红黑树（自平衡二叉查找树）；时间复杂度O(log)；可以有相同的元素
  • multimap
    • 红黑树（自平衡二叉查找树）；时间复杂度O(log)；1 key 对多 value
• Unordered associative containers
  • unordered_set
    • 查找、插入和删除时间复杂度常数O(1)
  • unordered_map
    • 查找、插入和删除时间复杂度常数O(1)
  • unordered_multiset
    • 查找、插入和删除时间复杂度常数O(1)
  • unordered_multimap
    • 查找、插入和删除时间复杂度常数O(1)
• Container adaptors
  • stack
    • 栈，后进先出LIFO
  • queue
    • 队列，先进先出FIFO
  • priority_queue 优先级队列
    • 可用于构造堆，查找时间复杂度常数O(1) ， 插入和删除时间复杂度O(log)
    • 大顶堆：priority_queue<int> q;，大的数在前边。 小顶堆：priority_queue<int, vector<int>, greater<int> > q;，小的数在前边。
• Span
  • span C++20