综述

为了更加 优雅 的写 C++,在学了一点 C++17 皮毛之后,重新探索了一下 C++ STL,总结一些好用的特征。

static_cast<T>, optional<T> 是两个好东西。

等到 Codeforces 支持 C++20 后开始学习 C++2x,十分期待 C++23 和 C++26。我猜应该等到 C++23 出来之后 Codeforces 才会添加 C++2x。

没有必要关心你自己不用的特征!用的就一定要搞清楚。

以下示例中,凡是 vector 类型的 a.begin(),a.end() 对应的数组类型都可以改成 a,a+n

避免使用 vector<bool>,推荐使用 bitset<N> (更省内存,O2 优化后特别快!,但是注意不能开特别大的局部变量,太大就开全局变量,注意 bitset 是从后往前记的)
简单的说就是它并未实际保存一个 bool, 而是用位域的概念进行了封装.
所以你在实际应用的时候可能会发生一些你意料之外的问题.

INT_MAX, DBL_MAX

注意一般只用来比较大小的初始变量,做运算会有溢出问题。int 溢出本质就是对 $2^31$ 取模,double 会出现大数吃小数(这个涉及 double 的二进制表达,加减的时候要向大的数对齐),一旦超过了 DBL_MAX,那就变成 infinf 的运算规则跟数学的一致。inf - inf = nan1/0 = nan 一致都是未定义数。

optional 有三个顾名思义的函数:have_value, value, value_or

如果无值时调用 value,那么会 RE,这是件好事。

最大最小值

min,max,minmax 都是参数个数为 2,返回的是值。所以不举例了,注意到 minmax 返回的是 pair

min_element,max_element,minmax_element 参数都是 vector,且返回的是索引。

1
2
3
4
5
std::cout << *max_element(a.begin(), a.end()) << std::endl;
auto lr = minmax_element(a.begin(), a.end()); //不能取*,因为返回的是pair类型
std::cout << *lr.first << " " << *lr.second << std::endl;
auto[l, r] = minmax_element(a.begin(), a.end()); //自动解析也行
std::cout << *l < " " << *r << std::endl;

累积运算 accumulate (长没关系,有代码补全)

1
2
3
4
5
6
7
8
9
std::vector<int> a{1, 3, 2, 4};
std::cout << accumulate(a.begin(), a.end(), 0) << std::endl; //默认累和
std::cout << accumulate(a.begin(), a.end(), 0, std::plus<int>()) << std::endl; //可选加减乘除
std::cout << accumulate(a.begin(), a.end(), 0, std::minus<int>()) << std::endl;
std::cout << accumulate(a.begin(), a.end(), 1, std::multiplies<int>()) << std::endl;
std::cout << accumulate(a.begin(), a.end(), 1, std::divides<int>()) << std::endl;
std::cout << accumulate(a.begin(), a.end(), 0, [](auto & x, auto & y) {
return 3 * x + y;
}) << std::endl;

排序

stable_sort 是稳定排序,即不改变原有相互不小于的元素的相对位置

1
2
3
4
5
6
7
8
9
10
std::sort(a.begin(), a.end()); // 默认从小到大排序
std::sort(a.begin(), a.end(), std::less<int>()); // 手动从小到大排序(不一定是int,具体问题具体修改)
std::sort(a.rbegin(), a.end()); // 从大到小排序
std::sort(a.begin(), a.end(), std::greater<int>()); // 从大到小排序
//对于 tuple 和 pair 大小关系都是从按照字典序比较的
std::sort(a.begin(), a.end(), [](int & x, int & y) {
return (x ^ 4) < (y ^ 4); // 位运算的优先级好低呀
});
for (auto & x: a) std::cout << x << " ";
std::cout << std::endl;

std::tuple_size<decltype(tupleExample)>::value; 可以获得 tuple 是多少维的。其中 decltype 代表 declare type 即声明类型。

集合交并运算

1
2
3
4
5
6
7
std::set<int> x{1, 2, 3};
std::set<int> y{2, 3, 5};
std::set<int> t;
std::set_intersection(x.begin(), x.end(), y.begin(), y.end(), std::inserter(t, t.begin()));
// 若x,y,t是vector等有push_back 的容器,就可以使用
// set_intersection(x.begin(),x.end(),y.begin(),y.end(),back_inserter(t));
// set_union,set_difference,set_symmetric_difference 等同理

优先使用 unorder_set

lambda 表达式递归写法

1
2
3
4
5
function<int(int, int)> gcd = [ & ](int a, int b) -> int { // 注意最前面不能用auto
return b ? gcd(b, a % b) : a;
};
std::cout << gcd(102, 210) << std::endl;
std::cout << std::__gcd(102, 210) << std::endl;

C++ STL 内建的一些好用的函数

下面函数后加 ll 就可以得到 unsigned long long 对应的版本。

1
2
3
4
5
6
7
8
9
10
11
12
using uint = unsigned int;
__builtin_parity(uint n): 返回n的二进制1的个数奇偶性
__builtin_clz(uint n): 返回n的二进制前置0的个数
__builtin_ctz(uint n): 返回n的二进制后置0的个数
__builtin_ffs(int n): 返回n的二进制从后往前第一次出现1的位置
= __builtin_ctz(uint n)+1
__builtin_popcount(uint n): 返回n的二进制1的个数,以上函数仅在GCC中有
__lg(int n): 返回log2(n)的整数部分
lowbit(uint n): n&(-n) 返回使得最大的2^i|n // 这个不是内建的
//产生大的随机数
std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
*/

容器简介

  • array, vector, deque, list(双向链表),forward_list(单向链表) 都是顺序容器。
  • set, map 是关联容器。
  • unordered_map 和 unordered_set 是无序关联容器
  • stack,queue,priority_queue 严格说不是容器,而是容器适配器(默认使用 deque,可以自己换成 vector)

优先队列 priority_queue

  • std::priority_queue<int> 是默认最大堆,即头部是最大值。
  • 最小堆可以用 std::priority_queue<int, std::vector<int>, std::greater<>>
  • 如果一般化地情况,std::priority_queue<Node> 其中 Node 中要定义小于号,然后也是最大堆。例如 Node 可以是 std::pair<int, int>
    1
    2
    3
    4
    5
    6
    7
    struct Node {
    int x, y;
    Node(int _x, int _y) : x(_x), y(_y) {}
    bool operator< (const Node &A) const {
    return x * A.y < y * A.x;
    }
    };
  • 另一种方式(cmp 中出现的 lambda 函数必须是全局变量),例如对 pii = std::pair<int, int>
    1
    2
    3
    4
    5
    6
    class cmp {
    public:
    bool operator() (const pii &lhs, const pii &rhs) const {
    return lhs.first * rhs.second < rhs.second * rhs.first;
    }
    };

注意优先队列不能随机访问和自然遍历 0.0

注意 map 和 unordered_map 的数据污染问题

map 中支持 mp[i] 的直接调用(即使没有数据 i,此时默认返回 0),但是次调用会污染了数据,即此时无论 mp 中是否有元素 i, i 都被添加到 mp 中。此时调用迭代器,i 就会出现了,这里需要特别注意。

unordered_map 同理。

大数库

GMP

谁说 GMP 好用的,出来挨打!已经抛弃

Ubuntu 20.04 好像内置安装了 GMP,如果没安装可以使用 sudo apt install libgmp-dev 安装(可能需要安装 m4)
使用的时候 #include <gmpxx.h> 就好了(带 xx 表示 C++ 使用,不带表示 C 使用),不过它真的难用

NTL:专攻数论,以后再学吧

NTL 才是正确的选择,但是它的高效是需要借助 GMP 的

Boost:最终选择

Boost 是激进的 STL,STL 是保守的 Boost

一键安装:sudo apt install libboost-all-dev,正确用法:

1
2
#include <boost/multiprecision/cpp_int.hpp>
using BINT = boost::multiprecision::cpp_int;

win10 下 WSL ubuntu20.04 真香。全所未有的方便!
win10 下 还可以用 MSYS2 安装

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <boost/multiprecision/cpp_int.hpp>
using BINT = boost::multiprecision::cpp_int;
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
#define print(x) std::cout << (x) << std::endl
#define println std::cout << std::endl
using LL = long long;
using pii = std::pair<int, int>;
using pll = std::pair<LL, LL>;

const int N = 2e3 + 2;
int sp[N], p[N];
int spf() {
int cnt = 1;
p[1] = 2;
for (int i = 2; i < N; i += 2) sp[i] = 2;
for (int i = 1; i < N; i += 2) sp[i] = i;
for (int i = 3; i < N; i += 2) {
if (sp[i] == i) p[++cnt] = i;
for (int j = 1; j <= cnt && p[j] <= sp[i] && i * p[j] < N; ++j) { //防止乘法溢出
sp[i * p[j]] = p[j]; // 注意到sp只被赋值一次
}
}
return cnt;
}
BINT f[N];
BINT getPowSum(LL n, int k) { // k<1000
if (k == 0) return BINT(n);
if (p[1] != 2) spf();
int nk = 2 * k + 1;
f[0] = 0;
f[1] = 1;
auto bPow = [](BINT x, int n) -> BINT {
BINT r(1);
for (; n; x *= x, n >>= 1) if (n&1) r *= x;
return r;
};
for (int i = 2; i <= nk + 1; ++i) {
if (sp[i] == i) f[i] = bPow(BINT(i), k);
else f[i] = f[sp[i]] * f[i / sp[i]];
}
for (int i = 1; i <= nk; ++i) f[i] += f[i - 1];
if (n <= nk) return f[n];
BINT res = 0, tl = 1, tr = 1;
for (int i = nk - 1; i >= 0; --i) tr = tr * (n - i - 1) / (nk - i);
for (int i = 0; i <= nk; ++i) {
if ((nk - i) & 1) res -= f[i] * tl * tr;
else res += f[i] * tl * tr;
tl = tl * (n - i) / (i + 1);
tr = tr * (nk - i) / (n - i - 1);
}
return res;
}

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

std::cout << getPowSum(100, 2) << std::endl;

return 0;
}

2021/1/11 更新

指向 const 的指针 p, const 指针 q 和 指向 const 的 const 指针 pq

1
2
3
4
5
6
7
8
const int i = 0;
const int j = 1;
const int *p {&i};
*p = &j;
int k = 0;
int * const q {&k};
*q = 1;
const int * const pq{&j};

mutable 成员

multable 成员指出,即使是 const 对象,它的 mutable 成员也是可以被修改的(例如计数的)

虚函数 virtual, 重载 overide,不再允许子类重载 final

假设基类 的 A 函数需要调用 B 函数,而子类有对 B 进行覆盖。那么子类在调用(从基类继承的) A 函数时,并不会调用子类的 B 函数,而是调用基类的 B 函数。如果像 A 函数调用的是子类中的 B 函数,那么只需在 A 函数前加 virtual 关键字即可,此时最好在子类的函数中添加一个 overide 关键字,例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// Box.hpp
#ifndef BOX_HPP
#define BOX_HPP
#include <bits/stdc++.h>
class Box {
double x = 2;
protected:
double length {1.0};
double width {1.0};
double height {1.0};
public:
Box() = default;
Box(double lv, double wv, double hv) : length {lv}, width {wv}, height {hv} {}
// Function to show the volume of an object
void showVolume() const { std::cout << "Box usable volume is " << volume() << std::endl; }
// Function to calculate the volume of a Box object
virtual double volume() const { return length * width * height; }
};

#endif

// Package.hpp
#ifndef PACKAGE_H
#define PACKAGE_H
#include "Box.hpp"
class Package : public Box {
public:
// Constructor
Package(double lv, double wv, double hv) : Box {lv, wv, hv} {}
// Function to calculate volume of a ToughPack allowing 15% for packing
double volume() const override { return 0.85 * length * width * height; }
};
#endif

// main.cpp
#include "Box.hpp" // For the Box class
#include "Package.hpp" // For the ToughPack class
int main() {
Box box {20.0, 30.0, 40.0}; // Define a box
Package hardcase {20.0, 30.0, 40.0}; // Declare tough box - same size
box.showVolume(); // Display volume of base box
hardcase.showVolume(); // Display volume of derived box
}

lambda 函数做计数器

多线程

这真的是特别大的一块内容。在处理多线程的时候一定要设计的特别细心,思路清晰,否则 bug 无穷无尽。很多单线程安全的代码,一到多线程马上不安全了。

学习资料:知乎cppReference在线电子书:C++ 并发编程实战 第二版 (C++ Concurrency in Action - SECOND EDITION)cnblog

线程获取返回值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

// 多线程函数获取返回值的方式
class A {
public:
int operator() (const int &a, const int & b, std::promise<int> &promiseObj) const {
promiseObj.set_value(a + b);
return a + b;
}
};

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
A a;
std::promise<int> promiseObj;
std::future<int> futureObj = promiseObj.get_future();
std::thread th1(a, 1, 2, std::ref(promiseObj));
th1.join();
watch(futureObj.get()); // 注意只能 get 一次。
return 0;
}

上述为最基本的做法,使用 std::packaged_taskstd::future 是更优雅的做法,下面有例子。

线程交互之消费者问题

根据 此文章 修改而来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
#include <unistd.h>

// 生产者消费者问题
void solve() {
std::queue<int> q;
std::mutex mu;
std::condition_variable cond;
const int C = 3; // 最大产品量
const int ST = 2; // 休眠时间
auto producer = [&]() {
std::srand(std::time(nullptr));
while (1) {
if(q.size() < C) { // 限流
int data = std::rand();
std::unique_lock locker(mu);
q.push(data);
std::cout << "Saving " << data << std::endl;
cond.notify_one(); // 通知取
}
sleep(ST);
}
};
auto consumer = [&]() {
while (1) {
std::unique_lock locker(mu);
while (q.size() < C) cond.wait(locker); // 满了之后一次取完
while (!q.empty()) {
int data = q.front();
q.pop();
std::cout << "withdraw " << data << std::endl;
}
sleep(ST);
}
};
std::thread t1(producer);
std::thread t2(consumer);
t1.join();
t2.join();
}

int main() {
solve();
return 0;
}

累加函数的并行算法

STL 中 std::accumulate 并不是并行的,可能是考虑到对于一般的类的加法并不一定满足结合律,从而没法并行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl

// https://www.bookstack.cn/read/CPP-Concurrency-In-Action-2ed-2019/content-chapter8-8.4-chinese.md
template<typename Iterator, typename T>
class AccumulateBlock {
public:
void operator()(Iterator start, Iterator end, T &r) {
r = std::accumulate(start, end, r);
}
};

template<typename Iterator, typename T>
T accumulateParallel(Iterator start, Iterator end, T init) {
int n = std::distance(start, end);
if (n == 0) return init;
const int minPerThread = 25; // 单个线程最小处理数据长度。
const int maxThread = (n + minPerThread - 1) / minPerThread;
const int hardwareThread = std::thread::hardware_concurrency();
int threadsNum = std::min(hardwareThread == 0 ? 1 : hardwareThread, maxThread);
watch(threadsNum);
int blockSize = n / threadsNum;
std::vector<T> results(threadsNum);
std::vector<std::thread> threads(threadsNum - 1);
Iterator blockStart = start;
for (int i = 0; i < threads.size(); ++i) {
Iterator blockEnd = blockStart;
std::advance(blockEnd, blockSize);
threads[i] = std::thread(AccumulateBlock<Iterator, T>(), blockStart, blockEnd, std::ref(results[i]));
blockStart = blockEnd;
}
AccumulateBlock<Iterator,T>()(blockStart, end, results.back());
std::for_each(threads.begin(), threads.end(), std::mem_fn(&std::thread::join));
return std::accumulate(results.begin(), results.end(), init);
}

int main() {
// freopen("in", "r", stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 5e7 + 2;
std::vector<int> a(n);
// watch(RAND_MAX);
std::srand(std::time(nullptr));
for (auto &x : a) x = rand();

auto start2 = std::clock();
auto r2 = std::accumulate(a.begin(), a.end(), 0LL);
watch(r2);
std::cout << "Time used: " << (std::clock() - start2) << "ms" << std::endl;

auto start = std::clock();
auto r = accumulateParallel(a.begin(), a.end(), 0LL);
watch(r);
std::cout << "Time used: " << (std::clock() - start) << "ms" << std::endl;

return 0;
}

还真能变很多(我电脑 6 核 6 线程的,时间运行为 1/4),不过上述代码是不安全的,因为可能 result 的结果并没有更新好就使用了!以下是安全的做法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl

// https://www.bookstack.cn/read/CPP-Concurrency-In-Action-2ed-2019/content-chapter8-8.4-chinese.md
template<typename Iterator, typename T>
class AccumulateBlock {
public:
T operator()(Iterator start, Iterator end) {
return std::accumulate(start, end, T());
}
};

template<typename Iterator, typename T>
T accumulateParallel(Iterator start, Iterator end, T init) {
int n = std::distance(start, end);
if (n == 0) return init;
const int minPerThread = 25; // 单个线程最小处理数据长度。
const int maxThread = (n + minPerThread - 1) / minPerThread;
const int hardwareThread = std::thread::hardware_concurrency();
int threadsNum = std::min(hardwareThread == 0 ? 1 : hardwareThread, maxThread);
// watch(threadsNum);
int blockSize = n / threadsNum;
std::vector<std::future<T>> futures(threadsNum - 1);
std::vector<std::thread> threads(threadsNum - 1);
auto blockStart = start;
for (int i = 0; i < threads.size(); ++i) {
Iterator blockEnd = blockStart;
std::advance(blockEnd, blockSize);
std::packaged_task<T(Iterator, Iterator)> task{AccumulateBlock<Iterator, T>()};
futures[i] = task.get_future();
threads[i] = std::thread(std::move(task), blockStart, blockEnd);
blockStart = blockEnd;
}
T r = AccumulateBlock<Iterator,T>()(blockStart, end) + init;
// 最后在加入线程貌似会更快,我也不懂为啥
std::for_each(threads.begin(), threads.end(), std::mem_fn(&std::thread::join));
for (auto &x : futures) r += x.get();
return r;
}

int main() {
// freopen("in", "r", stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 5e7 + 2;
std::vector<int> a(n);
// watch(RAND_MAX);
std::srand(std::time(nullptr));
for (auto &x : a) x = rand();

auto start = std::clock();
auto r = accumulateParallel(a.begin(), a.end(), 0LL);
watch(r);
std::cout << "Time used: " << (std::clock() - start) << "ms" << std::endl;

auto start2 = std::clock();
auto r2 = std::accumulate(a.begin(), a.end(), 0LL);
watch(r2);
std::cout << "Time used: " << (std::clock() - start2) << "ms" << std::endl;
return 0;
}

一起查找,有线程找到就全部结束。

用到了递归中调用多线程,async 会自动根据当前空闲线程判断是否生成子线程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl

// https://www.bookstack.cn/read/CPP-Concurrency-In-Action-2ed-2019/content-chapter8-8.5-chinese.md
template<typename Iterator, typename MatchType>
Iterator findParallelCore(Iterator start, Iterator end, MatchType match, std::atomic<bool> &done) {
try {
const int n = std::distance(start, end);
const int minPerThread = 25;
if (n < minPerThread * 2) {
while (start != end && !done.load()) {
if (*start == match) {
done = true;
return start;
}
++start;
}
return end;
} else {
auto mid = start;
std::advance(mid, n / 2);
std::future<Iterator> asyncResult =
std::async(findParallelCore<Iterator, MatchType>, mid, end, match, std::ref(done));
Iterator directResult = findParallelCore(start, mid, match, done);
return directResult == mid ? asyncResult.get() : directResult;
}
} catch (...) {
done = true;
throw;
}
}
template<typename Iterator, typename MatchType>
Iterator findParallel(Iterator start, Iterator end, MatchType match) {
std::atomic<bool> done(false);
return findParallelCore(start, end, match, done);
}

int main() {
// freopen("in", "r", stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 1e3 + 2;
std::vector<int> a(n);
// watch(RAND_MAX);
std::srand(std::time(nullptr));
for (auto &x : a) x = rand();
auto start = std::clock();
auto r = findParallel(a.begin(), a.end(), 123);
watch(std::distance(a.begin(), r));
if (r != a.end()) watch(*r);
std::cout << "Time used: " << (std::clock() - start) << "ms" << std::endl;
return 0;
}

由于 std::find 本身是并行的,因此没必要和它比较效率。

并行版的 Karatsuba 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

// 任意模数多项式乘法 O(n^{\log_2 3})
using VL = std::vector<LL>;
VL KaratsubaParallel(VL a, VL b, LL p) {
if (a.size() < b.size()) std::swap(a, b);
auto mulS = [&](VL a, VL b) {
int n = a.size(), m = b.size(), sz = n + m - 1;
std::vector<__int128> c(sz);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
c[i + j] += a[i] * b[j];
}
}
VL r(sz);
for (int i = 0; i < sz; ++i) r[i] = c[i] % p;
return r;
};
const int N = 65;
std::function<VL(VL, VL, int)> mul = [&](VL a, VL b, int n) -> VL {
if (n < N) return mulS(a, b);
int n2 = n / 2, n1 = n - 1;
VL a2 = VL(a.begin() + n2, a.end());
VL b2 = VL(b.begin() + n2, b.end());
a.resize(n2); b.resize(n2);
VL ap = a2, bp = b2;
for (int i = 0; i < n2; ++i) if ((ap[i] += a[i]) >= p) ap[i] -= p;
for (int i = 0; i < n2; ++i) if ((bp[i] += b[i]) >= p) bp[i] -= p;
std::future<VL> abThread = std::async(mul, a, b, n2);
VL a2b = mul(ap, bp, n2);
VL ab = abThread.get();
VL a2b2 = mul(a2, b2, n2);
for (int i = 0; i < n1; ++i) {
if ((a2b[i] -= ab[i]) < 0) a2b[i] += p;
if ((a2b[i] -= a2b2[i]) < 0) a2b[i] += p;
}
auto r = ab;
r.emplace_back(0);
r.insert(r.end(), a2b2.begin(), a2b2.end());
for (int i = 0; i < n1; ++i) if ((r[i + n2] += a2b[i]) >= p) r[i + n2] -= p;
return r;
};
int n = a.size(), m = b.size(), tot = n + m - 1, sz = 1;
if (m < N || n / m * 2 > m) return mulS(a, b);
while (sz < n) sz *= 2;
a.resize(sz), b.resize(sz);
auto r = mul(a, b, sz);
r.resize(tot);
return r;
} // 模板例题:https://www.luogu.com.cn/problem/P4245

int main() {
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
LL p;
std::cin >> n >> m >> p;
VL a(n + 1), b(m + 1);
for (auto &x : a) {
std::cin >> x;
x %= p;
}
for (auto &x : b) {
std::cin >> x;
x %= p;
}
VL c = KaratsubaParallel(a, b, p);
for (auto &x : c) std::cout << x << " ";
std::cout << "\n";
return 0;
}

协程

已经加入 C++20,但是是给库开发者使用的,要 C++23 才适合一般开发者使用,到那时就有类似于 Python yield 表达式一样的生成器(generator) 了。

网络编程之 asio

很依赖 boost,将于 C++23 加入 STL

学习资料:官方库基于 asio 的 C++ 网络编程

数据库

计算机组成原理

操作系统

https://www.bilibili.com/video/BV1js411b7vg?p=1

编译原理

数值优化

计算机图形学