C++ 头文件与常用函数

专为算法刷题设计的头文件使用指南 - 避坑版

目录

• 输入输出流 iostream

• 动态数组 vector

• 算法库 algorithm

• 字符串 string

• 数学函数 cmath

• 队列 queue

• 栈 stack

• 集合 set

• 映射 map

• 哈希表 unordered_map

• 哈希集合 unordered_set

• 工具 utility

• 数值算法 numeric

• C字符串 cstring

• 常量限制 climits

• 位集合 bitset

输入输出流 iostream

是什么

C++标准输入输出库，提供cin、cout、endl等对象进行格式化输入输出。

怎么用

​x
#include <iostream>
using namespace std;

// 基础输入输出
int n;
cin >> n;
cout << n << endl;

// 多个变量
int a, b, c;
cin >> a >> b >> c;
cout << a << " " << b << " " << c << endl;

// 加速IO（竞赛必备）
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

// 链式输入输出
cout << "Result: " << a + b << endl;

为什么用

• 类型安全，自动识别数据类型

• 支持自定义类型的重载

• 比printf/scanf更易用（但默认较慢）

常见陷阱与注意事项

1. cin读取字符串遇到空格会停止

xxxxxxxxxx
// ❌ 错误：只能读到第一个空格前
string s;
cin >> s;  // 输入"hello world"，只得到"hello"

// ✅ 正确：读取整行
string s;
getline(cin, s);  // 得到"hello world"

2. cin和getline混用的坑

xxxxxxxxxx
// ❌ 错误示例
int n;
cin >> n;
string s;
getline(cin, s);  // s会是空字符串！

// ✅ 正确：清除缓冲区的换行符
int n;
cin >> n;
cin.ignore();  // 忽略换行符
string s;
getline(cin, s);

3. 加速IO后不能混用scanf/printf

xxxxxxxxxx
// ❌ 错误：加速后混用会导致输出顺序错乱
ios::sync_with_stdio(false);
cin >> n;
printf("%d\n", n);  // 可能不按预期输出

// ✅ 正确：统一使用cin/cout或scanf/printf
ios::sync_with_stdio(false);
cin >> n;
cout << n << endl;

4. endl vs '\n'

xxxxxxxxxx
// endl会刷新缓冲区，较慢
cout << n << endl;

// '\n'不刷新缓冲区，更快（推荐）
cout << n << '\n';

// 大量输出时差异明显
for(int i = 0; i < 100000; i++) {
    cout << i << '\n';  // 快
    // cout << i << endl;  // 慢
}

5. 读取到文件末尾

xxxxxxxxxx
// 方法1：while(cin >> n)
int n;
while(cin >> n) {
    // 处理n
}

// 方法2：检查EOF
while(scanf("%d", &n) != EOF) {
    // 处理n
}

// 方法3：先读取数据量
int t;
cin >> t;
while(t--) {
    // 处理每组数据
}

6. 浮点数输出精度

xxxxxxxxxx
#include <iomanip>

double pi = 3.1415926535;

// 保留2位小数
cout << fixed << setprecision(2) << pi << endl;  // 3.14

// 科学计数法
cout << scientific << pi << endl;  // 3.14e+00

// 恢复默认
cout << defaultfloat << pi << endl;

7. 终极性能封印：解除 cin/cout 的同步限制（防 TLE）

在默认情况下，cin/cout 比 scanf/printf 慢非常多。因为 C++ 为了保证混合输入输出时的兼容性，强制把 cin/cout 和 C 语言的 stdio 缓冲区绑定在了一起。在遇到百万级别的数据输入时，不关同步必然超时（Time Limit Exceeded）。

✅ 考场必备的加速咒语（写在 main 函数第一行）：

xxxxxxxxxx
ios::sync_with_stdio(false); // 打破 C++ 和 C 的输入输出流绑定
cin.tie(NULL);               // 解除 cin 和 cout 的绑定（默认 cin 执行前会刷新 cout）
cout.tie(NULL);              // 解除 cout 绑定的非必要刷新

⚠️ 致命陷阱： 加了这三行代码后，绝对不能再在代码中混用 scanf/printf/puts！否则缓冲区的剥离会导致输入输出顺序彻底错乱。

补充：scanf/printf格式化（更快）

xxxxxxxxxx
#include <cstdio>

// 常用格式符
int n;
scanf("%d", &n);        // int
printf("%d\n", n);

long long ll;
scanf("%lld", &ll);     // long long
printf("%lld\n", ll);

double d;
scanf("%lf", &d);       // double
printf("%.2lf\n", d);   // 保留2位小数

char c;
scanf(" %c", &c);       // 注意空格，跳过空白字符

char s[100];
scanf("%s", s);         // 字符串（遇空格停止）
printf("%s\n", s);

// 读取整行（包含空格）
char line[1000];
fgets(line, sizeof(line), stdin);

动态数组 vector

是什么

动态大小的数组，自动管理内存，是STL中最常用的容器。

怎么用

xxxxxxxxxx
#include <vector>
using namespace std;

// 声明
vector<int> v;                    // 空vector
vector<int> v(10);                // 10个元素，默认值0
vector<int> v(10, 5);             // 10个元素，值都是5
vector<int> v = {1, 2, 3, 4, 5};  // 初始化列表
vector<int> v(arr, arr + n);      // 从数组构造

// 基本操作
v.push_back(x);        // 尾部添加
v.pop_back();          // 删除尾部
v.size();              // 元素个数
v.empty();             // 是否为空
v.clear();             // 清空
v.front();             // 第一个元素
v.back();              // 最后一个元素
v[i];                  // 访问第i个元素
v.at(i);               // 带边界检查的访问

// 插入删除
v.insert(v.begin() + i, x);  // 在位置i插入x
v.erase(v.begin() + i);      // 删除位置i的元素
v.erase(v.begin() + i, v.begin() + j);  // 删除[i, j)

// 大小调整
v.resize(n);           // 改变大小为n
v.reserve(n);          // 预留空间（不改变size）

// 二维vector
vector<vector<int>> matrix(n, vector<int>(m, 0));

为什么用

• 动态大小，不需要预先知道数组长度

• 自动内存管理，不会内存泄漏

• 支持所有STL算法

• 比数组更安全（at()会检查边界）

常见陷阱与注意事项

1. size()返回无符号类型

xxxxxxxxxx
vector<int> v;
// ❌ 错误：size()是unsigned，减法可能溢出
for(int i = 0; i < v.size() - 1; i++) {  // v为空时溢出！
    // ...
}

// ✅ 正确方法1：转为int
for(int i = 0; i < (int)v.size() - 1; i++) {
    // ...
}

// ✅ 正确方法2：先判断
if(!v.empty()) {
    for(int i = 0; i < v.size() - 1; i++) {
        // ...
    }
}

// ✅ 正确方法3：使用有符号变量
int n = v.size();
for(int i = 0; i < n - 1; i++) {
    // ...
}

2. 迭代器失效

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

// ❌ 错误：erase后迭代器失效
for(auto it = v.begin(); it != v.end(); it++) {
    if(*it % 2 == 0) {
        v.erase(it);  // it失效！
    }
}

// ✅ 正确：erase返回下一个有效迭代器
for(auto it = v.begin(); it != v.end(); ) {
    if(*it % 2 == 0) {
        it = v.erase(it);  // 更新it
    } else {
        it++;
    }
}

// ❌ 错误：push_back可能导致扩容，所有迭代器失效
for(auto it = v.begin(); it != v.end(); it++) {
    v.push_back(*it);  // 危险！
}

// ✅ 正确：先记录大小
int n = v.size();
for(int i = 0; i < n; i++) {
    v.push_back(v[i]);
}

3. 二维vector初始化陷阱

xxxxxxxxxx
// ❌ 错误：所有行共享同一个vector
vector<int> row(m, 0);
vector<vector<int>> matrix(n, row);
matrix[0][0] = 1;  // 不会影响其他行（这个是对的）

// ❌ 错误：这样会有问题
vector<vector<int>> matrix(n);  // n个空vector
matrix[0].push_back(1);  // 第0行有1个元素
// matrix[1][0];  // 越界！第1行还是空的

// ✅ 正确：每行独立初始化
vector<vector<int>> matrix(n, vector<int>(m, 0));

// ✅ 正确：逐行初始化
vector<vector<int>> matrix(n);
for(int i = 0; i < n; i++) {
    matrix[i].resize(m, 0);
}

4. 访问越界

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

// ❌ 错误：[]不检查边界
cout << v[10] << endl;  // 未定义行为，可能崩溃

// ✅ 正确：at()会检查边界并抛出异常
try {
    cout << v.at(10) << endl;
} catch(out_of_range& e) {
    cout << "越界！" << endl;
}

// ✅ 最佳：先判断
if(i >= 0 && i < v.size()) {
    cout << v[i] << endl;
}

5. clear()不释放内存

xxxxxxxxxx
vector<int> v(1000000);
v.clear();  // size变为0，但capacity不变

// 真正释放内存
vector<int>().swap(v);  // 或
v.shrink_to_fit();      // C++11

6. 比较操作

xxxxxxxxxx
vector<int> v1 = {1, 2, 3};
vector<int> v2 = {1, 2, 4};

// 字典序比较
v1 < v2;   // true
v1 == v2;  // false

7. 高阶技巧：用 emplace_back 代替 push_back

当 vector 中存储的是 pair 或自定义结构体时，push_back 会先创建一个临时对象，再拷贝/移动进去。而 emplace_back 支持直接在容器末尾原地构造对象，省去了拷贝的开销。

xxxxxxxxxx
vector<pair<int, int>> v; 
// ❌ 略慢：需要大括号构造临时 
pair v.push_back({1, 2}); 
// ✅ 更快：直接传入构造参数，原地生成 
v.emplace_back(1, 2); 

算法库 algorithm

是什么

提供各种算法函数，如排序、查找、反转等，是刷题必备的头文件。

怎么用

xxxxxxxxxx
#include <algorithm>
using namespace std;

vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

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

// 自定义排序
sort(v.begin(), v.end(), [](int a, int b) {
    return a > b;  // 降序
});

// 二分查找（必须已排序）
bool found = binary_search(v.begin(), v.end(), 5);

// lower_bound: 第一个>=x的位置
auto it = lower_bound(v.begin(), v.end(), 5);
int pos = it - v.begin();  // 获取下标

// upper_bound: 第一个>x的位置
auto it = upper_bound(v.begin(), v.end(), 5);

// 反转
reverse(v.begin(), v.end());

// 去重（必须先排序）
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

// 最大最小值
int maxVal = *max_element(v.begin(), v.end());
int minVal = *min_element(v.begin(), v.end());

// 填充
fill(v.begin(), v.end(), 0);

// 全排列
sort(v.begin(), v.end());
do {
    // 处理当前排列
} while(next_permutation(v.begin(), v.end()));

// 部分排序（前k个最小）
partial_sort(v.begin(), v.begin() + k, v.end());

// 第k小元素
nth_element(v.begin(), v.begin() + k, v.end());

为什么用

• 高效实现，经过优化

• 代码简洁，避免手写错误

• 通用性强，适用于各种容器

常见陷阱与注意事项

1. sort的比较函数必须严格弱序

xxxxxxxxxx
// ❌ 错误：使用<=会导致未定义行为
sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b;  // 错误！
});

// ✅ 正确：使用<
sort(v.begin(), v.end(), [](int a, int b) {
    return a < b;
});

// 严格弱序要求：
// 1. 反自反性：comp(a, a) == false
// 2. 非对称性：comp(a, b) == true 则 comp(b, a) == false
// 3. 传递性：comp(a, b) && comp(b, c) 则 comp(a, c)

2. 二分查找前必须排序

xxxxxxxxxx
vector<int> v = {3, 1, 4, 1, 5};

// ❌ 错误：未排序就二分
bool found = binary_search(v.begin(), v.end(), 4);  // 结果不可靠

// ✅ 正确：先排序
sort(v.begin(), v.end());
bool found = binary_search(v.begin(), v.end(), 4);

3. lower_bound和upper_bound的区别

xxxxxxxxxx
vector<int> v = {1, 2, 2, 2, 3, 4, 5};
sort(v.begin(), v.end());

// lower_bound: 第一个 >= target
auto it1 = lower_bound(v.begin(), v.end(), 2);
cout << *it1 << endl;  // 2（第一个2）
cout << it1 - v.begin() << endl;  // 1（下标）

// upper_bound: 第一个 > target
auto it2 = upper_bound(v.begin(), v.end(), 2);
cout << *it2 << endl;  // 3（第一个大于2的）
cout << it2 - v.begin() << endl;  // 4（下标）

// 统计元素个数
int count = upper_bound(v.begin(), v.end(), 2) 
          - lower_bound(v.begin(), v.end(), 2);  // 3个2

// 查找不存在的元素
auto it3 = lower_bound(v.begin(), v.end(), 10);
if(it3 == v.end()) {
    cout << "不存在" << endl;
}

4. unique只是移动元素，不删除

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

// ❌ 错误：unique不改变size
unique(v.begin(), v.end());
cout << v.size() << endl;  // 还是7

// ✅ 正确：配合erase删除
sort(v.begin(), v.end());  // 必须先排序
v.erase(unique(v.begin(), v.end()), v.end());
cout << v.size() << endl;  // 4

// unique返回的是"新结尾"的迭代器
// 原理：[1, 2, 3, 4, 3, 3, 4] -> unique后变为 [1, 2, 3, 4, ?, ?, ?]
//                                                        ^返回这里

5. next_permutation的使用

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

// ❌ 错误：未排序，会漏掉一些排列
v = {3, 2, 1};
do {
    // 只会生成一个排列
} while(next_permutation(v.begin(), v.end()));

// ✅ 正确：从最小排列开始
sort(v.begin(), v.end());
do {
    // 打印当前排列
    for(int x : v) cout << x << " ";
    cout << endl;
} while(next_permutation(v.begin(), v.end()));

// 生成所有排列：3! = 6个
// 1 2 3
// 1 3 2
// 2 1 3
// 2 3 1
// 3 1 2
// 3 2 1

6. max_element和min_element返回迭代器

xxxxxxxxxx
vector<int> v = {3, 1, 4, 1, 5};

// ❌ 错误：直接当值用
int maxVal = max_element(v.begin(), v.end());  // 错误！

// ✅ 正确：解引用
int maxVal = *max_element(v.begin(), v.end());

// 获取最大值的下标
auto it = max_element(v.begin(), v.end());
int idx = it - v.begin();
cout << "最大值" << *it << "在下标" << idx << endl;

// 空容器会导致未定义行为
vector<int> empty;
// int maxVal = *max_element(empty.begin(), empty.end());  // 危险！

// 安全做法
if(!empty.empty()) {
    int maxVal = *max_element(empty.begin(), empty.end());
}

7. sort的时间复杂度陷阱

xxxxxxxxxx
// sort平均O(n log n)，最坏O(n log n)（C++11后保证）
// 但对于特殊数据可能较慢

// 对于大量重复元素，可以用stable_sort
vector<int> v(100000, 1);  // 全是1
stable_sort(v.begin(), v.end());  // 保持相对顺序

// 或者先去重再排序
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

8. 自定义排序的常见错误

xxxxxxxxxx
// 对pair排序
vector<pair<int, int>> v = {{1, 3}, {2, 1}, {1, 2}};

// 默认先按first排序，first相同按second排序
sort(v.begin(), v.end());
// 结果：{1, 2}, {1, 3}, {2, 1}

// 按second排序
sort(v.begin(), v.end(), [](auto& a, auto& b) {
    return a.second < b.second;
});

// 按first降序，second升序
sort(v.begin(), v.end(), [](auto& a, auto& b) {
    if(a.first != b.first) return a.first > b.first;
    return a.second < b.second;
});

// 对结构体排序
struct Student {
    string name;
    int score;
};

vector<Student> students;
sort(students.begin(), students.end(), [](Student& a, Student& b) {
    return a.score > b.score;  // 按分数降序
});

字符串 string

是什么

C++标准库的字符串类，比C风格字符串更安全、更易用。

怎么用

xxxxxxxxxx
#include <string>
using namespace std;

// 声明与初始化
string s = "hello";
string s(10, 'a');  // "aaaaaaaaaa"
string s(s2);       // 拷贝构造

// 基本操作
s.length() / s.size();  // 长度
s.empty();              // 是否为空
s.clear();              // 清空
s[i];                   // 访问第i个字符
s.at(i);                // 带边界检查

// 拼接
s += "world";
s = s + " !";
s.append("!");

// 子串
s.substr(pos);          // 从pos到末尾
s.substr(pos, len);     // 从pos开始长度len

// 查找
s.find(str);            // 查找子串，返回位置或string::npos
s.find(str, pos);       // 从pos开始查找
s.rfind(str);           // 从后往前查找
s.find_first_of("aeiou");  // 查找第一个元音
s.find_last_of("aeiou");   // 查找最后一个元音

// 插入删除
s.insert(pos, str);     // 在pos位置插入
s.erase(pos, len);      // 删除从pos开始长度len

// 替换
s.replace(pos, len, str);  // 替换

// 比较
s1 == s2;
s1 < s2;  // 字典序

// 转换
int num = stoi(s);           // string转int
long long num = stoll(s);    // string转long long
double d = stod(s);          // string转double
string s = to_string(123);   // 数字转string

为什么用

• 自动内存管理

• 丰富的成员函数

• 支持运算符重载（+, ==, <等）

• 比C字符串更安全

常见陷阱与注意事项

1. find返回string::npos表示未找到

xxxxxxxxxx
string s = "hello world";

// ❌ 错误：find返回size_t（无符号），不能用-1判断
if(s.find("abc") == -1) {  // 错误！
    // ...
}

// ✅ 正确：使用string::npos
if(s.find("abc") == string::npos) {
    cout << "未找到" << endl;
}

// ✅ 或者判断是否不等于npos
if(s.find("world") != string::npos) {
    cout << "找到了" << endl;
}

// string::npos的值通常是-1（转为size_t后是最大值）
cout << string::npos << endl;  // 18446744073709551615（64位）

2. substr的参数陷阱

xxxxxxxxxx
string s = "hello";

// ❌ 错误：长度超出范围不会报错，自动截断
string sub = s.substr(2, 100);  // "llo"（不是错误）

// ❌ 错误：起始位置超出范围会抛出异常
try {
    string sub = s.substr(10);  // 抛出out_of_range
} catch(out_of_range& e) {
    cout << "越界" << endl;
}

// ✅ 正确：先检查
if(pos < s.length()) {
    string sub = s.substr(pos, len);
}

// substr(pos)：从pos到末尾
string sub = s.substr(2);  // "llo"

// substr(pos, len)：从pos开始长度len
string sub = s.substr(2, 2);  // "ll"

3. 字符串拼接的效率问题

xxxxxxxxxx
// ❌ 低效：每次+=都可能重新分配内存
string s;
for(int i = 0; i < 100000; i++) {
    s += "a";  // O(n²)
}

// ✅ 高效：预留空间
string s;
s.reserve(100000);  // 预留空间
for(int i = 0; i < 100000; i++) {
    s += "a";  // O(n)
}

// ✅ 或使用构造函数
string s(100000, 'a');

4. 字符串比较的字典序

xxxxxxxxxx
string s1 = "abc";
string s2 = "abd";

s1 < s2;   // true（字典序）
s1 == s2;  // false

// 数字字符串的比较
string n1 = "10";
string n2 = "2";
n1 < n2;   // true（字典序："1" < "2"）

// ✅ 正确：转为数字比较
int num1 = stoi(n1);
int num2 = stoi(n2);
num1 < num2;  // false（10 > 2）

5. stoi等转换函数的异常

xxxxxxxxxx
// ❌ 错误：非法字符串会抛出异常
string s = "abc";
int n = stoi(s);  // 抛出invalid_argument

// ❌ 错误：超出范围会抛出异常
string s = "99999999999999999999";
int n = stoi(s);  // 抛出out_of_range

// ✅ 正确：捕获异常
try {
    int n = stoi(s);
} catch(invalid_argument& e) {
    cout << "非法输入" << endl;
} catch(out_of_range& e) {
    cout << "超出范围" << endl;
}

// stoi会忽略前导空格和后面的非数字字符
string s = "  123abc";
int n = stoi(s);  // 123

// 获取转换了多少字符
size_t pos;
int n = stoi(s, &pos);
cout << "转换了" << pos << "个字符" << endl;

6. 字符串与字符的区别

xxxxxxxxxx
string s = "hello";

// ❌ 错误：单引号是字符，双引号是字符串
s += 'a';   // 正确：添加字符
s += "a";   // 正确：添加字符串
s = s + 'a';  // 错误！不能直接相加

// ✅ 正确
s.push_back('a');  // 添加字符
s += 'a';          // 添加字符
s += "a";          // 添加字符串
s = s + "a";       // 字符串拼接

7. 字符串遍历与修改

xxxxxxxxxx
string s = "hello";

// 遍历（只读）
for(char c : s) {
    cout << c;
}

// 遍历（可修改）
for(char& c : s) {
    c = toupper(c);
}
cout << s << endl;  // "HELLO"

// 使用下标修改
for(int i = 0; i < s.length(); i++) {
    s[i] = toupper(s[i]);
}

数学函数 cmath

是什么

C++数学函数库，提供常用数学运算函数。

怎么用

xxxxxxxxxx
#include <cmath>
using namespace std;

// 基本运算
sqrt(x);        // 平方根
pow(x, y);      // x的y次方
abs(x);         // 绝对值（整数用abs，浮点用fabs）
fabs(x);        // 浮点数绝对值

// 取整
ceil(x);        // 向上取整
floor(x);       // 向下取整
round(x);       // 四舍五入
trunc(x);       // 截断小数部分

// 对数
log(x);         // 自然对数（ln）
log10(x);       // 以10为底
log2(x);        // 以2为底（C++11）

// 三角函数
sin(x);         // 正弦（弧度）
cos(x);         // 余弦
tan(x);         // 正切
asin(x);        // 反正弦
acos(x);        // 反余弦
atan(x);        // 反正切
atan2(y, x);    // 返回y/x的反正切（考虑象限）

// 其他
exp(x);         // e^x
fmod(x, y);     // 浮点数取模
hypot(x, y);    // sqrt(x²+y²)

为什么用

• 高精度实现

• 跨平台一致性

• 处理特殊值（NaN, Inf）

常见陷阱与注意事项

1. pow的精度和效率问题

xxxxxxxxxx
// ❌ 低效：pow对整数也返回double
int result = pow(2, 10);  // 返回double，可能有精度误差

// ✅ 高效：整数幂用快速幂
long long quickPow(long long a, long long b) {
    long long res = 1;
    while(b > 0) {
        if(b & 1) res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}

// pow的精度问题
cout << pow(10, 9) << endl;  // 可能输出999999999.999999

// ✅ 正确：四舍五入
int result = round(pow(10, 9));

// 对于小整数幂，直接乘更快
int x2 = x * x;           // 比pow(x, 2)快
int x3 = x * x * x;       // 比pow(x, 3)快

2. sqrt的参数必须非负

xxxxxxxxxx
// ❌ 错误：负数的平方根是NaN
double result = sqrt(-1);  // NaN（Not a Number）

// 检查NaN
if(isnan(result)) {
    cout << "结果是NaN" << endl;
}

// ✅ 正确：先判断
if(x >= 0) {
    double result = sqrt(x);
}

// 判断浮点数是否有效
isnan(x);   // 是否为NaN
isinf(x);   // 是否为无穷大
isfinite(x); // 是否为有限值

3. 浮点数比较的精度问题

xxxxxxxxxx
double a = 0.1 + 0.2;
double b = 0.3;

// ❌ 错误：直接比较
if(a == b) {  // false！
    cout << "相等" << endl;
}

// ✅ 正确：使用误差范围
const double EPS = 1e-9;
if(fabs(a - b) < EPS) {
    cout << "相等" << endl;
}

// 或使用函数
bool equal(double a, double b) {
    return fabs(a - b) < 1e-9;
}

4. 整数除法 vs 浮点除法

xxxxxxxxxx
int a = 5, b = 2;

// ❌ 错误：整数除法
double result = a / b;  // 2.0（先算5/2=2，再转double）

// ✅ 正确：至少一个转为double
double result = (double)a / b;  // 2.5
double result = 1.0 * a / b;    // 2.5
double result = a / (double)b;  // 2.5

5. abs vs fabs

xxxxxxxxxx
int x = -5;
double y = -5.5;

// abs用于整数
int result1 = abs(x);  // 5

// fabs用于浮点数
double result2 = fabs(y);  // 5.5

// ❌ 错误：混用可能导致精度丢失
int result = abs(-5.5);  // 可能是5（截断）

// ✅ 正确：根据类型选择
double result = fabs(-5.5);  // 5.5

// C++11：通用abs
#include <cstdlib>
auto result = std::abs(-5);    // int
auto result = std::abs(-5.5);  // double

6. 三角函数的弧度制

xxxxxxxxxx
// ❌ 错误：sin/cos等使用弧度，不是角度
double result = sin(90);  // 不是1！

// ✅ 正确：角度转弧度
const double PI = acos(-1);  // 或 3.14159265358979323846
double radians = 90 * PI / 180;
double result = sin(radians);  // 1

// 弧度转角度
double degrees = radians * 180 / PI;

7. log的底数

xxxxxxxxxx
// log是自然对数（ln），底数是e
double result = log(10);  // ln(10) ≈ 2.302585

// log10是常用对数，底数是10
double result = log10(100);  // 2

// log2是以2为底（C++11）
double result = log2(8);  // 3

// 换底公式：log_a(b) = log(b) / log(a)
double log_a_b = log(b) / log(a);

8. 取整函数的区别

xxxxxxxxxx
double x = 2.7;
double y = -2.7;

// ceil：向上取整（朝正无穷）
ceil(x);   // 3
ceil(y);   // -2

// floor：向下取整（朝负无穷）
floor(x);  // 2
floor(y);  // -3

// round：四舍五入
round(x);  // 3
round(y);  // -3

// trunc：截断小数（朝0）
trunc(x);  // 2
trunc(y);  // -2

// 注意：返回值是double，需要转换
int result = (int)ceil(x);

队列 queue

是什么

先进先出（FIFO）的数据结构，常用于BFS、任务调度等场景。

怎么用

xxxxxxxxxx
#include <queue>
using namespace std;

// 普通队列
queue<int> q;

q.push(x);        // 入队
q.pop();          // 出队（无返回值）
q.front();        // 队首元素
q.back();         // 队尾元素
q.empty();        // 是否为空
q.size();         // 队列大小

// 双端队列
deque<int> dq;

dq.push_back(x);   // 尾部插入
dq.push_front(x);  // 头部插入
dq.pop_back();     // 尾部删除
dq.pop_front();    // 头部删除
dq.front();
dq.back();
dq[i];             // 随机访问
dq.empty();
dq.size();

// 优先队列（大顶堆）
priority_queue<int> pq;

pq.push(x);       // 插入
pq.pop();         // 删除堆顶
pq.top();         // 获取堆顶
pq.empty();
pq.size();

// 小顶堆
priority_queue<int, vector<int>, greater<int>> pq;

为什么用

• queue：BFS、层序遍历、任务队列

• deque：滑动窗口、单调队列

• priority_queue：Dijkstra、Top K问题、贪心算法

常见陷阱与注意事项

1. pop()没有返回值

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

// ❌ 错误：pop()不返回值
int x = q.pop();  // 编译错误！

// ✅ 正确：先front()再pop()
int x = q.front();
q.pop();

// 或者一起写
while(!q.empty()) {
    int x = q.front();
    q.pop();
    // 处理x
}

2. 访问空队列导致未定义行为

xxxxxxxxxx
queue<int> q;

// ❌ 错误：空队列调用front()
int x = q.front();  // 未定义行为！

// ✅ 正确：先判断
if(!q.empty()) {
    int x = q.front();
}

// BFS模板
queue<int> q;
q.push(start);
while(!q.empty()) {
    int cur = q.front();
    q.pop();
    // 处理cur
}

3. priority_queue默认是大顶堆

xxxxxxxxxx
priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);

cout << pq.top() << endl;  // 4（最大值）

// 小顶堆（最小值在顶部）
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(3);
pq.push(1);
pq.push(4);

cout << pq.top() << endl;  // 1（最小值）

4. 自定义优先队列比较

xxxxxxxxxx
// 对pair的优先队列
priority_queue<pair<int, int>> pq;  // 默认按first降序，first相同按second降序

// 自定义结构体
struct Node {
    int val, idx;
    
    // ❌ 错误：operator<的含义是"小于"
    bool operator < (const Node& other) const {
        return val < other.val;  // 这样会变成大顶堆！
    }
};

// ✅ 正确：要小顶堆，需要反向比较
struct Node {
    int val, idx;
    
    bool operator < (const Node& other) const {
        return val > other.val;  // 小顶堆
    }
};

priority_queue<Node> pq;

// 或使用lambda（C++11）
auto cmp = [](Node& a, Node& b) {
    return a.val > b.val;  // 小顶堆
};
priority_queue<Node, vector<Node>, decltype(cmp)> pq(cmp);

5. deque的效率问题

xxxxxxxxxx
// deque支持随机访问，但比vector慢
deque<int> dq;
vector<int> v;

// 频繁随机访问：vector更快
for(int i = 0; i < n; i++) {
    v[i] = i;  // 快
    dq[i] = i; // 慢
}

// 频繁头部插入：deque更快
for(int i = 0; i < n; i++) {
    dq.push_front(i);  // O(1)
    v.insert(v.begin(), i);  // O(n)
}

// 使用场景：
// - 只需要尾部操作 → vector
// - 需要头尾操作 → deque
// - 需要中间插入删除 → list

6. 优先队列不支持遍历

xxxxxxxxxx
priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);

// ❌ 错误：不能直接遍历
for(int x : pq) {  // 编译错误！
    cout << x;
}

// ✅ 正确：逐个取出（会清空队列）
while(!pq.empty()) {
    cout << pq.top() << " ";
    pq.pop();
}

// 如果需要保留，先复制
priority_queue<int> pq_copy = pq;
while(!pq_copy.empty()) {
    cout << pq_copy.top() << " ";
    pq_copy.pop();
}

7. 单调队列的实现

xxxxxxxxxx
// 滑动窗口最大值
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;  // 存下标，保持递减
    vector<int> res;
    
    for(int i = 0; i < nums.size(); i++) {
        // 移除窗口外的元素
        while(!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();
        }
        
        // 维护单调性（递减）
        while(!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }
        
        dq.push_back(i);
        
        // 窗口形成后记录答案
        if(i >= k - 1) {
            res.push_back(nums[dq.front()]);
        }
    }
    return res;
}

栈 stack

是什么

后进先出（LIFO）的数据结构，常用于括号匹配、表达式求值、DFS等场景。

怎么用

xxxxxxxxxx
#include <stack>
using namespace std;

stack<int> stk;

stk.push(x);      // 入栈
stk.pop();        // 出栈（无返回值）
stk.top();        // 获取栈顶元素
stk.empty();      // 是否为空
stk.size();       // 栈大小

// 典型用法
while(!stk.empty()) {
    int x = stk.top();
    stk.pop();
    // 处理x
}

为什么用

• 括号匹配问题

• 表达式求值（中缀转后缀）

• 单调栈（找下一个更大/更小元素）

• DFS的迭代实现

• 函数调用栈的模拟

常见陷阱与注意事项

1. pop()没有返回值

xxxxxxxxxx
stack<int> stk;
stk.push(1);
stk.push(2);

// ❌ 错误：pop()不返回值
int x = stk.pop();  // 编译错误！

// ✅ 正确：先top()再pop()
int x = stk.top();
stk.pop();

2. 访问空栈导致未定义行为

xxxxxxxxxx
stack<int> stk;

// ❌ 错误：空栈调用top()
int x = stk.top();  // 未定义行为！

// ✅ 正确：先判断
if(!stk.empty()) {
    int x = stk.top();
}

3. 栈不支持遍历

xxxxxxxxxx
stack<int> stk;
stk.push(1);
stk.push(2);
stk.push(3);

// ❌ 错误：不能直接遍历
for(int x : stk) {  // 编译错误！
    cout << x;
}

// ✅ 正确：逐个取出（会清空栈）
while(!stk.empty()) {
    cout << stk.top() << " ";
    stk.pop();
}

// 如果需要保留，先复制
stack<int> stk_copy = stk;
while(!stk_copy.empty()) {
    cout << stk_copy.top() << " ";
    stk_copy.pop();
}

4. 括号匹配问题

xxxxxxxxxx
bool isValid(string s) {
    stack<char> stk;
    
    for(char c : s) {
        if(c == '(' || c == '[' || c == '{') {
            stk.push(c);
        } else {
            // ❌ 错误：没有检查栈是否为空
            // char top = stk.top();
            
            // ✅ 正确：先判断
            if(stk.empty()) return false;
            
            char top = stk.top();
            stk.pop();
            
            if(c == ')' && top != '(') return false;
            if(c == ']' && top != '[') return false;
            if(c == '}' && top != '{') return false;
        }
    }
    
    return stk.empty();  // 栈必须为空
}