本文最后更新于18 天前，其中的信息可能已经过时，如有错误请在评论区留言

常用技巧/方法

整数转字符串

使用 std::to_string (C++11 及以上)

#include <string>
#include <iostream>

int main() {
    int num = 123;
    std::string str = std::to_string(num);
    std::cout << str << std::endl; // 输出: "123"
    return 0;
}

最大值、最小值

整数类型

类型	最小值宏	最大值宏	备注
`char`	`CHAR_MIN`	`CHAR_MAX`	`char` 可有符号也可无符号，取决于实现
`signed char`	`SCHAR_MIN`	`SCHAR_MAX`	明确有符号
`unsigned char`	—	`UCHAR_MAX`	最小值隐含为 0
`short`	`SHRT_MIN`	`SHRT_MAX`	—
`unsigned short`	—	`USHRT_MAX`	最小值 0
`int`	`INT_MIN`	`INT_MAX`	—
`unsigned int`	—	`UINT_MAX`	最小值 0
`long`	`LONG_MIN`	`LONG_MAX`	—
`unsigned long`	—	`ULONG_MAX`	最小值 0
`long long`	`LLONG_MIN`	`LLONG_MAX`	C99 开始支持
`unsigned long long`	—	`ULLONG_MAX`	最小值 0
—	`CHAR_BIT`	—	每字节位数

浮点类型

类型	最小正正规化宏	最大值宏	备注
`float`	`FLT_MIN`	`FLT_MAX`	最小正正规化非零值
`double`	`DBL_MIN`	`DBL_MAX`	—
`long double`	`LDBL_MIN`	`LDBL_MAX`	—

浮点类型的最小值宏（如 FLT_MIN）均表示最小的正规化正数，非负负下溢值；若需表示最负数，可用 -FLT_MAX、-DBL_MAX、-LDBL_MAX。

查询方法find() count()

容器	`find()` 返回值	`count()` 返回值	时间复杂度	适用场景
`std::set`	迭代器（或 `end()`）	`0` 或 `1`	O(log n)	有序去重集合
`std::map`	迭代器（或 `end()`）	`0` 或 `1`	O(log n)	有序键值对
`std::unordered_set`	迭代器（或 `end()`）	`0` 或 `1`	平均 O(1)	快速哈希查找
`std::vector`	迭代器（或 `end()`）	出现次数	O(n)	线性搜索
`std::multiset`	第一个匹配的迭代器	出现次数	O(log n)	允许重复的有序集合

vector 是顺序容器，存储方式为连续内存，未内置快速查找算法。
set/map 是关联容器，基于红黑树（或哈希表）实现，天然支持高效查找（O(log n) 或 O(1)），因此提供了.find() 成员方法。

也就是说，vector使用find方法：

std::vector v = {1, 2, 3};
auto it = std::find(v.begin(), v.end(), 2); // 全局函数

set等关联容器使用find方法：

std::set s = {1, 2, 3};
auto it = s.find(2); // O(log n)，利用红黑树特性

count方法与find方法同理

std::accumulate()求和函数

原型：

// 基本形式，使用 operator+ 进行累加
template<class InputIt, class T>
T accumulate(InputIt first, InputIt last, T init);

// 带自定义二元运算的版本
template<class InputIt, class T, class BinaryOperation>
T accumulate(InputIt first, InputIt last, T init, BinaryOperation op);

从迭代器 first 到 last 遍历，初始值为 init，默认使用加法（即 operator+）将每个元素与累加值结合。如果提供了自定义的 op，则用该运算符进行操作。

#include <iostream>
#include <vector>
#include <numeric>  // std::accumulate

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    
    // 使用 std::accumulate 计算总和，初始值为 0
    int sum = std::accumulate(numbers.begin(), numbers.end(), 0);
    
    std::cout << "总和为: " << sum << std::endl; // 输出 15
    return 0;
}

位运算

整数通常以二进制形式存储。位运算就是对这些二进制位逐位进行操作，可以实现高效且底层的数值处理。

按位与（&）

对应位都为 1 时结果才为 1，否则为 0。

示例：

二进制：0101 & 0011 = 0001
十进制：5 & 3 = 1

按位或（|）

对应位只要有一个为 1，结果即为 1。
示例：

二进制：0101 | 0011 = 0111
十进制：5 | 3 = 7

按位异或（^）

对应位相同为 0，不同为 1。
示例：

二进制：0101 ^ 0011 = 0110
十进制：5 ^ 3 = 6

按位取反（~）

将每一位取反（0 变 1，1 变 0）。需要注意的是，取反操作符在有符号整数上通常会返回一个负值，这是因为 C++ 使用补码来表示负数。
示例：

~5 的结果在 32 位系统下通常为 -6（因为 ~5 = -(5+1)）。

左移运算符（<<）

将二进制位向左移动指定的位数，右侧补零。左移相当于乘以 2 的指定次幂。
示例：

5 << 1 将 5（二进制 0101）左移一位变为 1010，即十进制的 10。

右移运算符（>>）

将二进制位向右移动指定的位数。对于无符号数，左侧补 0；对于有符号数，不同编译器可能执行算术右移（保留符号位）或逻辑右移。
示例：

5 >> 1 将 5（二进制 0101）右移一位变为 0010，即十进制的 2。

无序映射unordered_map

unordered_map 是 C++ 标准模板库（STL）中的一个关联容器，主要用于存储键值对（key-value pairs），并能在O(1)的时间复杂度下完成查找、插入和删除操作，但在最坏情况下可能会退化为O(n)。

unordered_map 提供了一种以键值对形式存储数据的方式，键（key）必须是唯一的，并且该容器内部并不保持元素的顺序。适合需要快速查找的场景，例如字典查找、缓存机制等。

unordered_map 通常基于哈希表实现。在内部，它使用了哈希函数将键映射到桶（bucket）中。每个桶中可以存储一个或多个键值对（一般采用链表或开放寻址法来处理哈希冲突）。这种实现机制使得大部分基本操作的平均时间复杂度为 O(1)。

插入元素

通过 insert() 或使用下标操作符 operator[] 插入元素。例如：

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> umap;
    
    // 使用 insert() 方法
    umap.insert({"apple", 3});
    umap.insert(std::make_pair("banana", 5));

    // 使用下标操作符（如果键不存在，则会自动创建一个默认值）
    umap["cherry"] = 7;

    for (const auto& pair : umap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}

查找元素

使用 find() 方法进行查找，如果找到对应键则返回迭代器，否则返回 end() 迭代器：

auto it = umap.find("banana");
if (it != umap.end()) {
    std::cout << "Found: " << it->second << std::endl;
} else {
    std::cout << "Not found!" << std::endl;
}

删除元素

可以使用 erase() 方法删除指定键或者指定迭代器指向的元素：

umap.erase("apple"); // 根据键删除
// 或者根据迭代器删除
auto it = umap.find("banana");
if (it != umap.end()) {
    umap.erase(it);
}

深度搜索的C++代码实现

不重点探讨深搜算法，而注重探讨深搜算法用C++代码的实现方式

这是一个遍历矩形所有节点的代码

int n, m;  // 矩形的行数和列数
vector<vector<bool>> visited;  // 记录每个单元格是否已被访问

// DFS 递归函数，(x, y) 为当前访问的单元格坐标
void dfs(int x, int y) {
    // 1. 边界检查：如果超出矩形范围则返回
    if (x < 0 || x >= n || y < 0 || y >= m)
        return;
    
    // 2. 如果当前单元格已经访问过，则直接返回
    if (visited[x][y])
        return;
    
    // 3. 标记当前单元格为已访问
    visited[x][y] = true;
    
    // 4. 在此可以对当前单元格进行处理，这里简单输出坐标
    cout << "(" << x << ", " << y << ") ";
    
    // 5. 递归访问当前单元格的相邻单元格（上下左右）
    dfs(x - 1, y);   // 向上
    dfs(x + 1, y);   // 向下
    dfs(x, y - 1);   // 向左
    dfs(x, y + 1);   // 向右
}

似乎，DFS只需要下面这三步：
递归终止条件：当节点或坐标超出范围或已经被访问时立即返回。
状态标记：确保遍历不会重复进入已处理的部分。
递归调用：对所有可能的下一步进行递归探索。

如果要记录DFS的路径，得加两步：
在递归开始时将当前节点/坐标添加到路径记录中；
在递归结束（即返回上层调用）前将当前元素从路径中移除（回溯操作）；

int n, m;  // 网格的行数和列数
vector<vector<bool>> visited;  // 记录每个格子是否已访问
vector<pair<int, int>> path;   // 当前 DFS 路径，记录 (x, y) 坐标

// DFS 递归函数，(x, y) 为当前访问的格子坐标
void dfs(int x, int y) {
    // 1. 边界检查：如果超出网格范围，返回
    if (x < 0 || x >= n || y < 0 || y >= m)
        return;
    
    // 2. 如果该格子已访问，返回
    if (visited[x][y])
        return;
    
    // 3. 标记格子已访问，添加到路径记录中
    visited[x][y] = true;
    path.push_back({x, y});
    
    // 4. 处理当前路径：此处输出当前路径
    cout << "当前路径: ";
    for (auto &p : path)
        cout << "(" << p.first << "," << p.second << ") ";
    cout << endl;
    
    // 5. 对四个方向进行递归调用（上、下、左、右）
    dfs(x - 1, y);  // 向上
    dfs(x + 1, y);  // 向下
    dfs(x, y - 1);  // 向左
    dfs(x, y + 1);  // 向右
    
    // 6. 回溯：移除当前格子，恢复状态
    path.pop_back();
}

在DFS中如何管理 visited 数组（已访问数组），该作为全局变量还是作为DFS的一个参数传入？

将 visited 作为全局变量（或外部变量）：

遍历整个图或树：当你只需要遍历每个节点一次，目的是防止重复访问（如查找连通分量、检测环路等），整个搜索过程中所有递归调用共享同一状态，这时将 visited 声明在函数外部或作为全局变量是非常自然且高效的。
状态唯一性：你希望整个图的访问状态是统一的，也就是说，一旦一个节点被访问过，就在所有后续递归中保持已访问状态，不需要针对每个路径分开记录。
简化参数传递：如果不需要在递归过程中回退“访问”的状态，这样设计能够减少参数传递，并使代码更简洁。

将 visited 作为递归函数的参数

需要维护局部状态或回溯：在一些问题中（如求解迷宫、全路径搜索、组合问题等），你希望每个递归调用都能独立决定“此时此刻”的访问状态，递归返回后能够回退已做的状态修改。传入 visited 参数可以让你在每条路径中独立管理访问记录，并在返回前“撤销”访问标记。
函数纯粹性和可重入性：如果你希望 DFS 函数成为一个纯函数，即输出仅依赖于输入参数而不是全局状态，那么把 visited 作为参数传入是更好的选择。这样可以减少副作用，方便调试和单元测试。
多条路径分叉独立性：当有多个可能路径并行搜索时，某个节点在不同的路径上其“访问状态”可能不同，此时不能使用唯一的全局 visited，而应在每个递归调用中传递独立的或经过适当修改的 visited 副本。

这里的“每个递归调用都能独立决定“此时此刻”的访问状态，递归返回后能够回退已做的状态修改”比较难以理解，举个例子：

void dfs(int i, int j, vector<vector<bool>> &visited, vector<pair<int,int>> &path) {
    // 检查边界
    if (i < 0 || i >= rows || j < 0 || j >= cols)
        return;
    // 如果已访问或当前位置不可通行（0），直接返回
    if (visited[i][j] || grid[i][j] == 0)
        return;
    
    // 标记访问并加入路径
    visited[i][j] = true;
    path.push_back({i, j});

    // 到达终点则输出当前路径
    if (i == rows - 1 && j == cols - 1) {
        cout << "找到路径：";
        for (auto &p : path) {
            cout << "(" << p.first << "," << p.second << ") ";
        }
        cout << endl;
    } else {
        // 定义四个方向移动的偏移量：下、上、右、左
        int di[4] = {1, -1, 0, 0};
        int dj[4] = {0, 0, 1, -1};
        for (int k = 0; k < 4; k++) {
            dfs(i + di[k], j + dj[k], visited, path);
        }
    }
    
    // 回溯：撤销当前访问状态和路径记录
    path.pop_back();
    visited[i][j] = false;
}

总而言之：大多数情况是要考虑该DFS是否需要寻找探索所有可能的情况，当问题只需一次遍历时，使用全局 visited 数组更简单直接；而在需要探索所有可能情况并回溯的场景下，传递 visited 作为参数更为灵活。