C++11在算法竞赛中常用语法特征/语法糖

简要总结本人在算法竞赛中遇到的C++11的常用特征/语法糖，内容不会很全。

初始化列表

引入了initializer_list ，使用{}的初始化方式称为适用于任何对象初始化的场景。

struct Foo {
	int a;
	string s;
};
void solve() {
	Foo a({3, "dkfjlkdf"});
}

struct Foo {
	int a;
	string s;
};
void solve() {
	vector<Foo> a;
	for(int i = 0; i < 10; ++i) a.push_back({i, "abd"});
}

搜索算法中四个方向：

vector<int> fx({0,0,1,-1}), fy({1,-1,0,0});

C++11中，max和min函数支持使用初始化列表：

	int a = 3,b = 4, c = 5;
	int ma = max({a,b,c}), mi = min({a,b,c});
	cout<<ma<<" "<<mi<<endl;

对() 和 {} 关系有疑惑，可以看此博客：[C++ () 和 {} 区别](C++ () 和 {} 区别-CSDN博客)

range-for

基于范围的for循环(range-for)是C++11新引入的特征，可遍历各种序列结构的容器（如数组、vector、list等）；每次循环都会将序列中的下一个元素，赋值给声明的变量，直到循环结束。

	int arr[] = {1,2,3,4,5};
	for(int &v: arr) cout<<v<<endl;
	vector<int> vec({1,2,3,4,5});
	for(int &v: vec) cout<<v<<endl;

使用&表示引用，可以对其进行更改，如果没有带&，则只是在这个范围内进行更改，但是当退出该范围内时，值没有进行更改。

	vector<int> vec({1,2,3,4,5});
	for(int v: vec) v=3,cout<<v<<endl;
	for(int v: vec) cout<<v<<endl;

常用于从下标0开始读入数据，注意要用引入**&**。

	int n = 100;
	vector<int> a(n);
	for(int i = 0; i < n; ++i) cin>>a[i];

	vector<int> b(n);
	for(int &t: b) cin>>t;

auto

C++11中用auto关键字来支持自动类型推导，C++11之前也有auto，但是由于过于偏僻，之前的被抛弃。

可以通过=右边的类型推导出变量的类型，前提是定义一个变量时对其进行初始化。

	vector<int> a(100);
	int b = 3;
	auto aa = a;
	auto bb = b;

跟范围for循环结合：

	vector<int> b(n);
	for(auto &t: b) cin>>t;

在使用容器套容器时，尽量用引用的方式，否则深拷贝代价太大。

	map<int,vector<int>> mp;
	mp[3] = vector<int>(1024);
	auto& vec = mp[3];

lambda表达式

C++11 引入了 Lambda 表达式，Lambda 表达式是一种匿名函数，可以在需要函数的地方定义并使用它，而无需显式命名函数。

使用lambda表达式可以在主函数或者solve函数内一气呵成。当操作内容不是全局变量时，用lambda表达式写个简单仿函数处理信息很方便。

[capture list](parameters) -> return_type {
    // 函数体
}

• capture list：捕获列表，有值传递和引用传递，表示函数体内使用的变量，非函数参数。
• parameters：仿函数参数，与函数类似。
• return_type：返回值。

	auto add = [&](int a, int b) -> int {
	return a + b; 
	};
	cout<<add(3,3); 

在C++11中，用lambda表达式实现递归需要用function，需要带上<functional>头文件。

    function<int(int)> fib = [&fib] (int n) {
        if(n <= 2) return 1;
        else return fib(n-1) + fib(n-2);
    };
	cout<<fib(5);

C++14lambda表达式性能可以，且实现递归会更加方便。在C++11中，lambda实现的递归有性能缺陷。

C++ lambda表达式函数递归调用简单写法实现-CSDN博客

常用函数

可能有些在C++11之前就已经存在了，由于在算法中比较常用，一并再次介绍。

<algorithm>库

二分

lower_bound(bg, ed, val)和upper_bound(bg, ed, val)。

lower_bound用于查找容器中大于等于某值的数，返回这个值的迭代器/指针。
upper_bound用于查找容器中大于某值的数，返回这个值的迭代器/指针。

在set中或者其他容器，有自己的lower_bound和upper_bound实现，就用自己的，否则花销极大。

例如：set s; s.lower_bound(...) ; lower_bound(s.begin(), s.end(), ..)。

最大值、最小值

min_element(bg, ed)，max_element(bg, ed)，返回相应迭代器或指针。

	vector<int> a({3,1,3434});
	int ma = *max_element(a.begin(), a.end()), mi = *min_element(a.begin(), a.end());

记数

count(bg, ed, val)，返回在$[bg,ed)$范围内有多个值为$val$的。

	vector<int> a({3,1,3434});
	int cnt = count(a.begin(), a.end(), 1);

翻转

reverse(bg, ed)，将$[bg,ed)$范围内的值进行翻转。

	vector<int> a({3,1,3434});
	reverse(a.begin(), a.end());

去重

unique(bg, ed)，将$[bg,ed)$范围内的元素进行去重并返回最后的迭代器。这个去重不是将重复的删除，而是移到后面。

删除

erase(bg, ed)，将$[bg, ed)内的元素进行删除。

利用排序，去重，删除，二分进行离散化。

		vector<int> a,id,last; id.assign(a.begin(), a.end());
        sort(id.begin(), id.end());
        id.erase(unique(id.begin(), id.end()), id.end());
        for(int i = 0; i < n; ++i) {
            last[i] = lower_bound(id.begin(), id.end(),a[i]) - id.begin();
        }

是否排序

is_sorted(bg, ed, comp)。

	vector<int> a({3,1,3434});
	if(is_sorted(a.begin(), a.end())) puts("YES");
	else puts("NO");

填充

使用fill(bg, ed, val)。

	vector<int> a({3,1,3434});
	fill(a.begin(), a.end(), -1);

第k大（

nth_element(bg, md, ed)，将$[bg,ed)$中的内容重新分配，小于等于$md$的元素在$[bg,md)$。

乱序

random_shuffle(bg, ed)，将$[bg,ed)$内的元素打乱。

	vector<int> a({3,1,3434});
	random_shuffle(a.begin(), a.end());

全排列

next_permutation(bg, ed)，按字典序从小到大，到最后一个时返回0。也可以处理组合。好像现在用处不大了，或许是写个排列是基础吧（

整体转换

transform(bg1, ed1, bg2, func)，将$[bg1,ed1)$范围的执行$func$函数后从$bg2$开始进行存入。常用于字符串全转为大写或者小写。

    string str;
    // 全部转换为大写字母
    transform(str.begin(), str.end(),str.begin(), ::toupper);
    // 全部转换为小写字母
    transform(str.begin(), str.end(), str.begin(), ::tolower);

旋转

rotate*bg, md, ed)，将$[bg,md)$范围内的值平移到$[md,ed)$后面。

	vector<int> a({3,1,3434});
	rotate(a.begin(), a.begin() + 1, a.end());
	for(auto &t: a) cout<<t<<" "; puts("");
	// 1 3434 3   左移

<numeric>库

累加

accumulate(bg, ed, val)，将$[bg,ed)$范围内的值与初始值$val$进行相加返回这个和。

	vector<int> a({3,1,3434});
	int sum = accumulate(a.begin(), a.end(), 0LL);

iota

iota(bg, ed, val)，表示将$[bg,ed)$范围按$val$累加。常用于并查集的初始化。

	vector<int> a({3,1,3434});
	iota(a.begin(), a.end(), 0); // 0 1 2

GNU

__lg()

__lg(x)，返回$?lo{g}_2(x)?$，时间复杂度是$O(1)$。

__gcd(x, y)

返回最大公约数。

<cmath>库

计算两点间距离

hypot(x, y)，用于计算$\sqrt{ x^2 + y^2} $，或者$ \sqrt { x^2 + y^2 + z^2 }$。

NAN,INFINITY

由编译器实现，一般NAN是0，INFINITY是基本数据类型的最大值。

Range-based for loop (since C++11) - cppreference.com

从 C++98 到 C++20，寻觅甜甜的语法糖们 - Acc_Robin 的博客 - 洛谷博客 (luogu.com.cn)

C++11新特性（全详解） - 知乎 (zhihu.com)