序列式容器

1️⃣ C++ 容器有哪些？

  • 序列式容器： vector、list
  • 关联式容器： map、unoredred_map

2️⃣ vector 超出容量会怎样？

  • vector 会先申请一块 1.5/2 倍 的当前内存大小的连续内存;
  • 把原来元素 拷贝/移动 到新内存;
  • 释放旧内存，再把新元素插进去

3️⃣ vector 扩容后会带来什么后果？

  • 因为元素移动到了新内存，所以原来元素的地址可能全变了。
  • 凡是指向原来 vector 内部元素的 迭代器、指针、引用失效

4️⃣ vector 如果申请新内存失败会怎样

  • 可能抛出异常，一般是 std::bad_alloc

5️⃣ size() 和 capacity() 的区别?

  • size()： 当前已经有多少个元素
  • capacity()： 当前底层内存最多还能容纳多少个元素而不触发扩容

6️⃣ resize() 和 reserve() 的区别?

  • reserve()： 让 vector 的内存容量至少达到 n，避免后续频繁扩容。
    • n <= capacity()：通常什么都不做;
    • n > capacity()：重新触发分配内存，导致迭代器、指针、引用失效
  • resize()： 让 vector 里实际元素个数改成 n。
    • size 变大：新增加的元素会被默认初始化;
    • size 变小：会销毁多余元素
    • size > capacity，也可能触发扩容

7️⃣ reserve 后能不能直接下标访问？

  • 不能。为 reserve 只保证内存够了，但没有真正构造元素。

8️⃣ vector 和 list 的区别?

  • 底层结构不同
    • vector：底层是 连续内存的动态数组
    • list：底层是 双向链表
  • 随机访问能力不同
    • vector 支持随机访问，O(1)
    • list 不支持随机访问，O(n)
  • 插入删除效率不同
    • 尾插 O(1)，中间 O(n)
    • 插入、删除是 O(1)
  • 内存开销不同
    • vector 只存元素本身，额外开销小；
    • list 点除了数据，还要存前驱/后继指针，额外开销更大；
  • 缓存局部性不同
    • vector 连续存储，CPU cache 命中率高，遍历速度快；
    • list 节点离散，cache 局部性差，遍历速度慢；

关联式容器

1️⃣ map 和 unordered_map 的区别?

  • 底层实现不同
    • map：底层一般是 红黑树
    • unordered_map：底层一般是 哈希表
  • 元素是否有序
    • map: 元素会按照 key 的大小自动 有序排列
    • unordered_map：哈希分布存储的，无序
  • 查找 / 插入 / 删除复杂度
    • map
      • 查找：O(log n)
      • 插入：O(log n)
      • 删除：O(log n)
    • unordered_map
      • 平均查找：O(1)
      • 平均插入：O(1)
      • 平均删除：O(1)

2️⃣ map 的 key 是自定义的类，需要注意什么?

  • 类要实现 < 的重载，保证 key 可以比较（也可以是函数对象）

3️⃣ 红黑树怎么插入和删除？

  • 定义：红黑树本质上是一个 自平衡二叉搜索树。
  • 性质：
    • 根节点是 黑色；
    • 所有叶子空节点（NIL 节点）都是 黑色；
    • 红色节点 只能有 黑色节点 的 孩子；
    • 从任意节点到其所有后代 NIL 节点的路径上，黑色节点数量相同；
  • 插入：
    • 先按二叉搜索树插进去，新节点 一般设为 红色。
    • 如果 父节点 也是红色，就违反了红黑树性质，这时分 叔叔节点 讨论：
      • 叔叔红就变色
      • 叔叔黑就结合旋转和变色修复