STL 和 C++17 学习记录

综述

为了更加优雅的写 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，那就变成 inf，inf 的运算规则跟数学的一致。inf - inf = nan 跟 1/0 = nan 一致都是未定义数。

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

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

constexpr 用编译时间换运行时间

好处：安全，加密；坏处：延长了编译时间。看以后的发展了。

替代解决方案：预处理得到文件，然后读取文件（容易有安全问题，另外要考虑独写效率）

最大最小值

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

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

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 （长没关系，有代码补全）

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 是稳定排序，即不改变原有相互不小于的元素的相对位置

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 即声明类型。

集合交并运算

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 表达式递归写法

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 对应的版本。

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>

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 同理。

pb_ds

过题的实例代码：gym 103076I

大数库

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 安装

#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

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

虚函数直白的例子：

#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

class A {
public:
	virtual void print() {
	// void print() {
		std::cout << "A" << std::endl;
	}
	void printS() {
		print();
	}
};
class B : public A {
public:
	void print() {
		std::cout << "B" << std::endl;
	}
};

int main() {
	//freopen("in", "r", stdin);
	std::cin.tie(nullptr)->sync_with_stdio(false);
	A a;
	B b;
	A *p1 = &a;
	A *p2 = &b;
	B *p3 = &b;
	p1->print();
	p2->print();
	p3->print();
	p1->printS();
	p2->printS();
	p3->print();
	return 0;
}

A 的 print 函数前加 virtual 和不加有很大的不同

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

// 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

线程获取返回值

#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_task 和 std::future 是更优雅的做法，下面有例子。

线程交互之消费者问题

根据此文章修改而来

#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 并不是并行的，可能是考虑到对于一般的类的加法并不一定满足结合律，从而没法并行。

#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 的结果并没有更新好就使用了！以下是安全的做法。

#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 会自动根据当前空闲线程判断是否生成子线程。

#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 算法

#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) 了。

综述

`INT_MAX`, `DBL_MAX`

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

constexpr 用编译时间换运行时间

最大最小值

累积运算 accumulate （长没关系，有代码补全）

排序

集合交并运算

lambda 表达式递归写法

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

容器简介

优先队列 priority_queue

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

pb_ds

大数库

GMP

NTL：专攻数论，以后再学吧

Boost：最终选择

2021/1/11 更新

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

mutable 成员

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

lambda 函数做计数器

多线程

线程获取返回值

线程交互之消费者问题

累加函数的并行算法

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

并行版的 Karatsuba 算法

协程

网络编程之 asio

数据库

计算机组成原理

操作系统

编译原理

数值优化

计算机图形学

综述

INT_MAX, DBL_MAX

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

constexpr 用编译时间换运行时间

最大最小值

累积运算 accumulate （长没关系，有代码补全）

排序

集合交并运算

lambda 表达式递归写法

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

容器简介

优先队列 priority_queue

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

pb_ds

大数库

GMP

NTL：专攻数论，以后再学吧

Boost：最终选择

2021/1/11 更新

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

mutable 成员

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

lambda 函数做计数器

多线程

线程获取返回值

线程交互之消费者问题

累加函数的并行算法

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

并行版的 Karatsuba 算法

协程

网络编程之 asio

数据库

计算机组成原理

操作系统

编译原理

数值优化

计算机图形学

`INT_MAX`, `DBL_MAX`

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