自动关联目录：LeetCode C++ 标准库速查

这不是 C++ 标准库百科，而是一份刷 LeetCode 时够用、能直接查代码的标准库清单。范围包括容器、算法、数值工具、字符串处理、函数对象和常用辅助类型。目标只有三个：

1. 看到题目特征，立刻知道该选什么容器和算法
2. 记住核心 API、复杂度和返回值，不在语法上浪费时间
3. 避开会导致错误答案或超时的高频坑

算法思路见 Data Structures & Algorithm，线性结构原理见 Linear，哈希原理见 Hash。本文只解决“算法想到了，C++ 怎么快速、正确地写出来”。工程中的内存布局、迭代器失效和分配器见 STL 容器与分配器。

容器：30 秒选型

最常用的优先级：

第一梯队：vector、string、unordered_map、queue、stack、priority_queue
第二梯队：deque、set、map、unordered_set、array
知道即可：multiset、list、forward_list、multimap

核心原则：

默认 vector
精确查找、计数        -> unordered_map / unordered_set
需要顺序、范围、前驱后继 -> map / set
只反复取一个最值       -> priority_queue

标准算法：30 秒选型

统一初始化

LeetCode 通常支持下面的竞赛式头文件；正式项目应按需包含标准头文件。

#include <bits/stdc++.h>
using namespace std;

本文默认使用 C++17。常见功能对应的标准头文件：

#include <algorithm>       // sort、lower_bound、find、unique
#include <array>
#include <bitset>
#include <cctype>          // isdigit、tolower
#include <climits>         // INT_MAX、LLONG_MAX
#include <cmath>           // sqrt、abs、ceil、floor
#include <deque>
#include <functional>      // greater、function
#include <iostream>
#include <iterator>        // next、prev、back_inserter
#include <list>
#include <limits>          // numeric_limits
#include <map>
#include <numeric>         // accumulate、iota、gcd、lcm
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>         // pair
#include <vector>

常见初始化方式：

vector<int> a;                  // 空数组
vector<int> b(n);               // n 个 0
vector<int> c(n, -1);           // n 个 -1
vector<vector<int>> grid(m, vector<int>(n, 0));

unordered_map<int, int> freq;
set<int> ordered;
queue<int> q;
stack<int> st;

复杂度总表

注意：unordered_* 的最坏复杂度是$O(n)$；表里的$O(1)$ 是平均复杂度。

vector：默认容器

vector 是动态数组，连续存储、随机访问快。刷题中没有明确理由时就用它。

必会 API

vector<int> v = {3, 1, 2};

v.push_back(4);                 // 尾插
v.emplace_back(5);              // 原地构造；int 场景与 push_back 差别不大
v.pop_back();                   // 删除尾部，不返回元素

int first = v.front();
int last  = v.back();
int x     = v[1];               // 不检查越界
int y     = v.at(1);            // 检查越界，越界时抛异常

int n = static_cast<int>(v.size());
bool isEmpty = v.empty();
v.clear();                      // size 变为 0，capacity 通常保留

reserve 和 resize 不一样

vector<int> v;
v.reserve(1000);                // 只预留容量，v.size() 仍然是 0
v.push_back(7);                 // 正确

v.resize(1000);                 // 真正创建 1000 个元素，默认值为 0
v[999] = 7;                     // 正确

遍历与修改

for (int x : v) {               // 拷贝，只读值时使用
    cout << x << ' ';
}

for (int& x : v) {              // 引用，可以修改原数组
    x *= 2;
}

for (const int& x : v) {        // 不拷贝且不修改，适合大对象
    cout << x << ' ';
}

排序、去重、删除

sort(v.begin(), v.end());
sort(v.rbegin(), v.rend());     // 降序

// 排序后去重
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

// 删除所有值等于 target 的元素（C++17）
v.erase(remove(v.begin(), v.end(), target), v.end());

// 删除下标 i 的元素：O(n)
v.erase(v.begin() + i);

unique 只把相邻的重复元素移到末尾，不会真的缩短容器，所以通常要先排序，再接 erase。

二维 vector

int m = 3, n = 4;
vector<vector<int>> grid(m, vector<int>(n, 0));

int rows = static_cast<int>(grid.size());
int cols = grid.empty() ? 0 : static_cast<int>(grid[0].size());

图的邻接表也是二维 vector：

vector<vector<int>> graph(n);
for (auto [u, v] : edges) {
    graph[u].push_back(v);
    graph[v].push_back(u);
}

迭代器失效

vector 扩容后，旧的迭代器、指针和引用全部可能失效。

vector<int> v = {1, 2, 3};
int* p = &v[0];
v.push_back(4);                 // 可能扩容
// cout << *p;                  // 危险：p 可能已经悬空

刷题中的实用规则：遍历 vector 时不要同时 push_back；确实需要时先 reserve，或改用下标。

string：字符序列

string 可以看作专门处理字符的动态数组。

string s = "leetcode";
s.push_back('!');
s.pop_back();

char c = s[0];
string part = s.substr(1, 3);   // 从下标 1 开始取 3 个字符，产生新字符串
size_t pos = s.find("code");
if (pos != string::npos) {
    // 找到了
}

reverse(s.begin(), s.end());
sort(s.begin(), s.end());

数字转换：

int x = stoi("123");
long long y = stoll("1234567890123");
string s = to_string(42);

常见代价：substr 会复制字符，长度为$k$ 时复杂度是$O(k)$。在双重循环里频繁切子串，可能把算法拖慢到$O(n^3)$。

stack：后进先出

stack 是容器适配器，只暴露栈需要的操作，不能遍历和随机访问。

stack<int> st;
st.push(1);
st.push(2);

int x = st.top();               // 2
st.pop();                       // pop 不返回值

bool isEmpty = st.empty();
int n = static_cast<int>(st.size());

典型信号：

• 最近的未匹配元素：括号匹配
• 左右第一个更大/更小元素：单调栈
• 把递归改成迭代：DFS
• 表达式求值

做单调栈时通常存下标，不存值，因为下标既能取值，也能计算距离。

queue：先进先出

queue<int> q;
q.push(1);
q.push(2);

int first = q.front();          // 1
int last  = q.back();           // 2
q.pop();                        // pop 不返回值

BFS 模板：

queue<int> q;
vector<int> dist(n, -1);

q.push(start);
dist[start] = 0;

while (!q.empty()) {
    int u = q.front();
    q.pop();

    for (int v : graph[u]) {
        if (dist[v] != -1) continue;
        dist[v] = dist[u] + 1;
        q.push(v);
    }
}

层序遍历时先保存本层长度：

while (!q.empty()) {
    int levelSize = static_cast<int>(q.size());
    while (levelSize--) {
        auto node = q.front();
        q.pop();
        // 处理 node，并把下一层加入 q
    }
}

deque：双端队列

deque 支持两端$O(1)$ 增删，也支持$O(1)$ 下标访问，但内存不是完全连续的。

deque<int> dq;
dq.push_front(1);
dq.push_back(2);

int a = dq.front();
int b = dq.back();
int c = dq[1];

dq.pop_front();
dq.pop_back();

最重要的用途是单调队列。滑动窗口最大值模板：

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;              // 存下标；对应值从队首到队尾递减
    vector<int> ans;

    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();     // 移除窗口外元素
        }
        while (!dq.empty() && nums[dq.back()] <= nums[i]) {
            dq.pop_back();      // 移除不可能成为答案的元素
        }
        dq.push_back(i);

        if (i >= k - 1) {
            ans.push_back(nums[dq.front()]);
        }
    }
    return ans;
}

priority_queue：堆

priority_queue 默认是大顶堆，堆顶是最大值。

priority_queue<int> maxHeap;
maxHeap.push(3);
maxHeap.push(1);
maxHeap.push(2);

int x = maxHeap.top();          // 3
maxHeap.pop();

小顶堆要显式写 greater：

priority_queue<int, vector<int>, greater<int>> minHeap;

pair 会先比较 first，再比较 second，因此 Dijkstra 常写成：

using State = pair<int, int>;   // {distance, node}
priority_queue<State, vector<State>, greater<State>> pq;

pq.push({0, start});
while (!pq.empty()) {
    auto [d, u] = pq.top();
    pq.pop();

    if (d != dist[u]) continue; // 丢弃过期状态：懒删除
    // 松弛与 u 相邻的边
}

自定义类型的小顶堆：

struct Node {
    int value;
    int id;
};

struct Compare {
    bool operator()(const Node& a, const Node& b) const {
        if (a.value != b.value) return a.value > b.value;
        return a.id > b.id;
    }
};

priority_queue<Node, vector<Node>, Compare> pq;

比较器很容易写反。可以记成：priority_queue 默认用 less 得到大顶堆；想让较小值优先，就在比较器里写 a.value > b.value。

堆还是 set

set 和 multiset：有序集合

set 自动去重并按升序维护；常见实现是红黑树。

set<int> s;
s.insert(3);
s.insert(1);
s.insert(3);                    // 重复值不会插入

bool exists = s.find(3) != s.end();
int count = static_cast<int>(s.count(3));  // set 中只能是 0 或 1
s.erase(3);

int smallest = *s.begin();
int largest  = *s.rbegin();

边插入边判断是否成功：

auto [it, inserted] = s.insert(x);
if (!inserted) {
    // x 原本就在集合里
}

multiset 允许重复元素：

multiset<int> ms = {1, 2, 2, 3};

ms.erase(2);                    // 删除所有值为 2 的元素

auto it = ms.find(2);
if (it != ms.end()) {
    ms.erase(it);               // 只删除一个 2
}

这是高频陷阱：multiset.erase(value) 删除全部匹配值，erase(iterator) 只删除迭代器指向的一个值。

lower_bound、upper_bound 和前驱后继

set<int> s = {1, 3, 3, 7};      // set 实际为 {1, 3, 7}

auto a = s.lower_bound(3);      // 第一个 >= 3 的元素
auto b = s.upper_bound(3);      // 第一个 > 3 的元素

查找不大于 x 的最大值，也就是前驱：

auto it = s.upper_bound(x);     // 第一个 > x
if (it != s.begin()) {
    --it;                       // 现在 *it <= x
} else {
    // 不存在 <= x 的元素
}

查找不小于 x 的最小值，也就是后继：

auto it = s.lower_bound(x);
if (it != s.end()) {
    // *it >= x
}

map：有序键值表

map<K, V> 按 key 升序维护，每个 key 唯一。

map<string, int> score;
score["alice"] = 90;
score["bob"]++;

bool exists = score.find("alice") != score.end();

for (const auto& [name, value] : score) {
    cout << name << ' ' << value << '\n';
}

map 的 lower_bound 和 upper_bound 比较的是 key：

map<int, string> m = {{1, "a"}, {4, "b"}, {8, "c"}};
auto it = m.lower_bound(3);      // 指向 key=4

注意 operator[] 会插入：

map<int, int> m;
if (m[42] == 0) {               // 访问后，key=42 已经被插入
}

// 只判断是否存在，不产生插入
if (m.find(42) != m.end()) {
}

multimap 允许重复 key，但刷题中通常用 map<Key, vector<Value>> 更直观，也更容易访问同一 key 的所有值。

unordered_map 和 unordered_set：哈希表

只关心“是否存在”“出现次数”“key 对应什么值”时，优先考虑哈希表。

频次统计

unordered_map<int, int> freq;
for (int x : nums) {
    ++freq[x];
}

for (const auto& [value, count] : freq) {
    cout << value << ": " << count << '\n';
}

判重

unordered_set<int> seen;
for (int x : nums) {
    if (seen.find(x) != seen.end()) {
        // x 重复出现
    }
    seen.insert(x);
}

Two Sum 模板

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> index;

    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        int need = target - nums[i];
        auto it = index.find(need);
        if (it != index.end()) {
            return {it->second, i};
        }
        index[nums[i]] = i;
    }
    return {};
}

已知元素数量时提前预留空间：

unordered_map<int, int> freq;
freq.reserve(nums.size() * 2);

这能减少扩容和重新哈希，但不是正确性要求。

不能直接哈希 pair

在常见的 C++17 环境里，unordered_map<pair<int, int>, int> 没有标准哈希，需要自定义：

struct PairHash {
    size_t operator()(const pair<int, int>& p) const noexcept {
        size_t h1 = hash<int>{}(p.first);
        size_t h2 = hash<int>{}(p.second);
        return h1 ^ (h2 + 0x9e3779b9U + (h1 << 6) + (h1 >> 2));
    }
};

unordered_map<pair<int, int>, int, PairHash> dist;

如果坐标范围已知，常常可以把二维坐标编码成一个整数，代码更简单：

long long key = 1LL * row * cols + col;
unordered_set<long long> visited;

map 还是 unordered_map

algorithm：查找、判断与变换

标准算法通常接受左闭右开区间 [first, last)。对整个 vector 操作时，基本形式就是 v.begin(), v.end()。

查找与计数

auto it = find(v.begin(), v.end(), target);
if (it != v.end()) {
    int index = static_cast<int>(it - v.begin());
}

int countTarget = static_cast<int>(count(v.begin(), v.end(), target));

auto firstEven = find_if(v.begin(), v.end(), [](int x) {
    return x % 2 == 0;
});

find、count、find_if 都是线性扫描，复杂度$O(n)$。如果要反复查询，应该排序后二分，或改用哈希表。

区间条件判断

bool hasNegative = any_of(v.begin(), v.end(), [](int x) {
    return x < 0;
});

bool allPositive = all_of(v.begin(), v.end(), [](int x) {
    return x > 0;
});

bool noZero = none_of(v.begin(), v.end(), [](int x) {
    return x == 0;
});

最值与位置

int a = min(x, y);
int b = max({x, y, z});
auto [small, large] = minmax(x, y);

auto minIt = min_element(v.begin(), v.end());
auto maxIt = max_element(v.begin(), v.end());

if (minIt != v.end()) {                         // 空容器时返回 end()
    int minValue = *minIt;
    int minIndex = static_cast<int>(minIt - v.begin());
}

int bounded = clamp(value, low, high);           // C++17

原地修改

fill(v.begin(), v.end(), -1);
reverse(v.begin(), v.end());
rotate(v.begin(), v.begin() + k, v.end());       // 左旋 k 位
swap(a, b);

按条件修改或筛选：

transform(v.begin(), v.end(), v.begin(), [](int x) {
    return x * x;
});

vector<int> positives;
copy_if(v.begin(), v.end(), back_inserter(positives), [](int x) {
    return x > 0;
});

v.erase(remove_if(v.begin(), v.end(), [](int x) {
    return x < 0;
}), v.end());

remove / remove_if 只是把保留元素移到前面，并返回新的逻辑结尾；要真正缩短 vector，必须再调用 erase。

排序、选择与排列

sort 和自定义比较器

sort(v.begin(), v.end());                        // 升序
sort(v.begin(), v.end(), greater<int>());        // 降序

sort(intervals.begin(), intervals.end(),
     [](const vector<int>& a, const vector<int>& b) {
         if (a[0] != b[0]) return a[0] < b[0];   // 左端点升序
         return a[1] > b[1];                     // 相同时右端点降序
     });

比较器回答的是“a 是否应该排在 b 前面”。它必须是严格比较：相等元素要返回 false，所以不能写 a <= b。也不要用 return a - b < 0，减法可能溢出。

stable_sort 会保持等价元素的原始相对顺序：

stable_sort(records.begin(), records.end(), [](const auto& a, const auto& b) {
    return a.score < b.score;
});

第 k 小与部分排序

只求第 k 小（k 从 0 开始）时，不必完整排序：

int k = 3;
nth_element(v.begin(), v.begin() + k, v.end());
int kthSmallest = v[k];

nth_element 平均$O(n)$。执行后 v[k] 与完整排序后该位置的值相同，但左右两部分内部不保证有序。

只需要最小的前 k 个且要求这 k 个有序：

partial_sort(v.begin(), v.begin() + k, v.end());
// v[0..k) 是最小的 k 个，并且已经升序

复杂度约为$O(n \log k)$。当 k 很小时，它比完整排序更合适。

枚举排列

sort(v.begin(), v.end());
do {
    // 使用当前排列 v
} while (next_permutation(v.begin(), v.end()));

要从升序开始，才能按字典序枚举全部排列。prev_permutation 则向前一个字典序排列移动。

有序集合运算

输入必须已排序，输出空间用 back_inserter 自动增长：

vector<int> a = {1, 2, 4};
vector<int> b = {2, 3, 4};
vector<int> out;

set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(out));
// out = {2, 4}

out.clear();
set_union(a.begin(), a.end(), b.begin(), b.end(), back_inserter(out));
// out = {1, 2, 3, 4}

out.clear();
set_difference(a.begin(), a.end(), b.begin(), b.end(), back_inserter(out));
// out = {1}

二分查找 API

对已经升序排列的 vector：

vector<int> a = {1, 2, 2, 2, 5, 8};

auto first = lower_bound(a.begin(), a.end(), 2); // 第一个 >= 2
auto last  = upper_bound(a.begin(), a.end(), 2); // 第一个 > 2

bool exists = binary_search(a.begin(), a.end(), 5);
int count = static_cast<int>(last - first);       // 2 出现 3 次
int index = static_cast<int>(first - a.begin());

记忆：

lower_bound(x) -> 第一个 >= x
upper_bound(x) -> 第一个 >  x

对 set / map 必须优先使用成员函数 s.lower_bound(x)，不要写 std::lower_bound(s.begin(), s.end(), x)。两者比较次数都可能是$O(\log n)$，但通用算法在树迭代器上移动要$O(n)$。

numeric：求和、编号与数论

accumulate

long long sum = accumulate(v.begin(), v.end(), 0LL);

long long product = accumulate(v.begin(), v.end(), 1LL,
                               multiplies<long long>());

accumulate 的返回类型由初始值决定。即使 v 是 vector<long long>，写成 accumulate(..., 0) 仍会用 int 累加并可能溢出；求和时优先写 0LL。

iota 和 partial_sum

vector<int> order(n);
iota(order.begin(), order.end(), 0);             // 0, 1, 2, ..., n-1

vector<long long> prefix(v.size());
partial_sum(v.begin(), v.end(), prefix.begin());  // prefix[i] = v[0] + ... + v[i]

iota 常用于“按另一个数组的值排序下标”：

vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
    return nums[i] < nums[j];
});

gcd 和 lcm

long long g = gcd(a, b);                          // C++17
long long l = lcm(a, b);                          // C++17

自己计算最小公倍数时，先除后乘可降低中间溢出风险：

long long l = a / gcd(a, b) * b;

这仍可能超过 long long，题目数值大时要先判断范围。

数值边界与数学函数

安全的无穷大

const int INF = numeric_limits<int>::max() / 4;
const long long LINF = numeric_limits<long long>::max() / 4;

除以 4 是为了让 dist[u] + weight 留出空间，避免直接用最大值时一做加法就溢出。

也可以使用：

int maxInt = INT_MAX;             // <climits>
long long maxLong = LLONG_MAX;

常用 cmath

auto distance = abs(a - b);
double root = sqrt(x);
double down = floor(x);
double up = ceil(x);
long long nearest = llround(x);

不要用 pow(a, b) 做整数幂或判断完全平方数：pow 返回浮点数，可能有精度误差。整数快速幂应该自己写二进制幂。

非负整数的向上取整除法：

// a >= 0, b > 0；写法避免 a + b - 1 溢出
long long ceilDiv = a / b + (a % b != 0);

负数取模规范化到 [0, mod)：

long long normalized = (x % mod + mod) % mod;

字符判断、大小写与解析

<cctype> 中最常用的函数：

isdigit(c);       // 数字
isalpha(c);       // 字母
isalnum(c);       // 字母或数字
islower(c);
isupper(c);
tolower(c);
toupper(c);

这些函数要求参数能表示为 unsigned char 或 EOF。稳妥写法：

bool digit = isdigit(static_cast<unsigned char>(c));

transform(s.begin(), s.end(), s.begin(), [](unsigned char c) {
    return static_cast<char>(tolower(c));
});

空白分隔字符串解析：

stringstream ss(line);
vector<int> values;
int x;
while (ss >> x) {
    values.push_back(x);
}

按指定分隔符切分：

stringstream ss(line);
string token;
while (getline(ss, token, ',')) {
    // 使用 token
}

Lambda、function 与比较器

捕获方式

int target = 10;

auto byReference = [&](int x) { return x < target; }; // 外部变量按引用捕获
auto byValue     = [=](int x) { return x < target; }; // 外部变量按值捕获
auto oneValue    = [target](int x) { return x < target; };

排序比较器经常需要引用外部数组：

sort(order.begin(), order.end(), [&](int i, int j) {
    if (nums[i] != nums[j]) return nums[i] < nums[j];
    return i < j;
});

递归 Lambda

LeetCode 中最直观的 C++17 写法是 std::function：

function<void(int, int)> dfs = [&](int u, int parent) {
    for (int v : graph[u]) {
        if (v == parent) continue;
        dfs(v, u);
    }
};

dfs(0, -1);

有返回值的记忆化搜索：

vector<int> memo(n, -1);

function<int(int)> solve = [&](int i) -> int {
    if (i == n) return 0;
    if (memo[i] != -1) return memo[i];
    return memo[i] = max(/* 选择一 */, /* 选择二 */);
};

std::function 有少量类型擦除开销，但在普通 LeetCode 题中通常不是瓶颈。深度可能达到$10^5$ 时，真正的风险是递归栈溢出，应改成显式栈或迭代算法。

迭代器与输出适配器

auto first = v.begin();
auto last = v.end();             // 指向尾后位置，不能解引用

auto second = next(first);       // 返回后一个迭代器，不修改 first
auto beforeLast = prev(last);
auto length = distance(first, last);

advance(first, 2);               // 原地向前移动 first 两步

复杂度取决于迭代器类型：vector 的 distance、next(it, k) 是$O(1)$，list、set、map 上移动$k$ 步是$O(k)$。

输出迭代器用于让算法自动向容器尾部插入：

vector<int> out;
copy_if(v.begin(), v.end(), back_inserter(out), [](int x) {
    return x % 2 == 0;
});

pair、tuple 和结构化绑定

它们不是容器，但几乎总和容器一起出现。

pair<int, string> p = {1, "one"};
cout << p.first << p.second;

auto [id, name] = p;            // C++17 结构化绑定

vector<pair<int, int>> edges;
edges.push_back({u, v});

tuple<int, int, string> t = {1, 2, "x"};
auto [a, b, s] = t;

pair、tuple、vector 都按字典序比较：先比第一个元素，相等再比下一个。因此区间题常能直接排序：

vector<pair<int, int>> intervals;
sort(intervals.begin(), intervals.end()); // 先按 left，再按 right

array 和 bitset

array

长度必须是编译期常量，但支持 STL 迭代器和算法：

array<int, 4> dr = {-1, 0, 1, 0};
array<int, 4> dc = {0, 1, 0, -1};

sort(dr.begin(), dr.end());
dr.fill(0);

固定字符集计数通常直接用数组，不必用哈希表：

array<int, 26> count{};         // 全部初始化为 0
for (char c : s) {
    ++count[c - 'a'];
}

bitset

位数也必须是编译期常量：

bitset<128> bits;
bits.set(3);
bits.reset(3);
bits.flip(5);

bool on = bits.test(5);
size_t ones = bits.count();
bool any = bits.any();
bool none = bits.none();

bitset 支持 & | ^ ~ << >>，适合固定范围集合和位运算 DP。位数运行期才知道时，可用整数数组手写动态位集；vector<bool> 是位压缩特化，元素访问返回代理对象，不完全等同于普通 vector<T>。

整数位操作

C++20 的 <bit> 提供了标准函数：

#include <bit>

int ones = popcount(static_cast<unsigned int>(x));
int leadingZeros = countl_zero(static_cast<unsigned int>(x));
int trailingZeros = countr_zero(static_cast<unsigned int>(x));
int width = bit_width(static_cast<unsigned int>(x));
bool powerOfTwo = has_single_bit(static_cast<unsigned int>(x));

在 LeetCode 的 C++17 + GCC/Clang 环境中，常用编译器内建函数：

int a = __builtin_popcount(x);       // unsigned int 中 1 的数量
int b = __builtin_popcountll(x);     // unsigned long long 中 1 的数量
int c = __builtin_ctz(x);            // 末尾 0 的数量；x 不能为 0
int d = __builtin_clz(x);            // 前导 0 的数量；x 不能为 0

__builtin_* 不是 C++ 标准库。提交前要确认编译器；另外 ctz(0)、clz(0) 的行为未定义，必须先判零。

list 为什么很少用

list 是双向链表，已知迭代器时插入、删除是$O(1)$，而且其他节点的迭代器不会失效。但它不能随机访问，缓存局部性也差。

LeetCode 的链表题通常直接操作题目提供的 ListNode*，并不需要 std::list。只有明确需要以下能力时再考虑它：

• 持有稳定迭代器并频繁在中间增删
• 使用 splice 在链表间$O(1)$ 转移节点
• 实现 LRU Cache：list + unordered_map<Key, list::iterator>

高频组合模板

Top K：小顶堆保留最大的 K 个

priority_queue<int, vector<int>, greater<int>> pq;

for (int x : nums) {
    pq.push(x);
    if (static_cast<int>(pq.size()) > k) {
        pq.pop();
    }
}
// pq.top() 是第 k 大元素

前缀和 + 哈希：和为 k 的子数组个数

long long answer = 0;
long long prefix = 0;
unordered_map<long long, int> count;
count[0] = 1;

for (int x : nums) {
    prefix += x;
    auto it = count.find(prefix - k);
    if (it != count.end()) {
        answer += it->second;
    }
    ++count[prefix];
}

动态中位数：两个堆

priority_queue<int> left;                               // 较小一半，大顶堆
priority_queue<int, vector<int>, greater<int>> right;  // 较大一半，小顶堆

void add(int x) {
    if (left.empty() || x <= left.top()) left.push(x);
    else right.push(x);

    if (left.size() > right.size() + 1) {
        right.push(left.top());
        left.pop();
    } else if (right.size() > left.size()) {
        left.push(right.top());
        right.pop();
    }
}

LRU Cache：list + unordered_map

using Entry = pair<int, int>;   // {key, value}
list<Entry> items;              // 表头最新，表尾最旧
unordered_map<int, list<Entry>::iterator> index;

// 访问节点后移到表头，不复制节点
auto it = index[key];
items.splice(items.begin(), items, it);

容器内删除的正确写法

遍历关联容器时删除元素：

for (auto it = m.begin(); it != m.end(); ) {
    if (shouldErase(*it)) {
        it = m.erase(it);        // erase 返回下一个有效迭代器
    } else {
        ++it;
    }
}

不要在范围 for 中直接删除当前元素：

// 错误示意：删除可能让循环内部持有的迭代器失效
for (int x : s) {
    // s.erase(x);
}

高频坑

面试前背诵清单

1. vector：push_back / pop_back / size / empty / reserve / resize
2. string：substr / find / npos / stoi / to_string
3. stack：push / top / pop
4. queue：push / front / back / pop
5. deque：push_front / push_back / front / back / pop_front / pop_back
6. priority_queue：默认大顶堆；小顶堆用 greater
7. set/map：有序，O(log n)，支持 lower_bound
8. unordered_set/map：平均 O(1)，无序，最坏 O(n)
9. lower_bound：第一个 >= x；upper_bound：第一个 > x
10. map[key] 会插入；multiset.erase(value) 会删除全部匹配值
11. sort + unique + erase 完成 vector 去重
12. 遍历中删除：it = container.erase(it)
13. find / count / min_element / max_element 都返回值或迭代器，先判 end
14. remove / remove_if 不缩短容器，必须配合 erase
15. nth_element 平均 O(n) 找第 k 小，但不会完整排序
16. accumulate 的初始值决定结果类型，求和常写 0LL
17. iota 生成连续值；gcd / lcm 位于 <numeric>
18. next_permutation 从升序开始枚举全部排列
19. 比较器必须严格，相等时返回 false
20. 递归 Lambda：function<返回类型(参数...)> f = [&](参数...) { ... f(...); }

最后只记一个判断顺序：

能用 vector 吗？
  -> 不能，因为要按 key 查：需要有序吗？
       -> 不需要：unordered_map / unordered_set
       -> 需要：map / set
  -> 不能，因为只关心最值：priority_queue
  -> 不能，因为操作受限：stack / queue / deque