⚔️ STL 与 语言基础

Q1. 关于 Vector 扩容 (STL 源码)

1. 原地还是异地？

• 答案：绝大多数情况下是 异地扩容 (Reallocation)。
• 原理：std::vector 要求内存必须是 连续的。当 capacity 不足时，如果在当前内存块后面紧接着没有足够的空闲空间（通常都没有，因为堆内存分配是紧凑的），系统就必须去寻找一块新的、更大的内存区域（通常是当前大小的 1.5 倍或 2 倍）。

2. 关键追问：迭代器/指针/引用会发生什么？(🔥 高危点)

• 答案：全部失效 (Invalidated)。
• 后果：这是 C++ 新手最容易写出的 Core Dump (程序崩溃) 原因之一。
• 过程：
  1. 申请新地址 (New Address)。
  2. 将旧数据 复制 (Copy) 或 移动 (Move) 到新地址。
  3. 释放 (Free) 旧地址的内存。
• 惨案现场：如果你在扩容前保存了一个指向 vector[0] 的指针 p，扩容后，p 仍然指向那个被释放的旧地址（悬空指针）。再次访问 *p 就是 未定义行为 (Undefined Behavior)。

3. 时间复杂度： 还是 ？

• 答案：
  • 单次扩容操作：是 。因为需要把 个元素搬家。
  • 平均（摊销）复杂度：是 。
• 为什么叫“摊销 (Amortized)”？ 想象你是一个搬运工。虽然每隔一段时间你会经历一次极其痛苦的“大搬家”（），但因为每次搬家后空间都翻倍了，下一次大搬家在很久很久之后才会发生。将那一次 的开销平摊到这期间成千上万次 的 push_back 操作上，每一次的平均成本就是一个常数。

---

Q2. 关于 String SSO (Small String Optimization)

1. 短字符串存在哪里？

• 答案：栈 (Stack)。
• 详解：std::string 对象本身的结构中包含了一个小的固定缓冲区（Buffer）。
  • 短字符串：直接存在这个对象内部的 Buffer 里。因为 std::string 对象通常在栈上，所以数据也在栈上。
  • 长字符串：Buffer 存不下，才会去 堆 (Heap) 上 malloc 内存，对象内部只存一个指向堆内存的指针。

2. SSO 解决了什么性能问题？

• 答案：
  1. 减少系统调用：new/malloc 是昂贵的操作，需要操作系统介入寻找空闲堆块。SSO 避免了频繁的小内存分配。
  2. 缓存友好 (Cache Locality)：栈内存通常已经在 CPU 的 L1/L2 缓存中，访问速度极快。而堆内存可能分散在物理内存的任何地方，容易导致 Cache Miss。

3. sizeof(std::string) 是多少？

• 答案：是 固定值。不随字符串长度变化。
• 数值：
  • 在 64位 Linux (GCC/libstdc++) 上通常是 32 字节。
  • 在 64位 Windows (MSVC) 或 Clang (libc++) 上通常是 24 字节。
• 理解：sizeof 衡量的是对象“句柄”的大小（包含指针、长度、容量、以及那个 SSO 的小 Buffer），而不是它管理的动态数据的总大小。

---

Q3. 指针 vs 引用 (C++ 基础)

1. 汇编层面如何实现？占内存吗？

• 汇编层面：引用和指针 完全一样。引用在底层就是通过“指针”实现的，它存储的也是对象的内存地址。
• 占内存吗：占。虽然 C++ 标准不说引用占内存，但在运行时，编译器通常会把引用作为指针处理，它需要占用寄存器或栈空间来存储那个地址（64位系统下就是 8 字节）。

2. 场景辨析：链表查找返回 Node* 还是 Node&？

• 答案：必须用 Node*。
• 理由：
  • 查找失败的情况：链表中可能找不到目标值。指针可以返回 nullptr 来表示“没找到”。
  • 引用的铁律：引用必须绑定到一个合法的对象，不存在“空引用”。如果你非要返回引用，当没找到时，你抛出异常吗？还是返回一个伪造的“空节点”？这都会让接口变得笨重。

---

Q4. Const 限定符 (C++ Primer)

这是阅读代码和写出高质量迭代器的基本功。

口诀：“划线法” —— 以 * 为界，谁在 const 右边，谁就不可变。

1. 区别解析

A. const int * p (底层 const)

• * 在 const 右边。
• 理解：p 指向的东西是常量。
• 权限：
  • 我可以改变 p 指向别的地址 (p = &b ✅)
  • 但我 不能 通过 p 修改它指向的值 (*p = 10 ❌)。
• 应用：函数参数 void print(const int* arr)，防止函数内部篡改数组内容。

B. int * const p (顶层 const)

• p 在 const 右边。
• 理解：p 这个指针本身是常量。
• 权限：
  • p 一旦初始化就不能指向别处 (p = &b ❌)
  • 但我 可以 修改它指向的值 (*p = 10 ✅)。
• 应用：像引用一样，绑定了就不许变。

2. 实现“只读迭代器” (const_iterator)

• 逻辑选择：应该采用 const int * p 的逻辑。
• 为什么：
  • 迭代器需要能移动（比如 it++ 遍历链表），所以指针本身必须能变（不能是 int * const p）。
  • 只读意味着不能通过迭代器修改元素，所以指向的数据必须是 const。

哈希表 (Hash Table)

Q1：内存管理：在你的 MyHashTable 析构函数中，如果只写 buckets.clear() 而不手动遍历链表 delete 节点，会发生什么？为什么 vector 销毁时不会自动释放它存的指针指向的内存？

答案：内存泄漏 (Memory Leak)。

• 原理：vector 对象销毁时，确实会释放它占用的内存。但它占用的内存仅仅是 “存指针的那块空间”（比如 10007 个小格子的空间）。

• 后果：那些通过 new HashNode 申请出来的节点（具体的“房子”），是存在 堆 (Heap) 上的。如果你不手动顺着指针去把它们一个个拆掉（delete），它们就会永远悬浮在内存里，直到程序结束。操作系统的内存管理器不知道这些内存已经没用了。

Q2:底层原理：在 vector<list<pair<int,int>>> 这种结构中，如果哈希表进行了一次 rehash (扩容)，原本指向某个元素的 迭代器 (iterator) 会失效吗？引用 (reference) 会失效吗？为什么？

答案：

• 迭代器 (Iterator)：会失效。
  • 当你持有 buckets.begin() 这种指向 vector 格子的迭代器时，一旦 vector 扩容，整个公寓楼搬迁到新地址，你手里的旧地址（迭代器）就变成了野指针。
• 引用/指针 (Reference/Pointer)：指向数据的引用不会失效（在 vector<list> 场景下）。
  • 这是 std::list 的特性。list 的节点是独立分配在堆上的。虽然 vector 搬家了，导致 list 的管理头节点移动了，但 list 里面存数据的那些节点（Node）在堆里的位置是不动的。
  • 注意：如果是 std::unordered_map 标准容器，标准规定：Rehash 会使所有迭代器失效，但元素的引用和指针保持有效。（原理同上，数据节点不动，只是挂到了新的桶位置）。

Q3:场景辨析：unordered_map 的平均查找复杂度是 ，但最坏情况是 。请问什么情况下会触发最坏情况？作为开发者，如何避免这种情况？（提示：与哈希函数有关）。

答案：

• 触发条件：严重的哈希冲突 (Hash Collision)。
  • 极端情况：所有的 Key 计算出来的哈希值都一样（比如 hash(key) = 1）。
  • 结果：所有数据都挂在同一个桶的链表上。哈希表变成了“一根链表”。查找时必须遍历这根长链表，复杂度变成 。
• 如何避免：
  1. 设计好的哈希函数：保证输出结果在桶范围内均匀分布，避免聚集。
  2. 桶的数量要是质数：使用质数（如 10007）取模，能有效减少因数据某种规律（如等差数列）导致的冲突。
  3. 扩容机制 (Load Factor)：当 元素总数 / 桶的总数 > 0.75 时，自动扩容（Rehash），把桶的数量翻倍，把数据重新分散开。
  4. (进阶回答)：Java 8 的 HashMap 在链表过长（>8）时，会将链表转化为 红黑树，将复杂度从 优化到 。