综述

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

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

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

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

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

避免使用 vector<bool>,推荐使用 bitset<N>
简单的说就是它并未实际保存一个 bool, 而是用位域的概念进行了封装.
所以你在实际应用的时候可能会发生一些你意料之外的问题.

INT_MAX, DBL_MAX

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

最大最小值

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

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

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 函数做计数器