标准库
#include<bits/stdc++.h>
万能头
是一个简写方式,用来一次性包含 C++ 标准库中的许多常用部分,比如输入输出流(iostream
)、算法(algorithm
)、向量(vector
)、列表(list
)、队列(queue
)、栈(stack
)、映射(map
)、集合(set
)等。使用它可以让程序员在编写解决特定问题的代码时,不必一一列出所需的所有头文件,简化了代码的编写过程。
在实际的工程项目或更专业的编程实践中,直接使用 #include<bits/stdc++.h>
并不被推荐,主要原因有:
- 非标准: 这个头文件不是 C++ 标准库的一部分,因此在不同的编译器或平台上可能不可用。
- 编译时间: 包含这个头文件可能会增加编译时间,因为它包含了大量你可能并不需要的功能。
- 可读性和可维护性: 明确列出所需的头文件可以提高代码的可读性和可维护性,让其他阅读代码的人更容易理解程序的结构和依赖。
#include<cmath>
基本运算
abs(x)
:返回x的绝对值,适用于整数、浮点数等。sqrt(x)
:返回x的平方根,x应为非负数。
幂与对数
pow(base, exponent)
:计算base的exponent次幂。exp(x)
:返回e的x次幂,其中e是自然对数的底数(约等于2.71828)。log(x)
:返回x的自然对数(以e为底)。log10(x)
:返回x的常用对数(以10为底)。
三角函数
sin(x)
:返回x弧度的正弦值。cos(x)
:返回x弧度的余弦值。tan(x)
:返回x弧度的正切值。- 以上每个函数都有对应的反三角函数,如
asin
,acos
,atan
等,以及它们的逆函数(如atan2(y, x)
)。
取整函数
floor(x)
:返回小于或等于x的最大整数。ceil(x)
:返回大于或等于x的最小整数。round(x)
:四舍五入到最近的整数。trunc(x)
:返回x去掉小数部分后的整数部分。
其他常用函数
fabs(x)
:返回x的浮点绝对值。fmod(x, y)
:返回x除以y的浮点余数。modf(x, &intpart)
:将x分解为整数和小数部分,整数部分存储在intpart
指针指向的位置,返回小数部分。max(a, b)
和min(a, b)
:分别返回两个数中的最大值和最小值。
ceil(向上取余)
ceil
是一个数学函数,全称为 “ceiling”,意为“天花板”。在C++标准库中的 <cmath>
头文件被定义。这个函数接受一个浮点数作为参数,返回大于或等于该数的最小整数。
ceil(3.2)
返回 4
ceil(4.0)
返回 4
ceil(-3.2)
返回 -3
ceil(-3.8)
返回 -3
pow
pow
函数的返回值类型通常是double
,表示计算结果。
如果要输出其他类型要进行强制转化
- 当基数(base)为正数或零,且指数(exponent)为任意实数时,
pow
返回基数的指数次幂的值。 - 当基数为负数且指数为非整数时,结果是复数(但这在C++标准库的
pow
函数中通常不直接支持,需要特殊的复数库处理)。 - 当基数为负数且指数为整数时,结果遵循算术规则,例如
pow(-2, 3)
返回-8。 - 如果指数为零,无论基数为何值(除了
pow(0, 0)
,这在数学上是不确定的形式,但在许多实现中会返回1),结果都是1。 - 如果基数为0且指数为负数,则结果是正无穷大,表示一个无效的数学操作(除以0的情况)。
#include<cctype>
#include 是C++标准库中的一个头文件,它包含了用于处理字符分类和转换的功能函数。
这个头文件定义了一系列测试字符类型和转换字符的函数,这些函数对于文本处理和验证输入非常有用。以下是一些常用的函数示例:
isalnum(c)
: 判断字符c是否为字母或数字。isalpha(c)
: 判断字符c是否为字母。isdigit(c)
: 判断字符c是否为数字。islower(c)
: 判断字符c是否为小写字母。isupper(c)
: 判断字符c是否为大写字母。isspace(c)
: 判断字符c是否为空白字符(如空格、换行、制表符等)。ispunct(c)
: 判断字符c是否为标点符号。tolower(c)
: 将字符c转换为小写形式(如果可能)。toupper(c)
: 将字符c转换为大写形式(如果可能)。
函数的返回值为bool类型
#include<algorithm>
C++ 标准库中的 头文件包含了一系列非常有用的算法函数,这些函数可以用于处理容器(如向量、列表、数组等)中的元素。这些算法可以极大地简化编程任务,使代码更加简洁和易于理解。
交换算法
swap()
用于交换两个对象的内容
#include <iostream>
#include <algorithm> // 包含swap模板函数int main() {int x = 10, y = 20;std::swap(x, y); // 交换x和y的值std::cout << "x = " << x << ", y = " << y << std::endl; // 输出:x = 20, y = 10return 0;
}
class MyClass {
public:// ... 其他成员函数和数据成员 ...// 重载 swap 成员函数friend void swap(MyClass& a, MyClass& b) noexcept {using std::swap; // 确保正确交换内部成员swap(a.member1, b.member1);swap(a.member2, b.member2);// ... 交换其他成员 ...}
};
reverse()
翻转容器里的元素
#include <algorithm>
#include <vector>
#include <iostream>int main() {std::vector<int> vec = {1, 2, 3, 4, 5};// 使用 reverse 函数反转容器中的元素std::reverse(vec.begin(), vec.end());// 打印反转后的容器for(int num : vec) {std::cout << num << " ";}std::cout << std::endl; // 输出: 5 4 3 2 1return 0;
}
注意事项
reverse
不会创建容器或数组的副本,而是直接修改原容器。- 该函数适用于各种标准库容器,如
std::vector
,std::list
,std::array
等,以及原始数组。 - 对于双向迭代器支持的容器(如
std::vector
,std::list
),reverse
可以正常工作。对于只支持单向迭代器的容器(如std::forward_list
),则无法直接使用reverse
,因为需要反向迭代的能力。
排序算法:
sort
std::sort(first, last): 对范围 [first, last) 内的元素进行排序。
它提供了高效、灵活的排序功能,支持自定义排序规则,并且默认实现的是快速排序算法,但在不同的标准库实现中可能会有所不同,有的实现可能会根据数据规模选择最适合的排序算法(例如,对于小数据集可能使用插入排序)。
#include <algorithm>
#include <vector>
#include <iostream>int main() {std::vector<int> vec = {5, 2, 4, 6, 1, 3};// 对整个向量进行升序排序std::sort(vec.begin(), vec.end());// 打印排序后的向量for(int num : vec) {std::cout << num << " ";}std::cout << std::endl;return 0;
}
自定义排序
如果你需要根据元素的特定条件进行排序,可以提供一个比较函数作为第三个参数给 sort
函数。这个比较函数应该接受两个参数并返回一个 bool
值,指示第一个参数是否应该排在第二个参数之前。
bool compare(int a, int b) {return a > b; // 降序排序
}int main() {std::vector<int> vec = {5, 2, 4, 6, 1, 3};// 使用自定义比较函数进行降序排序std::sort(vec.begin(), vec.end(), compare);// 打印排序后的向量for(int num : vec) {std::cout << num << " ";}std::cout << std::endl;return 0;
}
Lambda 表达式
C++11 引入了lambda表达式,使得自定义排序规则更加简洁。
int main() {std::vector<int> vec = {5, 2, 4, 6, 1, 3};// 使用Lambda表达式进行降序排序std::sort(vec.begin(), vec.end(), [](int a, int b){ return a > b; });// 打印排序后的向量for(int num : vec) {std::cout << num << " ";}std::cout << std::endl;return 0;
}
sort
函数的时间复杂度平均为 O(nlog n),在最坏情况下也是 O(nlogn),其中 n 是容器中元素的数量。由于它使用了高效的排序算法,因此在处理大量数据时表现优秀。
std::stable_sort(first, last): 稳定排序,即保持等价元素的相对顺序。
std::partial_sort(first, middle, last): 对范围 [first, last) 内的元素进行部分排序,使得前 middle - first 个元素是整个范围内的最小元素。
全排序
next_permutation
功能:生成当前排列的下一个字典序排列。如果当前排列已经是最大的(即按字典序排列的最大值),则函数返回 false
,并且不改变原序列。
示例:
std::vector<int> vec = {1, 2, 3};
while(std::next_permutation(vec.begin(), vec.end())) {for(int num : vec) std::cout << num << " ";std::cout << std::endl;
}
这段代码会输出 1, 2, 3
的所有后续排列,直到达到最大排列 3, 2, 1
,之后停止。
prev_permutation
功能:生成当前排列的上一个字典序排列。如果当前排列已经是最小的(即按字典序排列的最小值),则函数返回 false
,并且不改变原序列。
示例:
std::vector<int> vec = {3, 2, 1};
while(std::prev_permutation(vec.begin(), vec.end())) {for(int num : vec) std::cout << num << " ";std::cout << std::endl;
}
这段代码会输出 3, 2, 1
的所有前序排列,直到达到最小排列 1, 2, 3
,之后停止。
工作原理简述
-
next_permutation:从序列的末尾开始,找到第一对相邻元素
i, i+1
使得vec[i] < vec[i+1]
。如果找不到这样的对,说明当前排列已经是最大的,返回false
。找到了这样的对之后,在序列vec[i+1:end]
中找到第一个大于vec[i]
的元素vec[j]
,交换vec[i]
和vec[j]
,然后反转vec[i+1:end]
的顺序。 -
prev_permutation:工作原理与
next_permutation
相似,但方向相反。它从序列的末尾开始,寻找第一对相邻元素i, i+1
使得vec[i] > vec[i+1]
。找到这对元素后,在vec[begin:i]
中找到第一个小于vec[i]
的元素vec[k]
,交换vec[i]
和vec[k]
,然后反转vec[i+1:end]
的顺序。next_permutation
和prev_permutation
函数的返回值都是布尔类型 (bool
)。
查找算法:
std::find(first, last, value): 在范围 [first, last) 内查找值为 value 的元素。
std::find_if(first, last, pred): 在范围 [first, last) 内查找满足谓词 pred 的第一个元素。
std::binary_search(first, last, value): 在已排序的范围 [first, last) 内进行二分查找。
lower_bound
std::lower_bound
函数在给定的排序区间 [first, last)
中查找第一个不小于(大于等于)给定值 val
的元素的位置。它返回一个迭代器,指向该元素或者位于该元素应该插入位置的迭代器。
如果所有元素都小于 val
,则返回 last
的迭代器。
template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );
upper_bound
std::upper_bound
函数则查找第一个大于给定值 val
的元素的位置。它返回一个迭代器,指向该元素或者位于该元素应该插入位置的迭代器。
如果所有元素都不大于 val
,则返回 last
的迭代器。
template< class ForwardIt, class T >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );
修改算法:
std::for_each(first, last, func): 对范围 [first, last) 内的每个元素执行函数 func。
std::transform(first1, last1, result, func): 将范围 [first1, last1) 内的每个元素通过函数 func 转换,并将结果存储在 result 指向的位置。
std::replace(first, last, old_value, new_value): 将范围 [first, last) 内所有值为 old_value 的元素替换为 new_value。
比较算法:
std::equal(first1, last1, first2): 检查两个范围 [first1, last1) 和 [first2, first2 + (last1 - first1)) 是否包含相同的元素。
std::lexicographical_compare(first1, last1, first2, last2): 按字典顺序比较两个范围。
集合算法:
std::set_union(first1, last1, first2, last2, result): 计算两个已排序范围的并集,并将结果存储在 result 指向的位置。
std::set_intersection(first1, last1, first2, last2, result): 计算两个已排序范围的交集。
std::set_difference(first1, last1, first2, last2, result): 计算第一个已排序范围与第二个已排序范围的差集。
std::set_symmetric_difference(first1, last1, first2, last2, result): 计算两个已排序范围的对称差集
分区算法:
std::partition(first, last, pred): 对范围 [first, last) 内的元素进行分区,使得谓词 pred 为真的元素都出现在为假的元素之前。
std::stable_partition(first, last, pred): 稳定分区,即保持等价元素的相对顺序。
最小/最大算法:
std::min/max():返回两个或多个参数中的最小值
#include <iostream>
#include <algorithm>int main() {int x = 10, y = 20;std::cout << "Min: " << std::min(x, y) << std::endl; // 输出 Min: 10// 使用初始化列表std::cout << "Min in list: " << std::min({30, 5, 15}) << std::endl; // 输出 Min in list: 5return 0;
}
std::min_element(first, last): 返回范围 [first, last) 内最小元素的迭代器。
std::max_element(first, last): 返回范围 [first, last) 内最大元素的迭代器。
std::minmax_element(first, last): 同时返回范围 [first, last) 内的最小和最大元素的迭代器。
std::ntr_element(first, last)
nth_element
是 C++ 标准库 <algorithm>
中的一个函数,它的功能是在未排序的序列中重新排列元素,使得某个特定的元素(按排序顺序定义的第 n 个元素)出现在它本来应该在的排序位置上,同时保证在这个元素之前的元素都不大于它,在这个元素之后的元素都不小于它。但是,nth_element
不保证序列中其他元素的顺序,它是一种部分排序算法,主要应用于需要快速访问第 n 小(或第 n 大)元素的场景,而不是完全排序整个序列。
基本用法
#include <algorithm>
#include <vector>
#include <iostream>int main() {std::vector<int> vec = {9, 1, 5, 3, 7, 6, 4, 8, 2};int n = 4; // 找到第4小的元素// 使用 nth_element 将第n小的元素放到它正确的位置上std::nth_element(vec.begin(), vec.begin() + n - 1, vec.end());// 输出结果,注意此时只有nth位置的元素确定了其排序位置std::cout << "The " << n << "th smallest element is: " << vec[n - 1] << std::endl;return 0;
}
在这个例子中,nth_element
会将第4小的元素放到序列中的第4个位置上,而序列中剩余元素的相对顺序可能会改变,但保证了前三个元素都不大于这个元素,且后面的所有元素都不小于这个元素。
参数说明
begin
:序列的起始迭代器。nth
:指向需要定位的第 n 个元素的迭代器。如果n
是0,则指向第一个元素;如果n
等于序列的大小,则指向序列的末尾迭代器。end
:序列的结束迭代器。
时间复杂度
nth_element
的平均时间复杂度为 O(N),其中 N 是序列中元素的数量,最坏情况下的时间复杂度为 O(N^2),但这种情况较为罕见。它在实践中通常比完整的排序算法更快,特别是在只需要找到序列中特定位置的元素时。
删除算法
std::remove和
std::remove_if
这两个函数用于重新排列容器中的元素,使得所有“不需要”的元素都被移动到容器的末尾,并返回一个指向新逻辑末尾(即最后一个“需要”的元素之后)的迭代器。但请注意,它们不会实际减少容器的大小;要减少大小,你需要使用容器的erase
成员函数。
#include <algorithm>
#include <vector> int main() { std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9}; // 移除所有偶数 auto new_end = std::remove_if(vec.begin(), vec.end(), [](int i) { return i % 2 == 0; }); // 现在vec包含{1, 3, 5, 7, 9, ?, ?, ?, ?},其中?是未定义的值 // 使用erase来真正删除这些元素 vec.erase(new_end, vec.end()); // 现在vec只包含{1, 3, 5, 7, 9}
}
std::stable_partition
虽然std::stable_partition
通常不直接用于删除操作,但它可以根据某个谓词重新排列元素,保持相等元素的相对顺序不变。这可以用于将满足条件的元素移动到容器的一侧,然后(如果需要)删除不满足条件的元素。
std::partition
类似于std::stable_partition
,但std::partition
不保证保持相等元素的相对顺序。它也可以用于根据谓词重新排列元素,但通常不是用于删除操作的首选方法。
std::unique
std::unique
用于去除相邻的重复元素,但它要求输入范围已经排序。它返回一个迭代器,指向去重后序列的末尾的下一个位置。然而,std::unique
并不真正删除元素;它只是通过覆盖来“删除”它们。要与std::unique
一起使用以实际删除元素,你需要确保你的容器已经排序,并且之后要使用erase
。
具体来说,std::unique
的工作流程如下:
- 输入要求:输入的序列必须是已经排序的。这是因为
std::unique
通过比较相邻元素来识别重复项,如果序列没有排序,那么它就无法正确地识别出哪些元素是重复的。 - 遍历序列:
std::unique
遍历输入的序列,一次比较两个相邻的元素。 - 处理重复元素:如果发现相邻的两个元素相等(即它们是重复的),
std::unique
就会将这两个元素中的后一个(或者说“第二个”)视为“不需要的”,并尝试通过将其位置上的值替换为一个在当前上下文中被认为是“未使用”或“未定义”的值来“删除”它。然而,实际上std::unique
并不显式地将这些元素的值设置为某个特定的占位符或默认值;相反,它通常只是简单地让这些元素保持其未初始化或已经被修改的状态,因此这些值在逻辑上是未定义的。 - 返回新逻辑序列的末尾:
std::unique
返回一个迭代器,该迭代器指向逻辑上新的、去重后序列的末尾的下一个位置。这意味着从序列的开始到这个返回的迭代器之间的元素是去重后的,而从这个返回的迭代器到序列末尾之间的元素(尽管它们的物理位置还在那里)在逻辑上被视为是“不需要的”或“被删除的”。 - 物理删除(如果需要):由于
std::unique
本身并不改变容器的大小,如果你想要物理地删除那些被逻辑上“删除”的元素,你需要使用容器的erase
成员函数,将std::unique
返回的迭代器作为起始点,将容器的end()
迭代器作为结束点,来删除这些元素。
#include<cstring>
memset()
memset
是C/C++语言中的一个函数,用于在内存块中填充特定的值。这个函数常用于初始化数组、结构体或其他内存区域,尤其是当需要将大量内存区域设置为零(即清零)时特别有效。memset
函数属于 <string.h>
或 <cstring>
头文件(C++ 中)。
void *memset(void *ptr, int value, size_t num);
ptr
:指向要填充的内存区域的指针。value
:要设置的值,会被转换为unsigned char
类型,因此实际上只能有效设置0-255之间的值到内存中。num
:要填充的字节数。