综述

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

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

等到 Codeforces 支持 C++20 后开始学习 C++2x

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

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

最大最小值

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;

集合交并运算

1
2
3
4
5
6
7
std::et<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 等同理

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 内建的一些好用的函数

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

容器简介

  • 数组,array, vector, deque 都是顺序表
  • queue 是队列,stack 是栈,list 是双向链表,forward_list 是单向链表
  • 标准拓展容器文档

优先队列 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

大数库

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;
}