快速入门
简介
INFO
为了能够快速看懂现代C++代码, 遂本文。
开变量
auto a = std::vector(n,0);开了一个
n个大小初始化为0的vector。
lambda表达式
Lambda 表达式实则是快速地编写一个函数，语法可见下文。
void f(int y)
{
int x = 1 + y;
return x;
}
auto main() -> int
{
auto f2 = [](int y) -> void { // 这是一个lambda表达式 原名为闭包*函数*
int x = 1 + y;
return x;
}; // 注意分号
auto ret = f(10);
ret = f2(10); // 等价！！！
}从这段代码可以看出 Lambda 的语法，以 [] 起手，返回值用 -> 指定。
Lambda 优势之一：减少传参
void f_plus1(std::vector& vec,int i,int v1)
{
vec[i] += v1;
return;
}
auto main() -> int
{
auto vec = std::vector{ 1,2,3,4,5,6 };
auto lam_plus1 = [&](int i,int v1) -> void {
vec[i] + v1; // 不用传vec了 因为在他*上方*的vec被捕获了
};
f_plus1(vec,0,10); // vec[0] += 10
lam_plus1(0,10); // vec[0] += 10
}只要对 [] 里加一个 &，Lambda 就能使用在其上方声明的任何局部变量，这是一个优势。
Lambda 优势之二：调用 STL 函数
这里以 std::sort 为例, 下面每个代码都假设我有这样的一个 std::vector a;
auto a = std::vector{ 1,2,3,4,5,6,7,8 };std::sort(a.begin(),a.end(),std::less{}); // 按升序排序a
std::sort(a.begin(),a.end()); // 按升序排序a 默认行为
std::sort(a.begin(),a.end(),std::greater{}) // 按降序排序上面对 int 排序很简单，如果是结构体呢？
假设我有这么一个结构体，我要求排序结果为
- 先x为升序
- x一样 则y为降序
那么我们可以用 Lambda 解决这个问题。
struct node
{
int x; // 升序
int y; // 降序
};
auto main() -> int
{
auto a = std::vector<node>(10); // 开一个大小为10的<node> vector
// 注意我的lambda
auto cmp = [](node lhs,node rhs) -> bool {
if(lhs.x == rhs.x) {
return std::greater{}(lhs.y,rhs.y); // 按 y 降序
// 注意花括号不要省，因为在上一个int示例，传给sort的也有{}
}
return std::less{}(lhs.x,rhs.x); // 按 x 升序
};
std::sort(a.begin(),a.end(),cmp); // 如此 便完成结构体排序
// 如果您喜欢 您当然可以这么写
std::sort(a.begin(),a.end(),[](node lhs,node rhs) -> bool {
if(lhs.x == rhs.x) {
return std::greater{}(lhs.y,rhs.y); // 按 y 降序
// 注意花括号不要省，因为在上一个int示例，传给sort的也有{}
}
return std::less{}(lhs.x,rhs.x); // 按 x 升序
});
}范围
拥有 .begin() 和 .end() 的都可以抽象为一个范围，并被应用于范围 for。
假设一个 std::vector = { 1,5,6,7,8,2,0 }
我们知道 std::vector 是有 .begin() 和 .end() 的，那么它就可以被应用于范围 for。
auto a = std::vector{ 1,5,6,7,8,2,0 };
for(auto v : a) {
std::cout << v << ' ';
}
// 打印结果就是 1 5 6 7 8 2 0
// 这段代码用到了基于范围的for循环C++ 拥有特别多的构造范围的函数。
以下对函数的描述都经过简化。
std::views::iota
using namespace std::views;
范围 iota(int x,int y); // 构造一个范围 [x,y)
// 实质上 iota不要求参数类型相同，也不要求必须是int
// 但最常用的还是两个int
for(auto i : iota(0,10)) { // for(int i = 0; i < 10; ++i)
std::cout << i << ' ';
// 打印 0 1 2 3 4 5 6 7 8 9
}管道运算符与take
C++ 同样有对范围加工的函数，比如 take。 加工方式是管道运算符 |。
using namespace std::views;
for(auto i : iota(0,10) | take(4)) {
std::cout << i << ' ';
// 打印 0 1 2 3
}
for(auto i : iota(0,4) | reverse) {
std::cout << i << '\n';
// 打印 3 2 1 0
}:::note 不要忘了 iota 是左闭右开 :::
map的范围与结构化绑定
C++ 支持对 pair 和 struct 的结构化绑定。
struct node
{
int x,y;
};
using side = std::pair<int,int>;
auto main() -> int
{
node z{ 1,2 };
side y{ 3,4 };
auto [x1,y1] = z;
auto [x2,y2] = y;
// 其实就是很方便的解包一个元组 使得我们不用 x.啥 x.啥的访问
}容易得知, map 依赖于一个 std::pair, 那么遍历 map 则可以用：
auto map = std::map<int,int>{};
map.emplace(1,2);
map.emplace(2,3);
map.emplace(3,4);
map.emplace(4,5);
map.emplace(5,6);
for(auto [x,y] : map) {
std::cout << x << ' ' << y << '\n';
// 输出
// 1 2
// 2 3
// 3 4
// 4 5
// 5 6
}ranges函数
ranges 函数实则是非 ranges 函数的包装。
比如以下方式都是等价的：
auto a = std::vector{ 1,2,3,4,5,6 };
std::ranges::sort(a);
std::sort(a.begin(),a.end());
std::ranges::unique(a);
std::unique(a.begin(),a.end());std::vector的范围构造函数
std::vector 其实很低版本的 C++ 就有范围构造函数了，所以接口很旧，需要传两个迭代器。
auto r = iota(0,5);
auto a = std::vector(r.begin(),r.end());
// a是 { 0,1,2,3,4 }ranges函数的proj接口
INFO
任何 std::ranges::func 都是对 std::func 的加强补丁版本, C++为了历史兼容, 不得不把新函数放入 std::ranges, 但是名字都是相同的.
ranges 函数都有额外一个 proj 函数, 投影。
我们用这个案例来理解投影：一个结构体，只对 x 排序。
struct node
{
int x;
int y;
};
auto main() -> int
{
std::vector<node> a(1000);
auto proj = [&](node v) {
return v.x;
}
std::ranges::sort(a,std::less{},proj);
// 他等同于对结构体排序，但是内部的sort只会把每个结构体v 投影为v.x 来进行std::less比较
// 最终效果就是 按x升序排序了这个结构体
}当然，你可以继续保持内联写法。
你会发现 proj 有时候没有必要，同样也可以内联到 cmp 里。
std::vector<node> a(1000);
auto cmp = [](node lhs,node rhs) -> bool {
return std::less{}(lhs.x, rhs.x);
};
std::ranges::sort(a,cmp);
// 同样可以仅对结构体中仅按x排序当然，proj 最初的引入就是为了方便，仅此而已。
至此，范围告一段落，让我们正式进入二分。
任何二分都可以转化为std::ranges::lower_bound
:::caution 本文章假设你了解 <algorithm> 的 std::lower_bound 函数...算了不假设了. :::
std::lower_bound 这种过时的就不讲了，直接 std::ranges::lower_bound。
std::ranges::lower_bound函数机制
它的伪码函数声明如下：
迭代器 std::ranges::lower_bound(范围, 查找值, cmp, proj)它的调用结果是, 返回序列里第一个大于等于查找值的迭代器。
如果你希望在一个序列里进行二分查找, 它的要求条件是：这个范围已经用同样的 cmp 和 proj 排过序了。
例子
auto main() -> int
{
auto a = std::vector<int>(1000);
scan(a); // 假设对a进行了某种输入
auto it = std::ranges::lower_bound(a,10); // 在vector a里 二分查找10
// 返回的it是一个迭代器 需要经过*解引用获取值
auto v = *it; // v是一个int 值为10 (如果找到了) 如果没找到则为范围的.end(), 本例是a.end()
}但是不幸的是，上面的结果是错误的，我们都知道，要二分必须有序。
auto main() -> int
{
auto a = std::vector<int>(1000);
scan(a);
std::ranges::sort(a,某个cmp,某个proj);
// 先排序才行！
auto it = std::ranges::lower_bound(a,10,某个cmp,某个proj);
// 此时这个函数才可能正常工作
auto v = *it;
}需要注意的是, sort 与 lower_bound 的 cmp 与 proj 必须相同。
:::note 其实本质上只要满足范围对查找值有划分即可，为了方便理解才上面描述，但只要排序，就一定是个充分的不能再充分的排序，算法竞赛也一般都直接排序后二分，所以请放心。 :::
以上介绍了如何快速查找一个范围是否存在一个值（检查返回的迭代器是不是等于 范围.end()）。
下面我们来看看，任何二分如何被 lower_bound 取代。
auto l = 0,r = 100;
while(l != r) {
auto mid = (l + r) / 2;
if(咋了(mid)) {
r = mid;
} else {
l = mid + 1;
}
}这是一个二分的传统 C++ 写法模板, 任何二分题的核心就是那个 咋了 函数, 参数是 mid。
当然，二分的写法太多了，起码四种，所以不用拘泥于我上面给你写的不一样。
我为什么用 l != r, 其实 l < r 完全更好, 但我就是铤而走险，我知道 l 最后一定等于 r, 我的左闭右开区间写法是适配 != 的, 左闭右闭二分就不一定了。
下面来进行一个等价对比
// 注意我的二分区间是左闭右开 [l,r) 所以我的iota可以写传入(l,r)
auto l = 0,r = 100;
while(l != r) {
auto mid = (l + r) / 2;
if(咋了(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
等价于
auto l = 0,r = 100;
std::ranges::lower_bound(iota(l,r),true,std::less{},[&](auto mid) {
// 实现咋了函数
});不知道你们看出下面写法的咋了函数在哪儿了没有, 在, lower_bound的proj函数的位置！
我们知道可以二分的题对mid的取值的结果是单调的，且只有false,和true (当然特殊情况特殊对待)
proj意味投影，有没有可能 iota + proj 把一个范围变成了
[false,false,false,false,true,true,true,true,true]
而我做的行为是在二分找第一个true
没错，很多二分题的本质就是！
- 找第一个true
- 找最后一个false
- 找是否存在true
- 找最后一个true
- 找第一个false
根据上面的任何题，其实抽象为lower_bound 在写那五个二分题会更加清晰好写
无非是 iota | reverse 与 lower_bound和upper_bound 的各种组合
因为那五个条件, 对应了手写二分的五种写法, 你写法稍微错了二分就容易越界, 当然lower_bound用错了也一样
但你只要理解了 lower_bound 一样可以取代任何二分！
好了，本次的快速入门暂时到此结束。