C++ 提供了丰富的算法函数库，主要通过头文件 <algorithm> 和 <numeric> 来提供常用的算法函数
1. 排序算法
sort
对范围内的元素进行排序，时间复杂度为 \((O (\frac{N}{logN}))\)。
sort(vec.begin(), vec.end());
sort (a.begin (), a.end ());//less<int>() //1 2 3 4 5
sort (a.begin (), a.end (), greater<int>()); //5 4 3 2 1
bool cmp (...)
{
...
}
sort (a.begin (), a.end (), cmp);
//lambda表达式
sort(a.begin(), a.end(), [](int x,int y){return x>y;} );
原本应该是这样的:
sort(a.begin(), a.end(), [](int x,int y) -> bool {return x>y;} );
//C++可以自动识别函数返回值得数据类型，所以可以简写
struct cri
{
int a, b, v;
bool operator<(const cri &x) const
{
return v < x.v;
}
} a[N];
sort (a + 1, a + n + 1);
struct cri
{
int a, b, v;
bool operator>(const cri &x) const
{
return v > x.v;
}
} a[N];
sort (a + 1, a + n + 1, greater<cri>());
stable_sort
稳定排序，保持相等元素的相对位置。
stable_sort(vec.begin(), vec.end());
partial_sort
对一部分元素排序。
将 begin 和 end 范围内的元素排序，使得 begin 到 begin+k 范围内的元素都比 begin+k 指向的元素小，begin+k 到 end 范围内的元素都比 begin+k 指向的元素大
partial_sort(vec.begin(), vec.begin() + k, vec.end(), cmp);
bool cmp(int a, int b)
{
return a > b;
}
int main()
{
vector<int> v = { 4, 2, 9, 1, 5 };
partial_sort(v.begin(), v.begin() + 3, v.end(), cmp);
for (int i : v)
cout << i << ' '; //95412
}
nth_element
对第 k 个位置的元素进行重排，使得它左边的所有元素都比它小，右边的都比它大。
函数只是把下标为 k 的元素放在了正确位置，对其它元素并没有排序，当然 k 左边元素都小于等于它，右边元素都大于等于它，所以可以利用这个函数快速定位某个元素
nth_element(vec.begin(), vec.begin() + k, vec.end(), cmp);
is_heap
判断范围是否是堆。
bool result = is_heap(vec.begin(), vec.end());
make_heap
将范围内的元素调整为堆。
make_heap(vec.begin(), vec.end());
push_heap
将新元素插入堆中（堆尾元素）。
vec.push_back(new_elem);
push_heap(vec.begin(), vec.end());
pop_heap
弹出堆顶元素。
pop_heap(vec.begin(), vec.end());
vec.pop_back(); // 删除堆顶
sort_heap
将堆排序。
sort_heap(vec.begin(), vec.end());
2. 查找算法
find
查找范围内第一个等于指定值的元素，返回迭代器。
auto it = std::find(vec.begin(), vec.end(), value);
binary_search
二分查找，前提是范围已排序。
bool found = binary_search(vec.begin(), vec.end(), value);
lower_bound
返回第一个大于等于某值的元素的迭代器，前提是范围已排序。
auto it = lower_bound(vec.begin(), vec.end(), value);
upper_bound
返回第一个大于某值的元素的迭代器，前提是范围已排序。
auto it = upper_bound(vec.begin(), vec.end(), value);
any_of
判断范围内是否至少有一个元素满足给定条件。
bool result = any_of(vec.begin(), vec.end(), [](int x) { return x > 10; });
all_of
判断范围内是否所有元素都满足给定条件。
bool result = all_of(vec.begin(), vec.end(), [](int x) { return x > 0; });
none_of
判断范围内是否没有任何元素满足给定条件。
bool result = none_of(vec.begin(), vec.end(), [](int x) { return x < 0; });
search
在一个范围中搜索另一个范围。
auto it = search(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());
search_n
搜索 n 个连续的等于某值的元素。
auto it = search_n(vec.begin(), vec.end(), 3, value);
find_end
在一个范围中查找另一个范围最后一次出现的位置。
auto it = find_end(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());
find_first_of
查找范围中第一次出现的等于另一个范围中任意元素的元素。
auto it = find_first_of(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());
3. 最大最小值算法
max
max({-1, 0, 1, 9})
max_element
返回范围内的最大元素的迭代器。
auto it = max_element(vec.begin(), vec.end());
min_element
返回范围内的最小元素的迭代器。
auto it = min_element(vec.begin(), vec.end());
minmax
同时返回两个值中的最小值和最大值（C++11 中引入）。
auto result = minmax(a, b);
minmax_element
同时返回范围内的最小和最大元素的迭代器。
auto result = std::minmax_element(vec.begin(), vec.end());
4. 变换与修改算法
reverse
反转范围内的元素。
reverse(vec.begin(), vec.end());
rotate
将范围内的元素循环移动。
rotate(vec.begin(), vec.begin() + k, vec.end());
next_permutation
生成字典序的下一个排列。
next_permutation(vec.begin(), vec.end());
prev_permutation
生成字典序的上一个排列。
prev_permutation(vec.begin(), vec.end());
is_permutation
判断两个范围是否为相同元素的不同排列。
bool result = is_permutation(vec1.begin(), vec1.end(), vec2.begin());
lexicographical_compare
按字典顺序比较两个范围，判断第一个范围是否小于第二个范围。
bool result = lexicographical_compare(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());
unique
删除相邻重复元素，返回不重复的最后一个元素的下一位地址。
auto it = unique(vec.begin(), vec.end());
5. 数学算法
__int 128
Int 类型范围约为 1 e 9，long long 的数据范围约为 1 e 18，如果题目的数据范围超过 long long 的限度 (例如 long long 乘 long long 时可能爆 long long)，就要考虑使用高精度。
这是 128 字节的数据类型，可以支持的数据范围大约在 2 的 127 次幂左右，不过由于该数据类型不在 C++ 标准中，所以只支持四则运算功能，无法直接用 cin, cout 进行输入输出（输入输出类似于 string 类型），想要使用 int 128 还需要抄一份输入输出的板子。
- 注意由于 int 128 的输入输出利用的是 getchar (), putchar () 等函数，因此使用 int 128 时不能关闭同步流。
__int128 read()
{
__int128 x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
void write(__int128 x)
{
if(x < 0)
{
putchar('-');
x = -x;
}
if(x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
accumulate
求和，定义在 <numeric> 头文件中。
#include <numeric>
accumulate(起始迭代器, 结束迭代器, 初始值, 自定义操作函数)
//计算数组中所有元素的和
int res = accumulate(arr.begin(), arr.end(), 0);
//计算数组中每个元素乘以3之后的和
int func(int acc, int num)
{
return acc + num * 3;
}
int res = accumulate(arr.begin(), arr.end(), 0, func);
//计算数组中所有元素的乘积
int res = accumulate(arr.begin(), arr.end(), 1, multiplies<int>());
//拼接字符串
vector<string> words{"this ", "is ", "a ", "sentence!"};
string init = "hello, ", res; //init表示字符串的初始值
res = accumulate(words.begin(), words.end(), init); // hello, this is a sentence!
partial_sum
计算部分和，并将结果存储到另一个范围中。
partial_sum(vec.begin(), vec.end(), result.begin());
exclusive_scan
(C++17): 计算前缀和，但不包含当前元素。
exclusive_scan(vec.begin(), vec.end(), result.begin(), 0);
inclusive_scan
(C++17): 计算前缀和，包含当前元素。
inclusive_scan(vec.begin(), vec.end(), result.begin());
gcd
计算两个数的最大公约数，C++17 中引入。
int result = gcd(a, b);
lcm
计算两个数的最小公倍数，C++17 中引入。
int result = lcm(a, b);
6. 集合操作
set_union
计算两个有序集合的并集。
vector<int> result;
set_union(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), inserter(result));
set_intersection
计算两个有序集合的交集。
vector<int> result;
set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), inserter(result));
set_difference
计算两个有序集合的差集。
vector<int> result;
set_difference(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), std::back_inserter(result));
set_symmetric_difference
计算两个有序集合的对称差集。
vector<int> result;
set_symmetric_difference(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), inserter(result));
merge
合并两个已排序的范围，结果也保持有序。
vector<int> result(vec1.size() + vec2.size());
merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());
Includes
判断一个有序集合是否包含另一个有序集合。
bool result = std::includes(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());
Inplace_merge
合并两个已排序的范围，使得整个范围也保持有序。通常用于在部分排序后合并数据。
inplace_merge(vec.begin(), vec_middle, vec.end());
7. 比较和查找相关的算法
equal
判断两个范围内的元素是否相等。
bool result = equal(vec1.begin(), vec1.end(), vec2.begin());
mismatch
找出两个范围之间第一个不相等的元素。
auto result = mismatch(vec1.begin(), vec1.end(), vec2.begin());
lexicographical_compare
字典序比较两个范围的元素。
bool result = lexicographical_compare(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());
is_sorted
判断范围内的元素是否已排序。
bool sorted = is_sorted(vec.begin(), vec.end());
is_sorted_until
返回指向第一个未排序元素的迭代器。
auto it = is_sorted_until(vec.begin(), vec.end());
is_partitioned
判断范围内的元素是否被划分为满足某个谓词和不满足谓词的两部分。
bool part = is_partitioned(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; });
8. 删除元素相关的算法
remove
删除等于某值的元素，将其移动到范围末尾并返回新范围的结束迭代器。需要结合 erase 完成删除操作。
auto new_end = remove(vec.begin(), vec.end(), value);
vec.erase(new_end, vec.end());
remove_if
删除满足条件的元素。
auto new_end = remove_if(vec.begin(), vec.end(), [](int x) { return x < 0; });
vec.erase(new_end, vec.end());
unique
移除连续的重复元素，只保留一个副本。
auto it = unique(vec.begin(), vec.end());
vec.erase(it, vec.end());
unique_copy
移除连续的重复元素，并将结果复制到另一个范围。
unique_copy(vec.begin(), vec.end(), result.begin());
9. 分区相关算法
partition
将范围内的元素按照谓词进行划分，满足谓词的元素移到前面，不满足的移到后面。
partition(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; });
stable_partition
与 partition 类似，但保证划分后各元素的相对顺序不变。
stable_partition(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; });
partition_copy
复制并分区，将满足条件的元素复制到一个范围，不满足条件的复制到另一个范围。
partition_copy(vec.begin(), vec.end(), even.begin(), odd.begin(), [](int x) { return x % 2 == 0; });
10. 聚合函数
adjacent_difference
计算相邻元素之间的差值，并将结果存储到另一个范围中，定义在 <numeric> 中。
adjacent_difference(vec.begin(), vec.end(), result.begin());
inner_product
计算两个范围的内积，定义在 <numeric> 中。
int result = inner_product(vec1.begin(), vec1.end(), vec2.begin(), 0);
partial_sum
计算部分和，定义在 <numeric> 中。
partial_sum(vec.begin(), vec.end(), result.begin());
iota
生成递增序列，定义在 <numeric> 中。
iota(vec.begin(), vec.end(), start_value);
#include <iostream>
#include <numeric> //iota头文件
using namespace std;
void func()
{
vector<int> v(10);
iota(v.begin(),v.end(),1);
vector<int>::iterator it = v.begin();
while(it != v.end())
{
cout<<*it++<<" ";
}
}
结果：
1 2 3 4 5 6 7 8 9 10
- 定义在 numeric 头文件中的 iota () 函数模板会用连续的 T 类型值填充序列。前两个参数是定义序列的正向迭代器，第三个参数是初始的 T 值。第三个指定的值会被保存到序列的第一个元素中。保存在第一个元素后的值是通过对前面的值运用自增运算符得到的。当然，这意味着 T 类型必须支持 operator++()。下面展示了如何生成一个有连续的浮点值元素的 vector 容器：
std::vector<double> data(9);
double initial {-4};
std::iota (std::begin (data) , std::end (data) , initial);
std::copy(std::begin(data), std::end(data),std::ostream_iterator<double>{std::cout<< std::fixed << std::setprecision(1), " "});
std::cout << std::endl;
// -4.0 -3.0 -2.0 -1.0 0.0 1.0 2.0 3.0 4.0
#include <iostream>
#include <numeric>
#include <list>
int main()
{
std::list<char> chars(4);
std::iota(chars.begin(), chars.end(), 'A');
for (const auto& ch : chars)
std::cout << ch << " ";
std::cout << std::endl;
return 0;
}
atoi ()
#include <stdlib.h>
int atoi(const char *str);
- 功能：atoi () 会扫描 str 字符串，跳过前面的空格字符，直到遇到数字或正负号才开始做转换，而遇到非数字或字符串结束符 (’\0’) 才结束转换，并将结果返回返回值。
- 参数：
str：待转换的字符串
【返回值】返回转换后的整型数；如果 str 不能转换成 int 或者 str 为空字符串，那么将返回 0
void func()
{
char str1[] = "-10";
int num1 = atoi(str1);
printf("num1 = %d\n", num1);
}
//结果：
num1 = -10
而 char str1[] = "abc-1100def";结果是： num1 = 0
11. 旋转与翻转相关的算法
rotate
将范围内的元素旋转，即左移或右移指定的元素个数。
rotate(vec.begin(), vec.begin() + 1, vec.end());
// 将 vec 的第一个元素移到最后，其他元素向前移动一位
rotate_copy
旋转范围内的元素，并将结果复制到另一个范围。
vector<int> result(vec.size());
rotate_copy(vec.begin(), vec.begin() + 1, vec.end(), result.begin());
reverse
反转范围内的元素顺序。
reverse(vec.begin(), vec.end());
reverse_copy
反转范围内的元素顺序，并将结果复制到另一个范围。
reverse_copy(vec.begin(), vec.end(), result.begin());
12. 移动与复制相关的算法
move
将一个范围内的元素移动到另一个范围（避免复制），常用于处理右值引用。
move(vec1.begin(), vec1.end(), vec2.begin());
move_backward
将一个范围内的元素移动到另一个范围，元素的顺序反向拷贝。
move_backward(vec1.begin(), vec1.end(), vec2.end());
copy
将一个范围的元素复制到另一个范围。
copy(vec1.begin(), vec1.end(), vec2.begin());
copy_if
将满足条件的元素从一个范围复制到另一个范围。
copy_if(vec.begin(), vec.end(), result.begin(), [](int x) { return x % 2 == 0; });
copy_backward
将范围内的元素逆序复制到另一个范围中。
copy_backward(vec1.begin(), vec1.end(), vec2.end());
13. 替换相关的算法
replace
将范围内等于某值的元素替换为新值。
replace(vec.begin(), vec.end(), old_value, new_value);
replace_if
将范围内满足条件的元素替换为新值。
replace_if(vec.begin(), vec.end(), [](int x) { return x < 0; }, 0);
replace_copy
将范围内的元素复制到另一个范围，并将等于某值的元素替换为新值。
replace_copy(vec.begin(), vec.end(), result.begin(), old_value, new_value);
replace_copy_if
复制并替换满足条件的元素。
replace_copy_if(vec.begin(), vec.end(), result.begin(), [](int x) { return x < 0; }, 0);
14. 填充与交换相关的算法
fill
用指定值填充范围内的元素。
fill(vec.begin(), vec.end(), value);
fill_n
用指定值填充指定数量的元素。
fill_n(vec.begin(), 5, value);
swap
交换两个变量的值。
swap(a, b);
swap_ranges
交换两个范围的元素。
swap_ranges(vec1.begin(), vec1.end(), vec2.begin());
15. 计算和统计相关的算法
count
统计范围内等于某个值的元素个数。
int cnt = count(vec.begin(), vec.end(), value);
count_if
统计范围内满足条件的元素个数。
int cnt = count_if(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; });
16.输入输出
printf
printf("%c", "\n "[i < n]);
//相当于:
if(i<n)
printf(" ");
else
printf("\n");
这段代码实际上是一种简洁的 C 风格技巧，利用三元运算符来根据条件选择打印的字符：
1. "\n "[i < n]
"\n "是一个字符串常量，其中包含了两个字符：\n（换行符）和一个空格字符' '。[i < n]是条件表达式i < n的结果，它是一个布尔值。如果i < n为真，则结果是 1；如果为假，则结果是 0。
在 C 语言中，布尔值 true 被视为整数 1，false 被视为整数 0。因此，"\n "[i < n] 这个表达式会返回 "\n " 字符串中的某个字符：
- 当
i < n为true时，"\n "[1]会返回空格字符' '。 - 当
i >= n时，"\n "[0]会返回换行符'\n'。
2. printf("%c", ...)
printf("%c", ...)用于输出一个字符。- 所以，根据条件
i < n的真假，printf("%c", "\n "[i < n]);会输出空格字符或换行符。
总结
这段代码会根据 i 和 n 的比较结果，决定输出空格还是换行符：
- 如果
i < n，输出空格' '； - 如果
i >= n，输出换行符'\n'。
sscanf
sscanf(const char *__source, const char *__format, ...)：从字符串 __source 里读取变量
比如 sscanf(str,"%d",&a)
1. sscanf 的基本用法
整型数转换
int year, month, day;
int converted = sscanf("20191103", "%04d%02d%02d", &year, &month, &day);
printf("converted=%d, year=%d, month=%d, day=%d/n", converted, year, month, day);
//输出结果：
converted=3, year=2019, month=11, day=03
"%04 d%02 d%02 d"是用来解析字符串的格式，%表示格式转换的开始，d 表示转换为一个整数，04 作为 d 的修饰，表示这是一个长度为 4 位的整数，不足 4 位时以 0 补齐。
例子返回结果等于 3，表示有 3 个数据成功转换，转换成功数目同时取决于被解析的字符串以及其转换格式，如果我们把例子中的格式改为"%04 d%02 d"，那么 sscanf 将只返回 2，day 的数值不会被 sscanf 更改。
浮点数转换
double longitude, latitude;
int converted = sscanf("113.123456789 31.123456789", "%lf %lf", &longitude, &latitude);
printf("converted=%d, longitude=%.9lf, latitude=%lf/n", converted, longitude, latitude);
//输出结果：
converted=2, longitude=113.123456789, latitude=31.123457
sscanf 的格式字符串中，f 表示这是一个浮点数，其修饰词 l 表示这是一个 double 的浮点数
2. sscanf 的高级用法
数字+字符串
char str[32] = "";
sscanf("123456abcdedf", "%31[0-9]", str);
printf("str=%s/n", str);
//输出结果：
str=123456
上面的格式中，[0-9] 表示这是一个仅包含 0-9 这几个字符的字符串，前面使用数字 31 修饰词表示这个字符串缓冲区的最大长度 (这也是 sscanf 最为人诟病的地方，很容易出现缓冲区溢出错误，实际上 sscanf 是可以避免出现缓冲区溢出的，只要在书写任何字符串解析的格式时，注意加上其缓冲区尺寸的限制)。
char str[32] = "";
sscanf("123456abcdedf", "%31[0-9a-z]", str);
printf("str=%s/n", str);
//输出结果：
str=123456abcdedf
在格式 [] 中增加了 a-z 的描述。
使用 ^ 示例：
char str[32] = "";
sscanf("123456abcdedf", "%31[^a-z]", str);
printf("str=%s/n", str);
//输出结果：
str=123456
在 [] 中增加表示相反的意思，上面的 [a-z] 表示一个不包含任何 a-z 之间的字符串
使用 * 示例：
char str[32] = "";
int ret = sscanf("123456abcdedf", "%*[0-9]%31[a-z]", str);
printf("ret=%d, str=%s/n",ret, str);
//输出结果：
ret=1, str=abcdedf
加上 * 修饰表示一个被忽略的数据，同时也不需要为它准备空间存放解析结果。如上面的例子中，我们就只使用了 str 一个参数存放 %31[a-z] 的解析结果，而 sscanf 也只返回 1，表示只解析了一个数据。
sprintf
sprintf(char *__stream, const char *__format, ...)：将 __format 字符串里的内容输出到 __stream 中，比如 sprintf(str,"%d",i)
17. 其它常用算法
for_each
对范围内的每个元素应用某个操作。
for_each(vec.begin(), vec.end(), [](int &x) { x += 1; });
transform
对范围内的元素进行变换，并将结果存储到另一个范围中。
transform(vec.begin(), vec.end(), result.begin(), [](int x) { return x * 2; });
clamp
将值限制在某个范围内（C++17 中引入）。
int result = std::clamp(value, min_value, max_value);
inplace_merge
合并两个已排序的相邻子范围，结果仍然有序。
inplace_merge(vec.begin(), middle, vec.end());
auto
- 如果在一个语句用 auto 声明了多个变量，则初始化这些变量的表达式都必须使对应声明的变量的类型一致
auto intVal=12,doubleVal=0.12; // 错误
//12是一个int类型的字面值常量，因此intVal判断出来的是int类型，而0.12是一个double类型的字面值常量，因此doubleVal推断出来的是double类型，两者推断的类型不一致，因此这条语句错误
for (auto a:b) 中 b 为一个容器，效果是利用 a 遍历并获得 b 容器中的每一个值，但是 a 无法影响到 b 容器中的元素
for (auto &a:b) 中加了引用符号，可以对容器中的内容进行赋值，即可通过对 a 赋值来做到容器 b 的内容填充
for (auto& [x, q] : mp)是一种基于范围的循环语法，常用于遍历 C++17 引入的结构化绑定语法
[x, q]：这是结构化绑定。map 的元素实际上是一个 pair<const Key, Value>，其中第一个元素是键（key），第二个元素是值（value）。[x, q] 将 pair 的键和值分别绑定到 x 和 q 上，允许我们更方便地访问键值对
fixed 和 setprecision
cout << fixed << setprecision(5) << x << endl;
__ builtin
位运算函数
//无符号整型(unsigned int / unsigned long / unsigned long long)
__builtin_ctz( ) / __buitlin_ctzl( ) / __buitlin_ctzll( ) // 返回括号内数的二进制表示数末尾0的个数
__buitlin_clz( ) / __buitlin_clzl( ) / __buitlin_clzll( ) // 返回括号内数的二进制表示数前导0的个数
__builtin_popcount( ) / __builtin_popcountl( ) / __builtin_popcountll( )// 返回括号内数的二进制表示数1的个数
__builtin_parity( ) / __builtin_parityl( ) / __builtin_parityll( )// 判断括号中数的二进制表示数1的个数的奇偶性(偶数返回0 , 奇数返回1)
//有符号整型(int / long / long long)
__builtin_ffs( ) / __builtin_ffsl( ) / __builtin_ffsll( ) // 返回括号中数的二进制表示数的最后一个1在第几位(从后往前算)
//其他
__builtin_sqrt( ) / __builtin_sqrtf( ) //快速开平方