算法竞赛中可能用得到的C++20新特性介绍

趋势为王

写在前面

时间飞逝，已经到了2023年了，C++23希望尽早Finalize吧。
最近，我们迎来了Atcoder的语言update计划，也就是说，我们即将可以在Atcoder上使用C++20甚至是C++23的Features。
想了下近2年变化也挺大的，从很少看到Lambda，到人均都会Y-combinator的递归写法，所有选手的C++水平也在互相影响和共同进步。
  auto dfs = [&](auto&& dfs, int x) -> void {
    // Y-combinator式递归
    if (x >= 10) return;
    dfs(dfs, x + 1);
  };
本文会侧重于讲一下在算法竞赛中可能会用的上的C++20，或者是17的features。我并非C++语言律师，很多小技巧都是看别人代码或者文章积累过来的，错误不可避免，欢迎指正！
测试环境是g++ (Homebrew GCC 12.2.0) 12.2.0
天知道我想办法在M1上安gcc 12花了多长时间折腾换各种版本的Xcode和对应command line tool。
因为Apple Clang++不支持相当多的C++20的Features，比如ranges。如果你也不幸踩了配置的坑可以来私聊我。
编译期常量

在C++20的更新中，绝大多数的<algorithms>header下的函数都变成了constexpr类型。
例如sort，在C++20之前是这个定义:
template< class RandomIt >
void sort( RandomIt first, RandomIt last );
C++20之后是
template< class RandomIt >
constexpr void sort( RandomIt first, RandomIt last );
可以看到，大量的STL函数可constexpr，简单地说，可以在编译期间运行。这样可以预处理很多东西，例如质数表。
举个栗子，这就是一个在编译期间进行某个排序的函数。
constexpr auto sort(auto arr) {
  std::sort(arr.begin(), arr.end());
  return arr;
}
int main() {
  constexpr auto ret = sort(std::array{3, 2, 1});
  static_assert(std::is_sorted(ret.begin(), ret.end())); // 编译期间检查是否已经排好序
}
此外，除了大量<algorithm>里的函数支持constexpr以外，vector和string也支持，但是有一个缺陷：只可以Transient Allocation。顺时分配。在编译期间运行的函数所分配的内存必须是临时的，在结束后必须释放掉。
因此，如果你要在编译期间创造出一个vector，你必须即时释放掉。
举个例子，如果你直接在main里写
constexpr std::vector<int> v = {1, 2, 3};  // 错误示范
因为我们在编译期间分配的动态内存并没有被消耗，作为代替，我们可以这么写。
在函数scope结束后，内存得到了释放，所以safe。
constexpr int f() {
  std::vector<int> v = {1, 2, 3};
  return v.back();
}
               
int main() {
  constexpr auto x = f();
  std::cout << x << '\n'; // 3
}
关于这个，其实有更多的黑魔法，有兴趣可以自己去查查，真的不想用array还是有办法使用vector然后传回来的。

<ranges> 和黑魔法

ranges原理不再赘述，这里只说实战里怎么用。
std::ranges::sort(a) 可以让我们更方便地进行排序。告别begin，end，从现在做起。
同理，max min 函数也都有相同的用法。
int main() {
  std::vector a = {3, 2, 1}, b = {3, 2, 1};
  std::ranges::sort(a.begin(), a.end());
  std::ranges::sort(b);
  
  for (int x : a) std::cout << x << ' '; // 1 2 3
  for (int x : b) std::cout << x << ' '; // 1 2 3
  std::cout << std::ranges::max(a); // 3
  std::cout << std::ranges::min(a); // 1
  return 0;
}
当然，你可能不想写ranges::这么长一串，于是你试图 using namespace std::ranges;
int main() {
  std::vector a = {3, 2, 1}, b = {3, 2, 1};
  using namespace std::ranges；
  sort(b);
  return 0;
}
但是报错，因为编译器默认你调用了STL里的原版sort函数。
看文章有一个神奇的黑魔法，我理解的有问题，具体解释看评论区吧。
using namespace std;
struct Hoge {};
template <>
struct std::ranges::view_interface<Hoge> {
  static void main() {
    vector<int> a{1, 2, 3};
    cout << max(a) << '\n';
  }
};
int main() {
  std::ranges::view_interface<Hoge>::main();
  return 0;
}

<bit> 让位运算更简单

用了这么多次的_builtin_popcount，可以说再见啦。
C++20之后，可以直接std::popcount。
介绍几个常用的

• has_single_bit: 是否只有一个比特位为1，换句话说，是否为2的次幂。
  
• bit_width: bit有效位，也就是最少有多少位可以表示该数字。
  
• countl_zero, countl_one,: 左端点开始连续0/1个数。
  
• countr_zero, countr_one: 右侧开始连续0/1个数
  
• bit_ceil, bit_floor 返回 n 以上最小的2的次幂或者以下最大的2的次幂。
  

给for loop施加一些魔法

对数组里每个元素进行某个操作，同时更新一个index或者count都是很常用的操作。
int main() {
  std::vector<int> a = {1, 2, 3};
  int idx = 1;
  for (auto x : a) {
    x += idx++;
    std::cout << x << ' ';
  }
}
// 2 4 6
考虑这样一个函数，C++17之后有一个这样的写法。
int main() {
  std::vector<int> a = {1, 2, 3};
  for (int idx = 1; auto x : a) {
    x += idx++;
    std::cout << x << ' ';
  }
}
也可以在直接在循环声明语句里初始化一个数组进行遍历
int main() {
  for (int idx = 0; auto dx : {1, -1, 1, -1}) {
    std::cout << idx + dx << ' ';
    idx++;
  }
}
C++20又有一些好东西让我们更加优雅地for。
int main() {
  for (int idx = 0; auto& x : foo()) { // 在foo里可以更新一些东西
    std::cout << idx + dx << ' ';
    idx++;
  }
}
int main() {
  for (int idx = cal(); auto& x : foo()) { // 在 cal里更新idx
    std::cout << idx + dx << ' ';
    idx++;
  }
}

view

view的知识点非常繁杂，这里只做抛砖引玉，详细请多多参考cppreference。
view是一个很奇妙的东西，他并不存在于内存中，你可以把view看成一个计算，而且是惰性的。
auto a = std::views::iota(0, 10); // 声明一个0 到 10 的数组，不访问或者遍历a的时候，不会占用内存
可以进行多层叠加，用|分割。
int main() {
  std::vector a = {1, 3, 2, 4, 5};
  auto v = a
           | std::views::transform([](int x) { return x * 2; })  // 所有数字 * 2
           | std::views::reverse; // 反转
           | std::views::take(3); // 取前三个
  for (int x : v) std::cout << x << ' '; // 10 8 4
}
配合string_view分割字符串。quoted是一个C++14引入的一个给字符串打引号的东西。
int main() {
  // 这个example来自cppreference
  constexpr std::string_view words{"Hello^_^C++^_^20^_^!"};
  constexpr std::string_view delim{"^_^"};
​
  for (const auto word : std::views::split(words, delim))
    std::cout << std::quoted(std::string_view{word.begin(), word.end()}) << ' ';
  // "Hello" "C++" "20" "!"
}
配合views可以做到只对部分进行排列，或者反向排列
int main() {
  std::vector a = {3, 2, 1, 0, -1};
  // std::sort(a.begin() + 2, a.end()); 等价于下面这行
  std::ranges::sort(std::views::drop(a, 2));

  for (int x : a) std::cout << x << ' '; // 3 2 -1 0 1

  return 0;
}
int main() {
  std::vector a = {1, 2, 3, 4, 5};
  // std::reverse(a.begin(), a.end());
  // std::sort(a.begin() + 1, a.end()); 两行等价于
  std::ranges::sort(std::views::drop(std::views::reverse(a), 1));
​
  for (int x : a) std::cout << x << ' ';  // 4 3 2 1 5
​
  return 0;
}

Contains终于来了

如果你也被map.find(x) != map.end()折磨，好消息是，对multiset, set, map, unordered_set终于有contains可以用了。用法也很简单，而且不会像 count(x) 一样在multiset上有一点点问题。
int main() {
  std::map<int, int> map{{1, 10}, {2, 20}, {3, 30}};
  std::unordered_set<int> u_set{1, 2, 3};
  std::cout << std::boolalpha;
  std::cout << map.contains(1);    // true
  std::cout << u_set.contains(4);  // false
}

倒序访问数组

在C++17，有一个不是很多人知道的小技巧是利用反向迭代器可以做到倒序访问数组
int main() {
  std::vector a = {1, 2, 3, 4, 5};
  std::cout << a.rbegin()[0]; // 5
  std::cout << rbegin(a)[1]; // 4
}
这篇CF的post 教会了我可以直接很Pythonic地用负数来访问。
int main() {
  std::vector a = {1, 2, 3, 4, 5};
  std::cout << a.end()[-1]; // 5
  std::cout << end(a)[-2]; // 4
}
求求你们别写v[v.size() - 2]啦。

<numbers> 里的大量数学常数

是时候告别acosl(-1.0)了。
https://en.cppreference.com/w/cpp/numeric/constants 更多请参考。
黄金分割，各种log，根号的常数都可以直接使用。
int main() {
  using namespace std::numbers;
  std::cout << pi << '\n';
  std::cout << pi_v<long double> << '\n';
  std::cout << e << '\n';
  std::cout << e_v<long double> << '\n';
  std::cout << inv_pi << '\n';
}
/*
3.14159
3.14159
2.71828
2.71828
0.31831
*/
​
STL自带的字符串匹配算法

C++17的<functional>里支持了Boyer Moore的字符串匹配算法。
我们看一个cpp reference上的例子。
int main() {
  constexpr std::string_view haystack =
      "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed "
      "do eiusmod tempor incididunt ut labore et dolore magna aliqua";
​
  const std::string_view needle{"pisci"};
​
  if (const auto it =
          std::search(haystack.begin(), haystack.end(),
                      std::boyer_moore_searcher(needle.begin(), needle.end()));
      it != haystack.end()) {
    std::cout << "The string " << quoted(needle) << " found at offset "
              << it - haystack.begin() << '\n';
  } else {
    std::cout << "The string " << std::quoted(needle) << " not found\n";
  }
}
​
​
// The string "pisci" found at offset 43
虽然简单，但是非常实用。
starts_with 与 ends_with

一个检验目标字符串是否有某个前缀or后缀的函数。
怎么C++20才有这个玩意，冷不丁多个这个略离谱。
int main() {
    std::string s = "bocchi the rock";
    std::cout << std::boolalpha ;
    std::cout << s.starts_with("bocchi") << '\n';  // true
}

我TM直接auto

随着C++地再一次更新，可以auto的东西又增加了，这次是参数。
auto f(auto a, auto b) { return a + b; }
​
// template <class T, class U>
// auto f(T a, U b) { return a + b; }
很自然地，这俩是等价的。
template的类型也是参数，很不自然地，我们可以写出这个代码
template <auto x>
auto g(auto y) {
  return x + y;
}
​
int main() {
  std::cout << g<2>(3);
}
很不自然地，现在可能只有两种东西不能return了。
decltype(auto) 和 std::vector<auto>

制作模板的时候的好习惯 [nodiscard]

有时候模板的函数有返回值，但是跑了函数忘记保存返回值。这时候就需要编译器来提醒我们啦。
​
[[nodiscard("你忘了存我！")]]
std::vector<int> my_super_strong_template() {
  return std::vector<int> {};
}
​
int main() {
  std::vector<int> ans;
  my_super_strong_template(); // 忘记保存值了！ ans = my_super_strong_template()
}
运行期间编译器会告诉你
A.cpp: In function 'int main()':
A.cpp:46:29: warning: ignoring return value of 'std::vector<int> my_super_strong_template()', declared with attribute 'nodiscard': '你忘了存我！' [-Wunused-result]
   46 |   my_super_strong_template();
      |                             ^
A.cpp:41:18: note: declared here
   41 | std::vector<int> my_super_strong_template() {
      |                  ^~~~~~~~~~~~~~~~~~~~~~~~

总结

C++23可以期待的东西更多，那么什么时候主流OJ可以交23呢（
首尾呼应一下，我不是C++语言律师，难免会有错误，欢迎指点和交流，有什么好用的features也可以教教我！
蟹蟹你们看到这里！
Reference

• https://www.modernescpp.com/index.php/constexpr-and-consteval-functions-in-c-20
  
• 競プロで役立つC++20新機能 - Qiita
  
• cppreference.com
  
• [Tutorial] Writing C++ like Python: tricks Python doesn't want you to know - Codeforces
  

美奈提

OI 选手表示 用起来很方便 但是比赛场上不能用[大哭]

秀水清波

不是写给oi选手的小宝贝[可怜] 网络赛玩一玩~

龙战骑士

[笔芯]

提笔不为风雅

什么时候能支持 反向范围for循环  啊

亿元户

最高用到c++17  qwq

冬日的月光

[图片]

鑨

oier表示只能用c++98

用户大雪纷飞

想请教一下，auto/template函数要怎么链接（多个cpp h的时候）[爱]

董一航

OI已经支持到C++14了吧（