算法面试 C++ 核心常识与避坑指南¶

在国内外一线科技大厂（Google, Meta, 字节跳动, 腾讯, 微软等）的算法面试与高水平周赛中，面试官不仅考察解题思路与时空复杂度，更密切关注候选人书写现代 C++ 代码的工程规范性、底层原理认知、性能直觉与代码健壮性。

本篇系统归纳算法面试中最高频出现、最容易踩坑的 C++ 核心语言特性与 STL 底层机制。

1. 核心 STL 容器原理与高频考点¶

1.1 `std::vector` 底层扩容与迭代器失效¶

std::vector 是基于连续线性内存的动态数组。

1. 扩容机制与均摊复杂度¶

当容量 capacity() 不足时，vector 会向操作系统申请一块更大的全新连续内存（通常按 1.5 倍（MSVC）或 2 倍（GCC / Clang）扩容），将旧元素依次搬迁（移动或拷贝）到新内存并释放旧内存；
单次扩容代价为 \(\mathcal{O}(n)\)，但平摊到每次插入的均摊时间复杂度为严格 \(\mathcal{O}(1)\)；
面试避坑优化：若提前已知元素总数 \(N\)，务必使用 vec.reserve(N) 预分配内存，彻底消除动态扩容带来的重复内存分配与数据搬移！

2. `reserve()` vs `resize()`¶

vec.reserve(n)：只改变容量（capacity），不改变元素个数（size），不创建任何新元素；此时不能通过 vec[i] 访问未经初始化的内存！
vec.resize(n)：改变元素个数（size）。若新尺寸大于当前尺寸，会调用默认构造函数填充新元素；此时可直接使用 vec[i] 下标访问。

std::vector<int> v1;
v1.reserve(10);
// v1[0] = 5; // ❌ 未定义行为 (UB)！此时 size 仍然是 0

std::vector<int> v2;
v2.resize(10, 0);
v2[0] = 5; // ✅ 正确，size 为 10，首元素被安全修改

3. `push_back()` vs `emplace_back()`¶

push_back()：接收已构造好的对象或临时对象，触发拷贝构造或移动构造；
emplace_back()：利用完美转发（Variadic Templates + std::forward）在容器末尾直接就地构造对象，省去临时对象的生成与移动开销；
写法建议：对于简单类型（如 int）两者完全等价；对于结构体、pair、复杂类对象，优先使用 emplace_back：

std::vector<std::pair<int, std::string>> vec;
vec.push_back({1, "apple"});         // 构造临时 pair 再移动
vec.emplace_back(1, "apple");        // 就地在容器内存直接构造

4. 迭代器失效 (Iterator Invalidation)¶

扩容导致全失效：一旦发生扩容，原数组所有指针、引用、迭代器全部指向已释放的野内存，立即失效；
插入/删除导致局部失效：在中间插入或删除元素时，被操作位置及其之后的所有迭代器均失效。
删除循环正确写法：必须使用 erase 的返回值更新迭代器：

for (auto it = vec.begin(); it != vec.end(); /* 自增由分支处理 */) {
    if (*it % 2 == 0) {
        it = vec.erase(it); // erase 返回下一个有效迭代器
    } else {
        ++it;
    }
}

1.2 `std::unordered_map` vs `std::map`¶

维度	`std::unordered_map` / `set`	`std::map` / `set`
底层实现	哈希表（开链桶数组 Bucket Array + 单链表）	红黑树（Red-Black Tree，自平衡二叉搜索树）
平均查找时间	\(\mathcal{O}(1)\)	\(\mathcal{O}(\log n)\)
最坏查找时间	\(\mathcal{O}(n)\)（严重哈希碰撞退化为链表）	严格 \(\mathcal{O}(\log n)\)
元素有序性	无序（遍历顺序随机）	严格有序（按 `Key` 升序排列）
二分能力	不支持 `lower_bound` / `upper_bound`	支持极速 `lower_bound` / `upper_bound`
Key 的要求	必须支持 `std::hash` 与 `operator==`	必须支持严格弱序 `operator<`

面试致命坑：`map[key]` 操作符的副作用¶

mp[key] 具有自动插入副作用：若 key 不存在，operator[] 会使用默认构造函数自动插入一条新记录 {key, T()}，然后再返回其引用！
严重后果：在仅需要查询某个元素是否存在、或者在只读函数（const 上下文）中误用 []，会导致哈希表无端急剧膨胀，不仅浪费内存，还会改变 mp.size()！
正确做法：仅做存在性检查或查询时，使用 mp.count(key) 或 mp.find(key) != mp.end()。

1.3 自定义 Hash 全面指南：在 `std::unordered_set` 与 `unordered_map` 中使用自定义类型¶

很多初学者在刷题或面试时，最常遇到的编译灾难之一就是：

std::unordered_set<std::pair<int, int>> visited; // ❌ 编译报错！报错信息长达几十行！

或者自定义了一个简单的结构体：

struct Point { int x, y; };
std::unordered_set<Point> points; // ❌ 同样直接编译报错！

为什么 `std::set` 可以直接用，而 `std::unordered_set` 不行？¶

std::set 底层是红黑树，只需要判断元素之间的大小关系（即 < 运算符）。C++ 标准库默认已经为 std::pair 实现了字典序的 operator<；
std::unordered_set 底层是哈希表，必须同时满足两个条件：
哈希函数（Hash Function）：能把对象映射成一个 std::size_t 整数，以此决定放入哪个哈希桶（Bucket）；
相等比较（Equality Operator）：当两个对象的哈希值冲突（进入同一个桶）时，必须用 operator== 判断它们是否真正相等。

C++ 标准库仅为基本数据类型（int, long long, double, std::string, 指针等）提供了默认的 std::hash，没有为 std::pair、std::vector 或任何自定义结构体提供默认哈希函数！

核心要素：自定义 Hash 的标准写法¶

要让自定义类型支持 std::unordered_set，必须提供两样东西： 1. operator==（判断是否相等）； 2. Hash 仿函数（计算哈希值）。

写法一：仿函数（Functor）—— 面试中最推荐、最不易出错的标准写法¶

定义一个结构体，并在其中重载调用运算符 operator()：

#include <iostream>
#include <unordered_set>
#include <utility>

// 1. 自定义结构体
struct Point {
    int x, y;

    // 关键点 A：必须提供 operator==，供哈希表在发生碰撞时比对
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 2. 自定义 Hash 仿函数
struct PointHash {
    // 关键点 B：必须是 const 成员函数，接收 const 引用，返回 std::size_t
    std::size_t operator()(const Point& p) const {
        auto h1 = std::hash<int>{}(p.x);
        auto h2 = std::hash<int>{}(p.y);
        // 优质哈希合并公式（避免直接简单的异或）
        return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
    }
};

int main() {
    // 3. 将仿函数作为第二个模板参数传入 unordered_set
    std::unordered_set<Point, PointHash> point_set;

    point_set.insert({1, 2});
    point_set.insert({3, 4});
    point_set.insert({1, 2}); // 重复元素，插入失败

    std::cout << "Size: " << point_set.size() << "\n"; // 输出 2
    std::cout << "Count (1, 2): " << point_set.count({1, 2}) << "\n"; // 输出 1

    return 0;
}

写法二：特化 `std::hash` —— 优雅、与原生类型无缝统一¶

如果不希望每次声明 unordered_set 时都显式传一个 PointHash，可以直接在 namespace std 中特化 std::hash<Point>：

struct Point {
    int x, y;
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 在 std 命名空间中特化 hash<Point>
namespace std {
    template <>
    struct hash<Point> {
        std::size_t operator()(const Point& p) const noexcept {
            auto h1 = std::hash<int>{}(p.x);
            auto h2 = std::hash<int>{}(p.y);
            return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
        }
    };
}

// 使用时完全和内置类型一样简洁！
std::unordered_set<Point> point_set;

写法三：解决 `std::pair<int, int>` 坐标去重（LeetCode 最高频场景）¶

在网格图搜索（BFS / DFS）中，我们极其频繁地需要记录访问过的二维坐标 (x, y)：

#include <unordered_set>
#include <utility>

// 为 std::pair 定义通用哈希仿函数
struct PairHash {
    template <class T1, class T2>
    std::size_t operator()(const std::pair<T1, T2>& p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);
        return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
    }
};

// 声明网格图已访问集合
std::unordered_set<std::pair<int, int>, PairHash> visited;

// 使用示例
visited.insert({0, 0});
visited.insert({1, 2});
if (visited.count({1, 2})) {
    // 已访问过
}

核心避坑：如何正确合并多个字段的 Hash 值？¶

很多初学者容易写出如下“危险代码”：

// ❌ 错误示范：极其糟糕的哈希合并方式！
std::size_t operator()(const Point& p) const {
    return std::hash<int>{}(p.x) ^ std::hash<int>{}(p.y);
}

为什么不能直接使用简单的 `h1 ^ h2`？¶

对称性致命碰撞：对于任意坐标，点 \((1, 2)\) 与点 \((2, 1)\) 的哈希值完全相同！
对角线彻底归零：若 \(x = y\)（如 \((0, 0), (1, 1), (2, 2), \dots\)），h1 ^ h2 的结果恒等于 0！所有对角线上的点全被塞进 0 号桶，哈希表瞬间退化为一条长链表，查找时间从 \(\mathcal{O}(1)\) 暴跌为 \(\mathcal{O}(n)\)！

推荐的两种哈希合并方案：¶

方案 A（极简好记，适合面试手写）：使用大质数相乘并错位，打破对称性：

return h1 * 31 + h2; // 类似 Java String.hashCode()
// 或者三维：
return (h1 * 31 + h2) * 31 + h3;

方案 B（工业级金标准：Boost hash_combine）：

// 经典的 Boost hash_combine 公式
template <class T>
inline void hash_combine(std::size_t& seed, const T& v) {
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

为什么是 0x9e3779b9？
\(0x9e3779b9\) 是黄金分割常数 \(2^{32} \times (\frac{\sqrt{5}-1}{2})\) 的十六进制表示。它在二进制下具有极高的随机性（无任何周期性规律），结合左移 6 位与右移 2 位，能将原始哈希值的高位和低位充分打乱混合（Avalanche Effect，雪崩效应），彻底避免由于字段取值相似而导致的哈希碰撞。

1.4 `std::priority_queue` 比较器全景¶

std::priority_queue 底层使用 std::vector 并通过算法库的 make_heap / push_heap / pop_heap 维护二叉堆。

为什么传 std::greater<T> 是小顶堆？

堆顶位于数组的末尾。标准库默认采用 std::less<T>，当比较器认为 \(a < b\) 时，较大的元素会被排到堆顶，构成大顶堆。若传入 std::greater<T>，则较小的元素被视作“优先级更高”，从而沉底到堆顶形成小顶堆。

三种常用自定义比较器写法¶

写法 1：结构体内部重载 `operator<`（最简洁）¶

struct Node {
    int id, dist;
    // 想要让 dist 小的在堆顶（小顶堆），需要反向定义：当前 dist 大于对方 dist 时返回 true
    bool operator<(const Node &other) const {
        return dist > other.dist;
    }
};
std::priority_queue<Node> pq;

写法 2：自定义仿函数（Functor，适合原结构体无法修改时）¶

struct Cmp {
    bool operator()(const std::pair<int, int> &a, const std::pair<int, int> &b) const {
        return a.second > b.second; // 按第二关键字升序（小顶堆）
    }
};
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, Cmp> pq;

写法 3：Lambda 表达式 + `decltype`（函数体内即插即用）¶

auto cmp = [](const auto &a, const auto &b) {
    return a.val > b.val; // 小顶堆
};
std::priority_queue<Node, std::vector<Node>, decltype(cmp)> pq(cmp);

1.5 `std::string` 短字符串优化与 `std::string_view`¶

1. 短字符串优化 (SSO, Small String Optimization)¶

现代 C++ 编译器（GCC, Clang, MSVC）均对 std::string 实现了 SSO：

长度较短的字符串（通常在 15 字节以内，不同平台略有差异）会直接存储在 std::string 对象内部的栈缓冲区中，完全不触发堆内存分配（Heap Allocation）；
只有当字符串长度超过内部缓冲区阈值时，才会调用 malloc 在堆上开辟内存。

2. `std::string_view` (C++17 零拷贝子串切片)¶

在字符串处理、回文串检测、高频子串提取的题目中，直接调用 s.substr(i, len) 会发生深拷贝并分配堆内存。

std::string_view 是只读的非拥有型字符串视图，内部仅仅由一个指向原始字符数组的指针和一个长度 size 组成（大小仅占 16 字节）；
切片操作 sv.substr(i, len) 是真正的 \(\mathcal{O}(1)\) 零内存分配！

bool isPalindrome(std::string_view sv) {
    int l = 0, r = sv.size() - 1;
    while (l < r) {
        if (sv[l++] != sv[r--]) return false;
    }
    return true;
}

// 调用时直接传入原 string，全程无任何临时 string 堆拷贝发生
std::string s = "racecar";
bool ok = isPalindrome(s);

2. 高频算法库与实用技巧 (`<algorithm>`, `<numeric>`)¶

2.1 `std::sort` 与严格弱序 (Strict Weak Ordering)¶

面试中因为自定义排序比较器写错导致“本地跑没问题，提交直接段错误 (Segfault) 或超时”是高频血泪教训！

严格弱序铁律¶

传递给 std::sort 的比较器函数 cmp(a, b) 必须定义严格小于（Strictly Less Than）关系：

非自反性：\(cmp(a, a)\) 必须严格返回 false！
非对称性：若 \(cmp(a, b) == \text{true}\)，则必有 \(cmp(b, a) == \text{false}\)；
传递性：若 \(cmp(a, b)\) 且 \(cmp(b, c)\)，则必有 \(cmp(a, c)\)。

!!! danger "致命错误示例：比较器写了 <="

// ❌ 绝对禁止：违反严格弱序！
std::sort(vec.begin(), vec.end(), [](int a, int b) {
    return a <= b; // 当 a == b 时返回了 true！
});

为什么会导致段错误？ std::sort 内部采用快速排序与堆排序。在快排划分区间时，指针向左/向右扫描寻找分割点，依赖 cmp(pivot, *ptr) 为 false 停下来作为哨兵。若比较器返回 <=，导致相等元素无法充当停止哨兵，指针直接冲出数组边界，引发内存越界段错误！

2.2 二分查找全家桶速查¶

前提条件：数组必须已经升序有序！

std::lower_bound(first, last, val)：返回指向首个 \(\ge val\) 元素的迭代器；
std::upper_bound(first, last, val)：返回指向首个 \(> val\) 元素的迭代器；
std::equal_range(first, last, val)：返回 pair<lower_bound, upper_bound>。

std::vector<int> nums = {1, 2, 4, 4, 4, 6, 7};

// 1. 寻找 4 的第一个出现位置下标
auto it1 = std::lower_bound(nums.begin(), nums.end(), 4);
int first_idx = it1 - nums.begin(); // 2

// 2. 寻找 4 的最后一个出现位置下标
auto it2 = std::upper_bound(nums.begin(), nums.end(), 4);
int last_idx = (it2 - nums.begin()) - 1; // 4

// 3. 统计 4 在有序数组中的出现频次
int count_4 = it2 - it1; // 3

2.3 原地去重经典连招 (`sort` + `unique` + `erase`)¶

std::unique 的机制是将相邻的重复元素移到序列末尾，并返回指向去重后逻辑末尾的迭代器。因此必须先排序！

std::vector<int> nums = {3, 1, 2, 3, 2, 4, 1};

// 1. 先排序保证重复元素相邻
std::sort(nums.begin(), nums.end());

// 2. 移除相邻重复并物理截断
nums.erase(std::unique(nums.begin(), nums.end()), nums.end());
// 此时 nums 保证严格升序且无重复元素: {1, 2, 3, 4}

2.4 线性快速选择 (`std::nth_element`)¶

当面试官要求“找到数组中第 \(k\) 小的元素”且不强制全数组完全有序时，std::sort（\(\mathcal{O}(n \log n)\)）不是最优解：

std::nth_element(first, nth, last) 基于快速选择（Quickselect）算法，在期望 \(\mathcal{O}(n)\) 线性时间内完成；
执行后，nth 位置上的元素恰好是全排序后该位置应有的值，且左侧所有元素均 \(\le\) 它，右侧所有元素均 \(\ge\) 它。

std::vector<int> nums = {9, 2, 7, 4, 5, 6, 3, 8, 1};
// 将第 4 小的元素（0-indexed 下标 3）放置到对应位置
std::nth_element(nums.begin(), nums.begin() + 3, nums.end());
int k_th_smallest = nums[3]; // 期望 O(n)

3. 现代 C++ 语法糖与高阶编码风格 (C++11 ~ C++20)¶

3.1 结构化绑定 (Structured Binding, C++17)¶

极大幅度提高图论、哈希表代码的可读性，避免冗长的 .first 与 .second：

// 1. 极速遍历 map 键值对
std::unordered_map<std::string, int> freq;
for (const auto &[word, count] : freq) {
    // 直接使用 word 与 count，语义清晰
}

// 2. 图论带权边解构
struct Edge { int u, v, w; };
std::vector<Edge> edges;
for (const auto &[u, v, w] : edges) {
    adj[u].push_back({v, w});
}

3.2 现代 C++ Lambda 表达式完全指南（底层机理、捕获陷阱与实战技巧）¶

Lambda 表达式（匿名函数闭包）自 C++11 引入以来，已成为现代 C++ 最具革命性的语言特性之一。在算法面试与工程代码中，熟练运用 Lambda 不仅能让代码更精炼紧凑，更能避免类的成员函数参数冗余与全局变量污染。

1. Lambda 完整语法结构拆解¶

[capture](parameters) mutable noexcept -> return_type { body }

[capture] 捕获子句：指定外部局部变量如何传递进 Lambda 作用域（按值、按引用、混合）；
(parameters) 参数列表：与普通函数形参一致；C++14 起支持泛型参数（如 auto a, auto b）；无参时括号可省略；
mutable 修饰符：默认情况下，按值捕获的变量在 Lambda 内部是 const 只读的。加上 mutable 后，允许在 Lambda 内部修改被按值捕获变量的局部副本；
noexcept：声明该 Lambda 不会抛出异常，有助于编译器进行内联与优化；
-> return_type 返回值类型推导：单 return 语句或分支类型一致时通常可省略由编译器自动推导；在多分支返回不同类型、或编写递归 Lambda 时建议显式指定；
{ body } 函数体：具体执行逻辑。

2. 捕获列表（Capture List）全景与内存陷阱¶

捕获方式	语法示例	行为特征与底层原理	算法面试使用建议
无捕获	`[]`	不使用任何外部局部变量。可以隐式转换为普通函数指针（如 `int(*)(int, int)`）。	简单无状态比较器、C 语言回调兼容
全引用捕获	`[&]`	以引用（指针）方式捕获当前作用域内所有被使用的局部变量。零拷贝开销。	算法刷题首选（直接读写外部结果数组、图邻接表、计数器）
全值捕获	`[=]`	以拷贝方式捕获所有被使用的局部变量。生成当前状态的一份快照。	只读数据安全快照、多线程避免竞态
精确指定	`[&ans, x]`	变量 `ans` 按引用捕获，变量 `x` 按值拷贝。	精确控制读写权限与开销
捕获类成员	`[this]` / `[*this]`	`[this]` 捕获当前对象的指针；`[*this]`（C++17）将整个对象完整拷贝一份进闭包。	成员函数异步回调、防对象析构悬垂
初始化捕获 (C++14)	`[p = std::move(ptr)]`	广义捕获（Generalized Lambda Capture），支持将不可拷贝的只移类型（如 `unique_ptr`）移动进闭包。	现代工程资源所有权转移

致命陷阱：悬垂引用（Dangling Reference）¶

若 Lambda 内部使用 [&] 按引用捕获了某个局部变量，而这个 Lambda 作为一个回调函数被返回（例如 return [&]() { ... };）或者传递给了异步线程；
当局部变量所在的作用域结束被销毁时，Lambda 内部持有的引用将变成悬垂指针，导致严重的未定义行为（UB）与内存崩溃！
防御准则：仅在 Lambda 的生命周期严格小于或等于被捕获变量的生命周期时（如局部排序、局部 DFS 递归），才使用 [&]。

3. 深入理解 `mutable` 关键字¶

为什么下面的代码在没有 mutable 时会直接编译报错？

int count = 0;
// auto func = [count]() { count++; }; // ❌ 编译报错: 无法修改只读变量
auto func = [count]() mutable { count++; }; // ✅ 正确
func();
std::cout << count << "\n"; // 输出 0 (外部变量未变，修改的是闭包内部副本)

底层机理：
编译器为每个 Lambda 生成仿函数类时，其 operator() 默认被声明为 const 成员函数（即 void operator()() const）。因此，所有按值拷贝进类的成员变量都受到 const 保护。加上 mutable 后，编译器生成的 operator() 不带 const，从而允许修改成员变量。

4. 算法面试五大高频实战场景¶

场景 1：自定义复杂比较器 (`std::sort`)¶

算法题目中经常需要多关键字排序或根据哈希表频次动态排序：

// 按照第一关键字升序，若相同则按第二关键字降序
std::vector<std::pair<int, int>> points = {{1, 2}, {1, 5}, {2, 3}};
std::sort(points.begin(), points.end(), [](const auto &a, const auto &b) {
    if (a.first != b.first) return a.first < b.first;
    return a.second > b.second; // 必须遵守严格弱序，严禁写 <=
});

场景 2：STL 算法库高级谓词结合¶

利用 std::all_of、std::any_of、std::count_if、std::remove_if 编写声明式极简代码：

std::vector<int> nums = {2, 4, 6, 8, 10};
// 1. 判断是否所有数都是偶数
bool all_even = std::all_of(nums.begin(), nums.end(), [](int x) { return x % 2 == 0; });

// 2. 统计大于 5 的元素个数
int cnt = std::count_if(nums.begin(), nums.end(), [](int x) { return x > 5; });

// 3. 原地移除所有奇数 (结合 erase-remove 惯用法)
nums.erase(std::remove_if(nums.begin(), nums.end(), [](int x) { return x % 2 != 0; }), nums.end());

场景 3：递归 Lambda 实现 DFS / 树遍历（告别类成员变量）¶

在 LeetCode 的 class Solution 中写 DFS，传统做法要么定义成员函数传一长串参数，要么定义全局静态变量（多组样例需手动 clear）。

现代 C++ 最佳实践：使用 C++14 泛型通用 Lambda 自传递（Y-Combinator 思想）：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        int max_ans = 0;

        // 递归 Lambda: 捕获外部变量引用 [&]，首个参数自传递 auto&& self
        auto dfs = [&](auto &&self, TreeNode* node, int depth) -> void {
            if (!node) return;
            max_ans = std::max(max_ans, depth);
            self(self, node->left, depth + 1);   // 递归调用自传递
            self(self, node->right, depth + 1);
        };

        dfs(dfs, root, 1);
        return max_ans;
    }
};

对比 std::function 递归：
有些同学习惯写 std::function<void(TreeNode*, int)> dfs = ...。但 std::function 内部涉及堆内存分配、虚函数间接寻址与类型擦除，运行耗时是上述泛型 Lambda 的数倍以上！在时间限制严格的竞赛与面试中，强烈推荐 auto &&self 写法。

场景 4：堆优先队列自定义比较器 (`std::priority_queue`)¶

利用 decltype 将 Lambda 传入优先队列：

struct Node { int id, cost; };
// 定义按 cost 升序排列的小顶堆比较器
auto cmp = [](const Node &a, const Node &b) {
    return a.cost > b.cost; // 小顶堆返回 a > b
};

// 必须将 cmp 实例作为构造函数参数传入 pq
std::priority_queue<Node, std::vector<Node>, decltype(cmp)> pq(cmp);

场景 5：即时执行表达式（IIFE - Immediately Invoked Function Expression）¶

在初始化 const 变量时，若需要多步复杂逻辑（如多重分支或循环），传统做法往往被迫放弃 const。利用 IIFE 可以优雅保证不可变性：

// 优雅地用 IIFE 初始化 const 变量
const auto lookup_table = []() {
    std::vector<int> table(256, -1);
    for (int i = 'a'; i <= 'z'; ++i) table[i] = i - 'a';
    return table;
}(); // 末尾带有 ()，定义即执行

5. 编译器的底层实现：Lambda 的本质是什么？¶

当你写下一个 Lambda 时，C++ 编译器到底做了什么？

int x = 10;
auto lambda = [x](int y) { return x + y; };

编译器在底层会将其自动展开为一个匿名的仿函数类（Functor Class）：

// 编译器自动生成的等价仿函数结构体
class __Lambda_Unique_Name__ {
private:
    int x; // 按值捕获的变量成为类的成员变量
public:
    __Lambda_Unique_Name__(int x_) : x(x_) {}

    // 默认是 const 成员函数！
    int operator()(int y) const {
        return x + y;
    }
};

// 使用时相当于实例化一个对象
__Lambda_Unique_Name__ lambda(x);

性能结论：Lambda 没有任何隐藏的运行时虚表（vtable）开销；相反，编译器极易将其完全内联展开（Inline Expansion），执行效率与手写普通算术指令毫无二致！

3.3 移动语义 (`std::move`) 规避回溯答案深拷贝¶

在回溯算法（如全排列、子集求和）收集最终结果时：

std::vector<std::vector<int>> results;
std::vector<int> path;

void backtrack(...) {
    if (goal) {
        // ❌ 传统写法: 触发整条 path 的深度内存拷贝
        // results.push_back(path);

        // ✅ 优秀写法（若后续无需再复用此 path）或只在转移所有权时使用:
        // 在必须复制的地方依然复制，但在将临时结果放入答案时，利用 std::move
    }
}

4. 内存管理、传参与未定义行为 (UB) 防御¶

4.1 DFS 回溯传参陷阱：值传递 vs 引用传递¶

// ❌ 灾难级写法：每层递归都发生整个 path 向量的完整深拷贝！
// 递归深度为 N 时，时间/空间复杂度直接退化至 O(N^2)，极易 MLE / TLE
void dfs_bad(TreeNode* root, std::vector<int> path) {
    if (!root) return;
    path.push_back(root->val);
    dfs_bad(root->left, path);
    dfs_bad(root->right, path);
}

// ✅ 正确规范写法：常量引用或普通引用 + 回溯现场恢复
void dfs_good(TreeNode* root, std::vector<int> &path) {
    if (!root) return;
    path.push_back(root->val);      // 做出选择
    dfs_good(root->left, path);
    dfs_good(root->right, path);
    path.pop_back();               // 撤销选择，恢复现场
}

4.2 无符号数下溢死循环 (Unsigned Underflow)¶

STL 容器的 .size() 返回值类型为无符号整数 size_t（在 64 位平台为 unsigned long long）：

std::vector<int> vec;

// ❌ 致命 Bug：当 vec 为空（size 为 0）时！
// 0u - 1 不会变成 -1，而是发生无符号下溢，变成 18446744073709551615 (2^64 - 1)！
// 循环将执行数十亿次导致程序彻底超时或访问非法内存卡死！
for (int i = 0; i <= vec.size() - 1; ++i) { ... }

// ✅ 正确规范写法 1：安全强转
for (int i = 0; i <= (int)vec.size() - 1; ++i) { ... }

// ✅ 正确规范写法 2：标准严格小于
for (int i = 0; i < (int)vec.size(); ++i) { ... }

4.3 整型溢出与防溢出二分¶

二分查找中点计算：
避免使用 mid = (l + r) / 2（当 \(l + r > 2^{31} - 1\) 时整型溢出为负数导致无限循环）；
务必使用：mid = l + (r - l) / 2。
大数相乘溢出：
两个 int 相乘（如 \(10^5 \times 10^5 = 10^{10}\)），即使左侧接收变量定义为 long long，右侧乘法依然在 int 内部计算完成并溢出截断！
必须在乘法发生前强制类型提升：long long prod = 1LL * a * b;。

4.4 负数取模修正 (Modulo on Negative Numbers)¶

在 C++ 中，% 实际上是取余（Remainder）而非数学上的取模（Modulo）：

在 C++ 中：-7 % 3 的结果是 -1（符号与被除数一致）；
在同余理论与算法竞赛中，模数必须为非负数 \([0, m - 1]\)。
正规化取模通用公式：

\[ \operatorname{mod}(x, m) = (x \bmod m + m) \bmod m \]

int mod(int x, int m) {
    return (x % m + m) % m;
}

4.5 链表虚拟头节点 (Dummy / Sentinel Node)¶

在单链表面试试题中，头节点的删除、插入经常需要特殊处理 if (head == nullptr) 或 if (prev == nullptr) 等繁琐分支。

哨兵虚拟头节点技巧：

ListNode dummy(0); // 栈上直接构造，无需 new，避免内存泄漏
dummy.next = head;
ListNode* prev = &dummy;

// 后续统一处理逻辑，彻底消除针对 head 的所有特判
...

return dummy.next;

算法面试 C++ 核心常识与避坑指南¶

1. 核心 STL 容器原理与高频考点¶

1.1 std::vector 底层扩容与迭代器失效¶

1. 扩容机制与均摊复杂度¶

2. reserve() vs resize()¶

3. push_back() vs emplace_back()¶